Make $2$ cubes out of $1729$ unit cubes, expected number of times you have to paint

I'm trying to solve question 6 from the PuMac 2007 Combinatorics A competition:

Joe has $1729$ randomly oriented randomly arranged unit cubes, which are initially unpainted. He makes two cubes of sidelengths $9$ and $10$ or of sidelengths $1$ and $12$ (randomly chosen). These cubes are dipped into white paint. Then two more cubes of sidelengths $1$ and $12$ or $9$ and $10$ are formed from the same unit cubes, again randomly oriented and randomly arranged, and dipped into paint. Joe continues this process until every side of every unit cube is painted. After how many times of doing this is the expected number of painted faces closest to half of the total?

Here's what I got so far:

• ${1\over2}$ chance of this happening: If you make two cubes of side lengths $9$ and $10$, then $16$ cubes will have $3$ faces sharing a vertex painted, $12(8 + 7) = 180$ cubes will have $2$ faces sharing an edge painted, $6(8^2 + 7^2) = 678$ cubes will have $1$ face painted, and the remaining $7^3 + 8^3 = 855$ cubes will have no faces painted.

• ${1\over2}$ chance of this happening: If you make two cubes of side lengths $1$ and $12$, then $1$ cube will have all $6$ faces painted, $8$ cubes will have $3$ faces sharing a vertex painted, $12(10) = 120$ cubes will have $2$ faces sharing an edge painted, $6(10^2) = 600$ cubes will have $1$ face painted, and the remaining $10^3 = 1000$ cubes will have no faces painted.

But I'm stuck as this point, and don't know what to do next. Any help would be well-appreciated.

Solution 1:

Thankfully we are being asked about the expected value of this random variable, the random variable is a sum of simpler random variables, namely whether each unit face remains unpainted or not, so we can exploit linearity of expectation.

If we are able to find a good expression for the expected value after $k$ steps then we must simply find which $k$ yields the value closest to $6\times 1729/2$

First note all $6\times 1729$ of the faces are identical. The expected number of painted faces after $k$ steps is equal to the probability $p_k$ that a face remains unpainted after $k$ steps multiplied by $6\times 1729$.

Hence we are simply asked to find the value of $k$ for which $p_k$ is closest to $\frac{1}{2}$.

Now, since every step is independent we begin by finding the probability $q$ that a face is painted in a single step. Assume we are in the $9,10$ case and notice that each possible location and orientation of the unit cube of our face is equally likely, so the probability that it is on the outside (and hence gets painted) is $\frac{6\times9^2 + 6\times 10^2}{6\times1729}$. For the other case we get $\frac{6\times 1^2 + 6\times 12^2}{6\times 1729}$, so $q = \frac{1}{2}\frac{6\times9^2 + 6\times 10^2}{6\times 1729} + \frac{1}{2}\frac{6\times 1^2 + 6\times 12^2}{6\times 1729} = \frac{7^2 + 10^2 + 1^2 +12^2}{2\times 1729} = 21/247 \approx 0.085$

Since $p_k$ is the probability that a face is never colored we have $p_k = (1-q)^k$, so we must solve for $\frac{1}{2} = (1-q)^k$ which yields a solution of 7.8. The integer value that gives the closest result to $\frac{1}{2}$ is $8$.