Author |
Topic: Magician having 100 cards (Read 340 times) |
|
navdeep1771
Newbie
Let your thoughts go beyond your imagination
Gender: 
Posts: 28
|
 |
Magician having 100 cards
« on: Jan 23rd, 2022, 5:08am » |
 Quote  Modify
|
A magician has one hundred cards numbered 1 to 100. He puts them into three boxes, a red one, a white one and a blue one, so that each box contains at least one card.
A member of the audience selects two of the three boxes, chooses one card from each and announces the sum of the numbers on the chosen cards. Given this sum, the magician
identifies the box from which no card has been chosen.
How many ways are there to put all the cards into the boxes so that this trick always works? (Two ways are considered different if at least one card is put into a different box.)
|
|
 IP Logged |
|
|
|
rmsgrey
Uberpuzzler
   
Gender:
Posts: 2873
|
|
Re: Magician having 100 cards
« Reply #1 on: Jan 23rd, 2022, 12:01pm » |
Quote Modify
|
I make it six ways.
First, a trivial observation: any solution gives rise to five others - if you divide the cards into three piles, there are six ways of putting one pile into each box, and it will all work equally well, whichever of the six orders you use, so the number of solutions must be a multiple of six.
For the actual proof:
| hidden: |
Take some closest pair of numbers in one pile that contains at least two numbers, a and b. They differ by some difference, d so that b=a+d.
For some number, x, in another pile, both a+x and b+x have to point to the third pile, but b+x=(a+d)+x=a+(d+x), so x+d (if it's in the range 1 to 100) has to be in the same pile as x, and the same applies to x-d. The same logic repeats to say that every number that differs from x by a multiple of d has to be in that second pile, and the third pile has to contain all the numbers that differ by a multiple of d from some number y in that third pile. But you can take x and x+d in place of a and b, and apply the same reasoning yet again to the original pile too.
So to avoid being able to make the same total with one card from each pile of a pair for two different pairs of piles, each pile must contain all the numbers of the form c+kd, where c is some number in that pile, and k is any integer.
This means we're effectively working modulo d, since all the numbers that are the same modulo d must be in the same pile as each other.
Each pile must contain at least one set of numbers. What happens if a pile contains more than one different value modulo d? Then those two numbers differ by less than d, modulo d, so picking appropriate examples from the two sets of numbers, you can find a pair that differs by less than d, which would mean that you can use that smaller difference as a new d and go through the same logic to show you can work modulo that number instead. Since d was picked to be the smallest difference in a particular pile, and all piles must share the same smallest difference, you can't find a smaller d that will work.
Since allowing more than one value modulo d in the same pile leads to a contradiction, each pile cannot have more than one value modulo d, so must have exactly one value modulo d.
Since there are three piles (to go into three boxes), d=3, and the piles are all the cards with numbers equal to 1 (mod3), 2 (mod 3) and 0 (mod 3).
The last step is to check that this division works - which it does - each pair of piles will give a different value mod 3 when you add one card from each.
So there's a unique partition of the numbers 1 to n (for large enough n) into three piles, and six ways of assigning those three piles to the three boxes.
|
edit: on second thoughts you can also do a lot of other divisions into piles that will take more thought to figure out.
edit: third thoughts:
A total of twelve solutions
In addition to the above, you can: have one pile with 1 in, one with 100 in, and one with everything else - without the 100, you can't get above 1+99=100; without the 1, you can't get below 100+2=102, and with both, you get 100+1=101
|
| « Last Edit: Jan 23rd, 2022, 12:18pm by rmsgrey » |
IP Logged |
|
|
|
rmsgrey
Uberpuzzler
Gender:
Posts: 2873
|
|
Re: Magician having 100 cards
« Reply #2 on: Jan 24th, 2022, 3:25am » |
Quote Modify
|
I've spotted a hole in my "proof" - still figuring out how to patch it, if it's possible to patch.
edit: And I've figured out the patch:
The hole is that x+d could be in the same pile as a and b without creating an ambiguous sum - it's only if it's in the third pile that it creates problems
The patch:
| hidden: | The smallest gap between two numbers in the same pile must be no more than 3 - if you take four consecutive numbers, the largest gap between any two of them is 3, and by the pigeonhole principle, when they're divided among three piles, at least two of them must be in the same pile.
If that smallest gap is bigger than 1, then take a, b as before as the two numbers either side of one such gap, d the difference between them, and let x be some number between a and b. x must be in a second pile, otherwise it would be in the gap between a and b At least one of x+d and x-d must be in the 1-100 range - without loss of generality, assume x+d is. It cannot be in the third pile - suppose x+d is in the third pile, then a+(x+d) = (a+d)+x = b+x gives you the same sum from two different pairs of piles. If it's in the first pile, then the gap between b and x+d would be smaller than the gap between a and b, contradicting our definition of a and b. So x+d must be in the same pile as x, but then x and x+d can be used in place of a and b, with b in place of x, to repeat the same argument to show that b+d (if it's not over 100) must be in the first pile. Repeating the argument, alternating piles, lets you fill in the first pile with a+kd and the second with x+kd for any integer k that gives a number between 1 and 100.
The third pile must contain some number, call it y, and y must either be in one of the gaps of the first pile (in which case the exact same argument works) or it must be at one of the ends of the range. If it's at the bottom, y+d will be less than d away from the lowest number in the first pile; at the top, y-d will be close to the highest - either way, it can't be in the first pile without creating a smaller gap, nor the second pile without creating an ambiguous sum.
The rest of the proof runs as above - d must be 3, and the cards sorted modulo 3.
The only remaining case is where two consecutive numbers are in the same pile. If a second pile also contains consecutive numbers, then the third pile must contain a number, call it y, where y has at least one neighbour in a different pile - without loss of generality, assume y+1 is in a different pile. Since both other piles have consecutive numbers in, you can pick x and x+1 from the pile that doesn't contain y nor y+1 so that x+(y+1) and (x+1)+y give the same value from two different pairs of piles.
So at most one pile can contain consecutive numbers.
If there is a pile with consecutive numbers, then the other two piles contain at least one number each, let the smallest number in each be x and y respectively, with x<y. If y-1 is in the same pile as x, then you can pick consecutive numbers, a and a+1, from the pile with consecutive numbers, and a+y = (a+1)+(y-1) gives an ambiguous sum. So y-1 must be in the pile with consecutive numbers.
If x-1 is in the range 1-100, it cannot be in the same pile as x otherwise x wouldn't be the smallest in that pile, nor in the same pile as y since y is smallest in that pile and, by assumption, greater than x. But if x-1 is in the same pile as y-1, then x+(y-1) = (x-1)+y gives an ambiguous sum. So x-1 cannot be in any pile, so x=1.
If there are more numbers in the same pile as x, call one of them x', and consider x'-1. It can't be in the same pile because there are no consecutive pairs of numbers in that pile, and can't be in the same pile as y for the same reason y-1 couldn't be in the same pile as x, but if it's in the same pile as y-1, you again get an ambiguous sum, so that pile must only contain a single number, 1.
Due to the symmetry of the situation, a very similar argument shows that y=100 and must be the only number in its pile.
So if one pile contains consecutive numbers, it must be 2-99, and the other piles must be 1 and 100.
|
|
| « Last Edit: Jan 24th, 2022, 5:30am by rmsgrey » |
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print