Given any five points on a sphere, show that some four of them must lie on a closed hemisphere
Hint: There is a one-line proof of this
Solution: Cut the circle into two hemispheres meeting at the plane defined by the center of the sphere and any two of the five points.
By pigeonhole, at least one of these two hemispheres must contain two of the three remaining points, and so we are done.
Two players play a game on a 3 x 3 board. The first player places a 1 on an empty square and the second player places a 0 on an empty square. Play continues until all squares are occupied. The second player wins if the resulting determinant is 0 and the first player wins if it has any other value. Who wins?
Just to make things easier, call the first player (who places 1s) Player 1, and the second player (who places 0s) Player 0.
Hints: Player 0 wins
Show that two columns of the matrix cannot sum to another
Solution: First, we show that no two rows can sum to another. Note that there are exactly 5 1s and 4 0s in the matrix at the end of the game. However, if the matrix had the form \[ \begin{pmatrix} a & a' & a + a'\\ b & b' & b + b'\\ c & c' & c + c' \end{pmatrix} \] This would imply that there are 6 1s in the matrix. So the only way for the determinant to be zero is to have two identical rows or columns, or for there to be a row or column that is purely zero. As a special case of the first observation, note that if zero manages to build a 2x2 square of all zeroes, they win by default. With these observations in mind, let's consider positions from which zero can force a win. If we have a position of the form \[ \begin{pmatrix} 0 & 0 & \_ \\ 0 & \_ & \\ \_ & & \end{pmatrix} \] (where two of the three _ should be empty spaces) or anything equivalent to it (in the sense of reachable from it via row/column operations, which maintain the determinant), no matter what 1 plays, 0 either make a row of all zeroes or build a 2x2 square. So 1 has to stop 0 from reaching this position. However, since all first moves by 1 are equivalent under row and column operations, 0 can always reach a position equivalent to \[ \begin{pmatrix} 1 & & & \\ & 0 & &\\ & & & \end{pmatrix} \] Since the determinant is invariant under transpose, and both moves played so far are on the main diagonal, on the next move 0 can without loss play in the bottom moddle. If 1's previous move was not at the top middle, 1 is forced to move there now (so the two situations are equivalent). There are now 2 cases, if 1 played either in the middle right or in the middle left, then a move in the opposite corner provudes the winning position described above. if 1 plays in one of the corners, a move in the middle edge on the opposite side also produces the winning position from above.
Let \(P(x) = x^2 - 3x - 7\), and let \(Q(x)\) and \(R(x)\) be two quadratic polynomials with the coefficient of \(x^2\) equal to \(1\). David computes each of the three sums \(P + Q, P + R, Q + R\), and is surprised to find that each pair of sums has a common root, and these three common roots are distinct. If \(Q(0) = 2\), then \(R(0) = \frac{m}{n}\), where \(m\) and \(n\) are relatively prime integers. Find \(m + n\).
Hint: TFP!
A regular \(100\)-gon is dissected into some number of parallelograms and two triangles. Prove that these triangles are equal.
Solution: Did not solve
There are \(n\) cars moving forward on a track. The speed of each car is sampled randomly, say from \([0, 1]\). When a faster car approaches a slower car, the faster car must slow down to match the speed of the slower car, forming a "cluster" of two cars. Similarly, if \(c_1\) is faster than \(c_2\) and \(c_2\) is faster than \(c_3\), the cars \(c_1, c_2, c_3\) will form a cluster of three cars (assuming that \(c_1, c_2, c_3\) are consecutive cars). Cars never speed up, only slow down. Given \(n\) cars on the track, what is the expected number of clusters \(X\)?
Hint: Consider the probability that any given car is at the front of a cluster and then use linearity of expectation.
Solution: Note that a car is at the front of a cluster iff it is slower than every car in front of it. This occurs with probability \(\frac{1}{k}\), where \(k\) is the number of cars in front of our particular car. By linearity of expectation
\[
E[X] = \sum_{k = 1}^n \frac{1}{n - k} = \sum_{k = 0}^n \frac{1}{k}
\]
which is the \(n\)-th harmonic number and cannot be simplified.
We also solved a slightly harder variant of the problem in which singleton cars are not considered clusters. A car \(C_i\) is a singleton cluster iff it is slower than every car after it AND faster than the car immediately before it. This is equivalent to saying that if we consider the set of cars \(\{C_{i - 1}, \dots, C_n\}\), the slowest should be \(C_{i - 1}\), and the second slowest should be \(C_i\), which occurs with probability \(\frac{1}{k(k - 1)}\). Thus, for this variant.
\[
E[X_1] = \sum_{k = 1}^n \frac{1}{k} - \frac{1}{n} - \sum_{k = 2}^n \frac{1}{k(k - 1)} = -1 + \sum_{k = 1}^n \frac{1}{k}
\]
Which is also intractable.
Prove that \[ \Biggl (\frac{1}{1} + \frac{1}{1 \cdot 3} + \frac{1}{1 \cdot 3 \cdot 5} + \dots \Biggr ) + \frac{1}{1 + \frac{1}{ 1 + \frac{2}{1 + \frac{3}{1 + \frac{4}{1 + \frac{5}{1 + \dots}}}}}} = \sqrt{\frac{\pi e}{2}} \]
Hints: Try writing the sum as as a taylor series, in partiuclar, try setting up a differential equation for \( \frac{x}{1} + \frac{x^3}{1 \cdot 3} + \frac{x^5}{1 \cdot 3 \cdot 5} \dots \) and solving for \(f(x)\)
For the continued fraction, I kinda don't understand what we did there tbh
Solution: Let \(f(x) = x + \frac{x^3}{1 \cdot 3} + \frac{x^5}{1 \cdot 3 \cdot 5} + \dots \). Then \(f'(x) = 1 + \frac{x^2}{1} + \frac{x^4}{1 \cdot 3} + \frac{x^6}{1 \cdot 3 \cdot 5} = xf(x) + 1, f(0) = 0\). This differential equation can be solved (using either integrating factors or WolframAlpha) to yield
\[ f(x) = \sqrt{\frac{\pi}{2}}e^{\frac{x^2}{2}}\text{erf} \Biggl (\frac{x}{\sqrt{2}} \Biggr ) \]
where
\[ \text{erf}(x) = \frac{2}{\sqrt{\pi}} \int^{x}_0 e^{-t^2} dt \]
though the actual definition of erf is not hugely relevant. This is convenient, as \( \sqrt{\frac{\pi e}{2}} \) shows up when \( x = 1 \), which is where \( f(x) \) equals the sum we are interested in
Next, we work on the continued fraction. We want to define a function \( g(x) \) such that \( g(1) = \frac{1}{1 + \frac{1}{ 1 + \frac{2}{1 + \frac{3}{1 + \frac{4}{1 + \frac{5}{1 + \dots}}}}}} \) and \( g(x) \) satisfies
\[ g(x) = \sqrt{\frac{\pi}{2}}e^{\frac{x^2}{2}} \Biggl( 1 - \text{erf} \Biggl( \frac{x}{\sqrt{2}} \Biggr) \Biggr) \]
Since then \( f(x) + g(x) = \sqrt{\frac{\pi e}{2}} \)