2
$\begingroup$

I'm working on project Euler 151 which goes as follows:

A printing shop runs 16 batches (jobs) every week and each batch requires a sheet of special colour-proofing paper of size A5.

Every Monday morning, the foreman opens a new envelope, containing a large sheet of the special paper with size A1.

He proceeds to cut it in half, thus getting two sheets of size A2. Then he cuts one of them in half to get two sheets of size A3 and so on until he obtains the A5-size sheet needed for the first batch of the week.

All the unused sheets are placed back in the envelope.

At the beginning of each subsequent batch, he takes from the envelope one sheet of paper at random. If it is of size A5, he uses it. If it is larger, he repeats the 'cut-in-half' procedure until he has what he needs and any remaining sheets are always placed back in the envelope.

Excluding the first and last batch of the week, find the expected number of times (during each week) that the foreman finds a single sheet of paper in the envelope.

Give your answer rounded to six decimal places using the format x.xxxxxx .

Now I know that Project Euler is old and there are answers readily available, but I'm not so much interested in the correct answer or how to find it, but rather in determining why my solution is incorrect.

Here was my reasoning: first of all the structure here is highly recursive, as is especially apparent when you consider the sheets as rooted trees, and the envelope as a forest. For convenience later on I reverse the labeling of sizes, considering A5 to be size $0$ and A1 to be size 4. Note that size in this case doesn't refer to the number of vertices, rather, a tree of size $n$ will have $2^n$ vertices. A tree of size $n>0$ will then consist of a root vertex connected to to the roots of $n$ smaller trees, one tree of size $k$ for every $k<n$. The process now involves removing the root from one of the trees in the forest, and our task is to determine the expected number of times (other than the first and last step) that the remaining forest consists of a single tree. If each vertex is considered unique based on it's position in the starting tree, let $a_n$ be the total number of ways the vertices can be removed if your starting tree is size $n$. Obviously $a_0=1$, and a stars-and-bars argument using the symmetry of the problem shows that it follows the recurrence $$a_{n+1}={a_n}^2{{2^{n+1}-1} \choose {2^n}}$$ Furthermore, for any $k<n$ a tree of size $n$ can be considered to be a tree of size $n-k$ whose vertices are all trees of size $k$, which gives rise to the more general recurrence $$a_n={2^n}!{a_{n-k} \over {2^{n-k}}!}\left(a_k \over 2^k!\right)^{2^{n-k}}$$

Now let $b_{n,k}$ be the number of ways to remove the vertices from an initial tree of size $n$ such that at some point your forest consists of a single tree of size $k$. Note that this can only happen once for any given $k$, so the expected value we are looking for is simply $$ \left(b_{4,1}+b_{4,2}+b_{4,3}\right)\over a_4$$

Now, the number of $k$-size subtrees in an $n$-size tree is $2^{n-k-1}$ and the number ways of removing its vertices are of course $a_k$. The remaining vertices form a tree of size $n-k-1$, one of whose vertices is a tree of size $k$, and the rest are trees of size $k+1$, so the number of ways to remove these vertices is $$\left(2^n-2^k\right)!{{a_{n-k-1}}\over 2^{n-k-1}!}{a_k \over 2^k!}\left({a_{k+1}\over2^{k+1}!}\right)^{2^{n-k-1}-1}$$Thus, for $0<k<n$, $$b_{n,k}={2^{n-k-1}}{a_k}{\left(2^n-2^k\right)!}{{{a_{n-k-1}}\over 2^{n-k-1}!}{a_k \over 2^k!}\left({a_{k+1}\over2^{k+1}!}\right)^{2^{n-k-1}-1}}$$$$={2^{n-k-1}}{a_k}{\left(2^n-2^k\right)!}{a_n \over {2^n!}}{{a_k} \over {a_{k+1}}}{2^{k+1}!\over2^k!} $$$$={{a_k}^2\over a_{k+1}}{2^{n-k-1}}{a_n{2^{k+1}!}{\left(2^n-2^k\right)!} \over {{2^n!}2^k!}}$$$$={{2^{n-k-1}}\over {{2^{k+1}-1}\choose 2^k}}{a_n{2^{k+1}!}{\left(2^n-2^k\right)!} \over {{2^n!}2^k!}}$$$$={{2^{n-k}}\over {{2^{k+1}}\choose 2^k}}{a_n{2^{k+1}!}{\left(2^n-2^k\right)!} \over {{2^n!}2^k!}}$$$$={2^{n-k}}{{a_n{2^k!}}{\left(2^n-2^k\right)!} \over {2^n!}}$$$$={{2^{n-k}{a_n}}\over{2^n \choose 2^k}}$$So our expected value should just be $${ \left(b_{4,1}+b_{4,2}+b_{4,3}\right)\over a_4}={2^3\over{2^4 \choose 2^1}}+{2^2\over{2^4 \choose 2^2}}+{2^1\over{2^4 \choose 2^3}}$$$$={8\over{16 \choose 2}}+{4\over{16 \choose 4}}+{2\over{16 \choose 8}}={1\over 15}+{1\over {5\times7\times13}}+{1\over{3\times11\times13\times15}}$$$$\approx 0.0690198690...$$ However, this is not accepted with standard rounding (to $0.069020$) or truncation (to $0.069019$). What am I doing wrong?

$\endgroup$
  • $\begingroup$ I'm not sure, but I think you aren't taking into account that the $A_5$ sheet that is used each time is discarded. Are you? $\endgroup$ – Jorge Fernández Hidalgo Aug 18 '16 at 3:23
  • $\begingroup$ Yes, I am. When a sheet larger than A5 is taken out, exactly one sheet of each smaller size is put back in (because with each cut, you make two sheets of the next smaller size, but use one of them). $\endgroup$ – Gabriel Burns Aug 18 '16 at 3:29
  • $\begingroup$ Oh, sorry, although something does seem really weird, the probability of picking an $A_5$ paper in the last batch should be $\frac{1}{2}$ right? $\endgroup$ – Jorge Fernández Hidalgo Aug 18 '16 at 3:31
  • $\begingroup$ Well, in the very last batch, it should be 1, Just as the probability of picking A1 in the first batch is 1,, but we're supposed to ignore those batches. The probability of picking A5 in the last batch being considered is not immediately obvious to me, as that's not how I chose to approach the problem, but I'll think about it... $\endgroup$ – Gabriel Burns Aug 18 '16 at 3:34
  • 1
    $\begingroup$ @CarryonSmiling No, now that I know what I did wrong, I'd rather take another crack at it myself. I know that Project Euler questions are usually intended to be solved with programs, but this one seemed at first blush like one I might be able to do with pencil and paper. I haven't given up on that yet, but if and when I do, I want to at least try to write my own program. $\endgroup$ – Gabriel Burns Aug 18 '16 at 4:16
2
$\begingroup$

Based on the clarifications in the comments, $a_n$ is the number of ways to choose the sequence of sheets drawn from the envelope, assuming that the sheets are distinguishable (even if the same size). For example, $a_2=3$ counts the following 3 possibilities:

  1. $\{A3\}\to\{A4,A5\}\to\{A4\}\to\{A5\}\to\{\}$
  2. $\{A3\}\to\{A4,A5\}\to\{A5,A5'\}\to\{A5\}\to\{\}$
  3. $\{A3\}\to\{A4,A5\}\to\{A5,A5'\}\to\{A5'\}\to\{\}$

However, these outcomes need not have equal probabilities. In this case outcome 1 has probability $\frac12$, while outcomes 2 and 3 each have probability $\frac14$. So we can't compute the expectation by counting outcomes and dividing by $a_n$.

$\endgroup$
  • $\begingroup$ Such a boneheaded error in retrospect. I think that when I started counting sequences, I intended to then go back and adjust for the various probabilities, but I got so caught up in trying to solve the counting problem, I forgot that I still needed to do that. $\endgroup$ – Gabriel Burns Aug 18 '16 at 4:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.