MathDB

4

Part of 2019 CMIMC

Problems(4)

2019 A/NT4: Greatest Common Divisor is Three

Source:

1/27/2019
Determine the sum of all positive integers nn between 11 and 100100 inclusive such that gcd⁡(n,2n−1)=3.\gcd(n,2^n - 1) = 3.
greatest common divisor2019number theory
2019 C/CS4: A Search Algorithm

Source:

1/27/2019
Define a search algorithm called powSearch\texttt{powSearch}. Throughout, assume AA is a 1-indexed sorted array of distinct integers. To search for an integer bb in this array, we search the indices 20,21,…2^0,2^1,\ldots until we either reach the end of the array or A[2k]>bA[2^k] > b. If at any point we get A[2k]=bA[2^k] = b we stop and return 2k2^k. Once we have A[2k]>b>A[2k−1]A[2^k] > b > A[2^{k-1}], we throw away the first 2k−12^{k-1} elements of AA, and recursively search in the same fashion. For example, for an integer which is at position 33 we will search the locations 1,2,4,31, 2, 4, 3.
Define g(x)g(x) to be a function which returns how many (not necessarily distinct) indices we look at when calling powSearch\texttt{powSearch} with an integer bb at position xx in AA. For example, g(3)=4g(3) = 4. If AA has length 6464, find g(1)+g(2)+…+g(64).g(1) + g(2) + \ldots + g(64).
search2019computer sciencealgorithm
2019 G4: Cube in a Right Tetrahedron

Source:

1/27/2019
Suppose T=A0A1A2A3\mathcal{T}=A_0A_1A_2A_3 is a tetrahedron with ∠A1A0A3=∠A2A0A1=∠A3A0A2=90∘\angle A_1A_0A_3 = \angle A_2A_0A_1 = \angle A_3A_0A_2 = 90^\circ, A0A1=5,A0A2=12A_0A_1=5, A_0A_2=12 and A0A3=9A_0A_3=9. A cube A0B0C0D0E0F0G0H0A_0B_0C_0D_0E_0F_0G_0H_0 with side length ss is inscribed inside T\mathcal{T} with B0∈A0A1‾,D0∈A0A2‾,E0∈A0A3‾B_0\in \overline{A_0A_1}, D_0 \in \overline{A_0A_2}, E_0 \in \overline{A_0A_3}, and G0∈△A1A2A3G_0\in \triangle A_1A_2A_3; what is ss?
geometry3D geometrytetrahedron
2019 T4: Expected Area of Triangle

Source:

1/27/2019
Let △A1B1C1\triangle A_1B_1C_1 be an equilateral triangle of area 6060. Chloe constructs a new triangle △A2B2C2\triangle A_2B_2C_2 as follows. First, she flips a coin. If it comes up heads, she constructs point A2A_2 such that B1B_1 is the midpoint of A2C1‾\overline{A_2C_1}. If it comes up tails, she instead constructs A2A_2 such that C1C_1 is the midpoint of A2B1‾\overline{A_2B_1}. She performs analogous operations on B2B_2 and C2C_2. What is the expected value of the area of △A2B2C2\triangle A_2B_2C_2?
geometry2019team