Partitioning
You blindfolded and let into a room. The room has an infinitely many quarters scattered around on the floor. your friend tells you that that 20 of these quarters are tails and the rest are heads. He also says that if you can split the quarters into 2 piles where the number of tails is the same in both piles, then you win all of the quarters. You are allowed to move the quarters and to flip them over, but you can never tell what state a quarter is currently in (the blindfold prevents you from seeing, and you cannot tell by feeling it). How do you go about partitioning the quarters so that you can win all of them?Source: William Wu's puzzle forum
posted by Karthik Nagaraj at
3:39 PM
20 Comments:
Bobach writes:
I have a lot of trouble envisioning this problem. First, I can't imagine a room that can hold an infinite number of quarters - that must be some room! Then, I don't think I would live long enough to sift through an infinite number of quarters.
But, assuming you restate the problem that gets me past these issues, form the stacks of quarters all standing on edge. That way the same number of tails are in each pile - 0.
Bobach,
Lets make it simple for now atleast - instead of infinite number of quarters lets have a total of 100 quarters. But you are funny, LOL :) So does this get you anywhere to partition the 100 quarters to win?
quoing from the puzzle
- "if you can split the quarters into 2 piles where the number of tails is the same in both piles, then you win all of the quarters"
- also there are 100 quaters
make two piles of 50 quaters each. both piles will have 50 tails.
how can you guarantee that the # of tails in your split are evenly distributed. you are told that 20 of them are tails
The inherent property of the quarter will ensure this. Each quarter has a head and a tail.
The solution may sound silly but it's true.
Panda,
The question states that originally we had about 20 tails. So when you split into 2 groups of 50 each how can you ensure that 50 will be tails? I dont seem to understand what is meant by the inherent property of the coin that will eusure the equality in the number of tails? Maybe you need to explain a little bit more.
Bobach writes:
Karthik, panda makes the point that every quarter has a "heads" side and a "tails" side, so making 2 piles with an equal number of coins will assure that both have the same number of tails.
What I have learned about you is that you do not play word games in these puzzles. Indeed, these are logic problems.
I still don't know why my original solution, stack the quarters in two piles of equal numbers in such a way that all quarters are standing on their edges, does not solve the problem. Both piles would have 0 tails up.
Bobach, Yes you are right in saying that these are not "word" problems so they are perfectly logical. So let us examine Panda's case:
If you were to split the 100 coins into 50 each - what would happen if the original 20 tail sided coins go into the 50 coin pile and for whatever reason all the other coins are heads. We have unequal number of tails on either side. Probably Panda missed one pre-cursor to this - Initially just toss the coin to remove any element of the original setting - Now we have a 50-50 chance that it might be tails or heads, so now start the split. This might go somewhere but without eliminating the original tail-sided coins which you know for sure I don't know how if we just simply split the coins into 2 stacks the tails will be equal.
Let us look at your approach - believe me I lost this last line of your reply amidst the infinite joke you were making - You said just stand them up on the edge and you will have 0 tails on both sides. this has made me to think - this is more logical BUT what when you make a coin stand on the edge - what is the probability that it is a head or a tail? Any idea ? This is a claer case of an unfair coin that doesn't define the definite probability of either case that has to occur. Let me think about this more. Cool!
Bobach writes:
Think of the way quarters are in the plastic or paper rolls - all lined up in a cylinder. Set the rolls on the floor horizontally and all quarters are standing on their edge - none would be considered heads or tails. Since I assumed I could not enter the room with those quarter rolls, I would use the walls and my shoes to prop up the end quarters of the cylinders to make them stand on edge.
Interestingly, this is a problem that is significantly changed when you decided to give a finite number of coins. With an infinite number, flipping the coins would end with the same number of heads in each stack. However, once you make it finite (and do-able as I pointed out in my first response) the guarantee of an equal number of heads and tails is no longer appropriate, right?
If I only had 6 coins, they could come out (after the flip) as 4 heads and 2 tails and since we can't tell which is which (we're blindfolded) when we create 2 piles of 3 each, they may not have the same number of tails. This goes for any finite number.
That's why I tried to eliminate heads/tails completely.
We can still feel the quarter and figure out which is the head and which is the tail, though we are blindfolded.
But this somehow seems too simple a solution even to me...lol
Kavya, nice try - the problem tells that you cannot tell by feeling it. :)
ph4n745m35 says:
I would like to stick to the original idea of 'infinite' number of quarters.. this way we can say tht the room is already in a state where half the coins are tails and other half are heads after mixing thoroughly(remember there are infinite negative and infite positive numbers and we say tht 0 lies mid way => we have as many positive numbers as many negative ones) going by this primise.. if we can manage to mix all the coins, and split them into 2 piles, we have the reqd condition for me to be the richest man ever..
Well the problem states that 20 of these are tails. So how can you assume that at some point you will get half of them to be tails and the other half be heads. Also there is no way of knowing which is which so how can you split the coins to be heads or tails. the idea is how best you can partition these coins
The best way is to toss every coin again and the 1st coin goes in the first stack then the next coin goes in the second stack and the third one back in the first stack and so on... since you have infinitely many quarters as the stack becomes big enough you will have equal number of heads and equal number of tails in both the stacks....to earn infinite money its onna take you infinite time!!
this is because the probability p of getting a head or a tail when you toss is equal and 1/2. so if given infinite chancs the theory is that there will be as many heads as tails.
you MUST have a finite number ... using 20 T and 80 H to start with:
Split the coins into a pile of 20 and a pile of 80. In the pile of 80, there are some number t (0<=t<=20) of tails. This means there are 20-t tails in the pile of 20. Now, flip the pile of 20. There are now 20-(20-t) = t tails in the pile of 20, so there are t tails in both piles. The $25 is yours.
Sorry, thinking about it, it is still possible with infinite, though the logistics are silly ... just make one pile of 20, the other of the remaining infinite ... now, there are t tails in the infinite pile (actually, t=20 with probability 1 ...), 20-t in the 20 pile ... so flip the 20, you have 20-(20-t) = t tails in the 20.
Solution
* Take 20 coins from the infinte set.
* Flip all of them over.
* In the rest of the coins, there'll be 20-n tails, where n is the no. of tails that went into the 20 coins selected. Also, there'll be 20-n tails now after n tails have been flipped over.
Thus, the taken set of coins (after flipping) and the rest have the same no. of tails.
brilliant my boy... well done
Hey Ishan,
Brilliant! Yes if we choose 20 coins from the infinite set and flip them over there will be 20-n tails left in both the split piles.
By conjecture if the puzzle tells us if there are t number of tails in an infinite pile all we have to do is split the pile into t # of coins and flip them over and the remaining coins in other pile will have the same number of tails as in the first pile. So the number of tails to begin with is the key to the problem! Amazing!
BTW, even Steve got the answer right!
Subscribe to Post Comments [Atom]
<< Home