3
$\begingroup$

Two large opened boxes are marked as "class $1$". Each "class $1$" box contains two smaller boxes marked as "class $2$". Each "class $2$" box also contains two smaller boxes marked as "class $3$"$...$ In the end, each "class $n-1$" box contains two "class $n$" boxes. Each "class $n$" boxes contains a coin, head or tail. Each step we choose only one box, any class, and turn over every coin inside the box. If we have chosen the box, we must turn over every coin inside the box, no cheating. Prove that with no more than $n$ steps, we can have the total number of heads equals the total number of tails. ($n>2$)

My idea is that if the number of heads in the two "class $1$" boxes are the same, then we can choose one of the two and flip the coins inside that box to get the number of heads and tails equal. After that, I think I can use induction to prove the problem, but it seems hopeless. Are there any approach or solutions to the problem?

$\endgroup$
9
  • $\begingroup$ So "flip" doesn't mean, toss the coin in the air and see how it comes down; it means whatever the coin is showing now, turn it over so it shows the other side. Right? $\endgroup$
    – Gerry Myerson
    Commented Nov 12, 2018 at 5:02
  • $\begingroup$ @GerryMyerson Yes, thank you. I will edit my post. $\endgroup$
    – apple
    Commented Nov 12, 2018 at 5:16
  • $\begingroup$ Clearly you cannot for $n=1$ as there is only one coin. There are $2^{n-1}$ coins so you want to wind up with $2^{n-2}$ heads $\endgroup$
    – Ross Millikan
    Commented Nov 12, 2018 at 5:59
  • 1
    $\begingroup$ For small $n$ allowing $n$ flips seems generous. I can do it in one flip for $n=2,3$ and two flips for $n=4$. The only $n=4$ cases that require two flips are starting with one head or one tail. $\endgroup$
    – Ross Millikan
    Commented Nov 12, 2018 at 6:05
  • 1
    $\begingroup$ @RossMillikan - for $n=3$ there are: 2 class-1 boxes, 4 class-2 boxes, and 8 class-3 boxes (i.e. 8 coins). If the starting configuration is ((HH)(HH))((HH)(HT)), you would need 2 flips. Or am I misunderstanding something? [Note that the OP specifies TWO class-1 boxes...] $\endgroup$
    – antkam
    Commented Nov 13, 2018 at 18:45

1 Answer 1

Reset to default
2
$\begingroup$

Instead of considering the difference in heads and tails let us consider the number of heads. There are $2^{n}$ coins so our target is $2^{n-1}$ heads. Label each box by the change in the number of heads that will result from turning the box over. A class $n$ box with a head inside will be labeled $-1$ and a class $n$ box with a tail inside will be labeled $1$. Each lower class box will be labeled by the sum of the next level boxes inside it. A class $n-3$ box with five heads and three tails will be labeled $-2$.

I claim that we can find a box that reduces the error by at least a factor $2$. If we had $2^{n-2}+10$ heads we would have an error of $+10$ and would look for a box labeled $-5$ to $-15$ to turn over. The two class $1$ boxes have labels that sum to $-2$ times the error so if they are equal either one solves the problem in one flip. Given a box with a label too large, the only way neither of the boxes inside it has an acceptable label is if one is still too large and one too small (or of the wrong sign). We know that the level $n$ boxes will have labels that are too small unless the error is just $1$ or $2$, so somewhere we will have a box with an acceptable label. We just go down the tree following the labels that are too large until we find one that is acceptable.

Since the maximum error is $2^{n-1}$ we can get the desired number of heads in at most $n-1$ flips.

Added to patch the hole noted by antkam: suppose we have an excess of $k$ heads. WOLOG assume $k \gt 0$. I claim there will be at least one box labeled in the range $[-\frac k2,-\frac {3k}2]$ that will reduce the absolute value of the excess by at least a factor $2$. The two class $1$ boxes will have labels that add to $-2k$. If neither is in the range of our target, one of them will have a label less than $-\frac {3k}2$. We proceed down the tree, turning the box in our range if there is one, and otherwise taking the box less than $-\frac {3k}2$. If there is not a box in range there must be one less than $-\frac {3k}2$ because two numbers greater than $-\frac k2$ sum to a number greater than $-k$. As the class $n$ box has a label of $\pm 1$ we will always find a box in range.

$\endgroup$
2
  • $\begingroup$ Very nice approach but IMHO there is a hidden subtlety here: your proof claims that between the labels that are too large and the level $n$ boxes whose labels are too small, there must be a box whose label is in range. I think this is true, but IMHO the proof as written is not 100% rigorous. E.g. the claim implicitly relies on the fact that the tree is binary -- If the tree has a large fan-out then clearly this claim is false. $\endgroup$
    – antkam
    Commented Nov 15, 2018 at 15:55
  • $\begingroup$ @antkam: I said some more words to patch the hole. It looks to me like even a three branch tree would satisfy the requirement, but a four branch tree might not. $\endgroup$
    – Ross Millikan
    Commented Nov 16, 2018 at 0:55

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .