Author 
Topic: Magician having 100 cards (Read 306 times) 

navdeep1771
Newbie
Let your thoughts go beyond your imagination
Gender:
Posts: 28


Magician having 100 cards
« on: Jan 23^{rd}, 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: 2872


Re: Magician having 100 cards
« Reply #1 on: Jan 23^{rd}, 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 xd. 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 23^{rd}, 2022, 12:18pm by rmsgrey » 
IP Logged 



rmsgrey
Uberpuzzler
Gender:
Posts: 2872


Re: Magician having 100 cards
« Reply #2 on: Jan 24^{th}, 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 xd must be in the 1100 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, yd 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 y1 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)+(y1) gives an ambiguous sum. So y1 must be in the pile with consecutive numbers. If x1 is in the range 1100, 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 x1 is in the same pile as y1, then x+(y1) = (x1)+y gives an ambiguous sum. So x1 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 y1 couldn't be in the same pile as x, but if it's in the same pile as y1, 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 299, and the other piles must be 1 and 100. 

« Last Edit: Jan 24^{th}, 2022, 5:30am by rmsgrey » 
IP Logged 



