with no more than $n$ steps, the total number of heads equals the total number of tails?
up vote
3
down vote
favorite
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?
combinatorics number-theory
asked Oct 29 at 13:00
apple
68915
|
show 4 more comments
up vote
3
down vote
favorite
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?
combinatorics number-theory
asked Oct 29 at 13:00
apple
68915
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?
– Gerry Myerson
Nov 12 at 5:02
@GerryMyerson Yes, thank you. I will edit my post.
– apple
Nov 12 at 5:16
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
– Ross Millikan
Nov 12 at 5:59
1
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.
– Ross Millikan
Nov 12 at 6:05
1
@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...]
– antkam
Nov 13 at 18:45
|
show 4 more comments
up vote
3
down vote
favorite
up vote
3
down vote
favorite
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?
combinatorics number-theory
asked Oct 29 at 13:00
apple
68915
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?
combinatorics number-theory
combinatorics number-theory
asked Oct 29 at 13:00
apple
68915
asked Oct 29 at 13:00
apple
68915
edited Nov 12 at 6:01
asked Oct 29 at 13:00
apple
68915
asked Oct 29 at 13:00
apple
68915
asked Oct 29 at 13:00
apple
68915
68915
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?
– Gerry Myerson
Nov 12 at 5:02
@GerryMyerson Yes, thank you. I will edit my post.
– apple
Nov 12 at 5:16
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
– Ross Millikan
Nov 12 at 5:59
1
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.
– Ross Millikan
Nov 12 at 6:05
1
@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...]
– antkam
Nov 13 at 18:45
|
show 4 more comments
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?
– Gerry Myerson
Nov 12 at 5:02
@GerryMyerson Yes, thank you. I will edit my post.
– apple
Nov 12 at 5:16
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
– Ross Millikan
Nov 12 at 5:59
1
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.
– Ross Millikan
Nov 12 at 6:05
1
@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...]
– antkam
Nov 13 at 18:45
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?
– Gerry Myerson
Nov 12 at 5:02
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?
– Gerry Myerson
Nov 12 at 5:02
@GerryMyerson Yes, thank you. I will edit my post.
– apple
Nov 12 at 5:16
@GerryMyerson Yes, thank you. I will edit my post.
– apple
Nov 12 at 5:16
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
– Ross Millikan
Nov 12 at 5:59
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
– Ross Millikan
Nov 12 at 5:59
1
1
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.
– Ross Millikan
Nov 12 at 6:05
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.
– Ross Millikan
Nov 12 at 6:05
1
1
@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...]
– antkam
Nov 13 at 18:45
@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...]
– antkam
Nov 13 at 18:45
|
show 4 more comments
1 Answer
1
active
oldest
votes
up vote
2
down vote
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.
answered Nov 14 at 22:46
Ross Millikan
287k23195364
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.
– antkam
Nov 15 at 15:55
@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.
– Ross Millikan
Nov 16 at 0:55
add a comment |
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
2
down vote
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.
answered Nov 14 at 22:46
Ross Millikan
287k23195364
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.
– antkam
Nov 15 at 15:55
@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.
– Ross Millikan
Nov 16 at 0:55
add a comment |
up vote
2
down vote
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.
answered Nov 14 at 22:46
Ross Millikan
287k23195364
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.
– antkam
Nov 15 at 15:55
@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.
– Ross Millikan
Nov 16 at 0:55
add a comment |
up vote
2
down vote
up vote
2
down vote
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.
answered Nov 14 at 22:46
Ross Millikan
287k23195364
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.
answered Nov 14 at 22:46
Ross Millikan
287k23195364
edited Nov 16 at 0:54
answered Nov 14 at 22:46
Ross Millikan
287k23195364
answered Nov 14 at 22:46
Ross Millikan
287k23195364
answered Nov 14 at 22:46
Ross Millikan
287k23195364
287k23195364
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.
– antkam
Nov 15 at 15:55
@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.
– Ross Millikan
Nov 16 at 0:55
add a comment |
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.
– antkam
Nov 15 at 15:55
@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.
– Ross Millikan
Nov 16 at 0:55
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.
– antkam
Nov 15 at 15:55
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.
– antkam
Nov 15 at 15:55
@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.
– Ross Millikan
Nov 16 at 0:55
@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.
– Ross Millikan
Nov 16 at 0:55
add a comment |
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2976114%2fwith-no-more-than-n-steps-the-total-number-of-heads-equals-the-total-number-o%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
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?
– Gerry Myerson
Nov 12 at 5:02
@GerryMyerson Yes, thank you. I will edit my post.
– apple
Nov 12 at 5:16
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
– Ross Millikan
Nov 12 at 5:59
1
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.
– Ross Millikan
Nov 12 at 6:05
1
@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...]
– antkam
Nov 13 at 18:45