HMMT-Feb 2023 guts, Problem 35

The Fibonacci numbers are defined recursively by $F_{0}=0, F_{1}=1$, and $F_{i}=F_{i-1}+F_{i-2}$ for $i \geq 2$. Given 30 wooden blocks of weights $\sqrt[3]{F_{2}}, \sqrt[3]{F_{3}}, \ldots, \sqrt[3]{F_{31}}$, estimate the number of ways to paint each block either red or blue such that the total weight of the red blocks and the total weight of the blue blocks differ by at most 1 . Submit a positive integer $E$. If the correct answer is $A$, you will receive $\left\lfloor 25 \min \left((E / A)^{8},(A / E)^{8}\right)\right\rfloor$ points. (If you do not submit a positive integer, you will receive zero points for this question.)

Solution: Solution: To get within an order of magnitude, one approach is to let $X_{n}$ be a random variable which takes the value $\pm \sqrt[3]{F_{n}}$, with the sign chosen uniformly at random. We want the probability that $S=\sum_{i=2}^{31} X_{i}$ is in $[-1,1]$. We can attempt to approximate the distribution of $S$ as normal (this is loosely justified because it is the sum of many independent random variables). Using the approximation $F_{n} \approx \frac{1}{\sqrt{5}} \varphi^{n}$ for $\phi=\frac{1+\sqrt{5}}{2}$, the variance of $S$ is: \[ \begin{aligned} \operatorname{Var}(S) & =\sum_{i=2}^{31} \operatorname{Var}\left(X_{i}\right) \\ & =\sum_{i=2}^{31} F_{i}^{2 / 3} \\ & \approx \sum_{i=2}^{31} 5^{-1 / 3} \varphi^{2 i / 3} \\ & \approx 5^{-1 / 3} \cdot\left(\frac{\varphi^{62 / 3}}{1-\varphi^{-2 / 3}}\right) \end{aligned} \] Now, we use the fact that if $\frac{1}{\sqrt{\operatorname{Var}(S)}} S$ is standard normal, then the probability that $S \in[-1,1]$ is approximately \[ \frac{1}{\sqrt{2 \pi}} \cdot \frac{2}{\sqrt{\operatorname{Var}(S)}} \approx \sqrt{\frac{2 \cdot 5^{1 / 3}}{\pi}} \cdot \frac{\sqrt{1-\varphi^{-2 / 3}}}{\varphi^{31 / 3}} \] When we multiply this by $2^{30}$, we get an approximation of $E \approx 4064598$, which achieves $A / E \approx 0.96$ and would score 17 out of 25 points. $\fbox{3892346}$.

Answer: 3892346