Author |
Topic: k-card Magic trick redux (Read 1019 times) |
|
Hippo
Uberpuzzler
Gender: 
Posts: 919
|
 |
k-card Magic trick redux
« on: Jul 22nd, 2017, 12:03am » |
 Quote  Modify
|
Two magicans with perfect memory shows the following trick (with cards), but as we don't want messages hidden in cards rotation and their prevention by volunteers intervention, let us formulate the trick with numbers:
Volunteer choses k different integers from 1,...,n.
First magican dictates him sequence of k-1 different numbers from the chosen set. Volunteer writes them on the table from left to right. Then second magican says the last of the integers chosen by the volunteer. The second magican was in "isolated cell" till the numbers were written on the table.
Question is function n(k) giving maximal n for k such the trick could be done. Special case k=5.
There is the argument for the upper bound:
There are n!/((n-k)!k!) choices of the volunteer possible and first magican has n!/(n-(k-1))! possible signals in total.
Each signal must detect another choice so it must hold than n!/(n-(k-1))! n!/((n-k)!k!) leading to k!+k-1 n.
So n(1) 1, n(2)3, n(3)8, n(4)27, n(5)124.
Solution could be viewed as rectangular table with n!/((n-k)!k!) rows and n!/((n-(k-1))!k!) columns with zeros and nonzeros,
such that there is exactly one nonzero in each row and exactly (k-1)! nonzeros in each column (denoting which subset would be dictated and we have (k-1)! ordering to distinguish the rows). The constraint is nonzero in row whose index is given subset R of numbers must be in column whose index is subset of R.
Manually there was no problem to generate tables for n(1)=1, n(2)=3 and n(3)=8. I bet computer will find table for n(4)=27 and n(5)=124.
(The table size is 27*26*25=17550 rows and 27*26*25/6=2925 columns for n(4)=27
and 124*123*122*121=225150024 rows and 124*123*122*121/24=9381251 columns for n(5)=124 case)
Unless there is a nice system, this requires very good memory for magicans to remember the table.
Hmm for n(5) when using bits for table 1 representing nonzero and 0 zero, the table would have > 240TB size. So more compact representation must be used. ... 24 bits per row leads to < 0.63GB
So we are chosing column indices (subsets of row index) such that each index is chosen exactly(at most) (k-1)! times.
|
| « Last Edit: Jul 23rd, 2017, 5:10am by Hippo » |
 IP Logged |
|
|
|
Hippo
Uberpuzzler
Gender:
Posts: 919
|
|
Re: k-card Magic trick redux
« Reply #1 on: Jul 22nd, 2017, 4:25am » |
Quote Modify
|
Algorithm to fill the table:
Let Rgoal= row (rowFill-1)2 and Cgoal=col (colFill-(k-1)!)2.
We start with filling rows by randomly chosing one number x from the row set R and putting nonzero to column R\{x}. This makes Cgoal=0 and Rgoal0.
We have to show that whenever Cgoal>0 we could swap nonzeros in some rows to valid columns (so preserving Rgoal=0) what decreases Cgoal.
We would search for these swaps in the following way. We would maintain two sets of columns U and O. We would extend the sets while possible unless we found an improving "path". Let us start with U = columns with minFill=minimal number of nonzeros and O columns with maxFill=maximal number of nonzeros. We would construct subsets U' and O' of processed columns till U'=U and O'=O in which case our algorithm failed.
So whenever there is column u U\U' we process all rows indexed by column set with a number added.
Any row r containing zero in the column u has nonzero in another column c. If c is already in U do nothing.
If c contains minFill+1 nonzeros, make arrow from c to u and add c to U. If c contains more nonzeros, put 0 to the r,c and 1 to r,u and either u had minFill or now u has minFill+2 nonzeros and there is arrow form u to some u'. In the former case we are done and Cgoal was decreased by the performed swaps. In the latter case u u' defines row. Let us rename (u,c,r)=(u',u,(uu')) and repeat swapping (the arrows finally reach original set U what finishes the swapping). After processing u it is put to U'.
Similarly we can process oO\O' set, but in that case we would choose rows r contatining nonzeros in the column o. Each column c missing one number from the row set r is considered. If c is already in O do nothing, otherwise if c contains MaxFill-1 nonzeros, put it to O and create arrow from c to o.
Otherwise c has at most MaxFill-2 nonzeros and we could start swapping (similarly as in the U case).
After processing o it is put to O'.
When there exists xO U, there are two arrows from x. We could start two swapping processes on these arrows. That would finish by reducing Cgoal as well.
So question is could it happen that we finish with O=O' and U=U'?
|
| « Last Edit: Jul 22nd, 2017, 6:52am by Hippo » |
IP Logged |
|
|
|
dudiobugtron
Uberpuzzler
Posts: 735
|
|
Re: k-card Magic trick redux
« Reply #2 on: Jul 22nd, 2017, 4:39pm » |
Quote Modify
|
As an lower bound: Assume the 1st magician always leaves off the highest number. The other numbers have (k-1)! different ways they can be rearranged, and the 2nd magician has at most n-(k-1) different numbers to choose from (usually it will be fewer than this unless the volunteer's set includes the first k-1 numbers). Each different rearrangement must be able to represent a different number.
So then using this strategy, we know that n-(k-1) is at most (k-1)!
So n is at most (k-1)! + k-1 for this strategy.
For k = 5, n is at most 4! + 4 = 28.
Perhaps there is a better strategy available though which can allow a higher n.
I have not yet read your spoilered text so apologies if I am repeating something or making a redundant point.
|
|
IP Logged |
|
|
|
rmsgrey
Uberpuzzler
    
Gender:
Posts: 2873
|
|
Re: k-card Magic trick redux
« Reply #3 on: Jul 23rd, 2017, 3:57am » |
Quote Modify
|
on Jul 22nd, 2017, 4:39pm, dudiobugtron wrote:As an lower bound: Assume the 1st magician always leaves off the highest number. The other numbers have (k-1)! different ways they can be rearranged, and the 2nd magician has at most n-(k-1) different numbers to choose from (usually it will be fewer than this unless the volunteer's set includes the first k-1 numbers). Each different rearrangement must be able to represent a different number.
So then using this strategy, we know that n-(k-1) is at most (k-1)!
So n is at most (k-1)! + k-1 for this strategy.
For k = 5, n is at most 4! + 4 = 28.
Perhaps there is a better strategy available though which can allow a higher n.
I have not yet read your spoilered text so apologies if I am repeating something or making a redundant point. |
|
You can improve on that - treat the numbers as cyclic and always take the number before the largest gap. The second magician knows where to start counting from (because removing a number makes the largest gap larger) but will never need to cross more than half the gap. That gives you n=52 for k=5, letting you do the trick with a pack of playing cards.
There's an upper bound of k!+k-1 - the first magician has k! possible signals to send from his group of k numbers (k choices of number to keep; (k-1)! orders for the signal). If memory serves, the upper bound is reachable, though I forget how to do it (it may involve a large lookup table rather than anything smarter)
|
|
IP Logged |
|
|
|
Hippo
Uberpuzzler
Gender:
Posts: 919
|
|
Re: k-card Magic trick redux
« Reply #4 on: Jul 23rd, 2017, 5:03am » |
Quote Modify
|
on Jul 23rd, 2017, 3:57am, rmsgrey wrote:
treat the numbers as cyclic and always take the number before the largest gap. The second magician knows where to start counting from (because removing a number makes the largest gap larger) but will never need to cross more than half the gap. That gives you n=52 for k=5, letting you do the trick with a pack of playing cards.
|
|
I like this more than the solution in 5-card Magic trick thread.
We are guessing length of gap before the largest gap. Second last gap can be long at most 23 giving at most 24 options. (5+23+24)=52
This can be extended to 53 cards by
In the case of two gaps of size 24 touching each other avoiding to choose the element between the gaps. (Other elements before the gap of size 24 makes gap of size 25 what is fine) so in all cases we have to describe gap of length at most 23.
|
| « Last Edit: Jul 23rd, 2017, 12:13pm by Hippo » |
IP Logged |
|
|
|
Hippo
Uberpuzzler
Gender:
Posts: 919
|
|
Re: k-card Magic trick redux
« Reply #5 on: Jul 26th, 2017, 4:32am » |
Quote Modify
|
I have made some changes to the algorithm ... filling table deterministically (changing already filled rows when they prevent filling next row) so only Overfill version of the collision is taken into account and for k=4 it went fine ... giving 52650 bytes of "strategy table" (using 13 of each 24 bits).
Table for k=5 would be computed longer  .
After about 10 days of computation, 80% of the table is finished, but the conflicts slowed down the computation roughly 10 times ... table for upto 119 cards is almost finshed. So let us see how long the adding remaining 5 cards would take.
After next 2 days of computation the file got corrupted and instead 0,171 portion I have to recompute 0,768 portion of the file  ... and the determinism (repeatibility) is over. Using corrupted data as starting point helps so the computation at least seems faster now (0,264 to do after a day of recovery).
After next 5 days, I am back on 0,170 portion. I have speeded the algorithm a little bit (in not initialising all columns when solving conflict ... helps especially in already computed portion) and when solving conflict, I choose the least filled column instead of any what was in original code (as the result is not repeatable anyways).
After 5 more days 120 cards table is finished. ... 0,137 portion remains.
After next 9 days 121 cards table is almost finished (121,120,116,70,34) already reported ... 121 cards should be in about half an hour.
So 3 more cards and a lot of time to finish ... 0,117 portion). 121 cards done in about an hour... so 0,113 remains.
Estimate of the remaining time based by remaining portion divided by current progress speed ... seems is increasing in average. (Of course when given number of cards is finished, there is quick progress till free columns with new card are almost filled.)
... we are currently (after next 2 days) on 0.095 portion.
after next 13 days:
Oops my friends recomended me to look how much RAM my current notebook has. Times when one have to "swap" 2*10^11 * 9*10^9 table with one nonzero in each row to disk are over. So may be I would compute remaining 0.083 portion of the file in reasonable time.
After few minutes of codding and about an hour 122 cards are finished and I am on 0.063 portion remaining (it looks like about 100-1000 times speedup).
After next almost a day table for 123 cards was finished. So about 0.025 portion remains.
After 3 more days I am on 0.00428 portion (less than 1000000 rows remainig).
The algorithm can be viewed as finding perfect matching on graph of rows and (k-1)! copies of columns. So proving Halls Marriage condition for the graph would be sufficient to show the algorithm cannot fail.
After 8 more hours ... 665000 rows remain.
When trying to find small number of rows generating big number of columns, it seems all 5 card subsets of chosen set of cards is good attempt ... what gives exactly the x(x-1)(x-2)(x-3)(x-4)/5! rows and 4!*x(x-1)(x-2)(x-3)/4! columns so (x-4)<=5! is the required condition ... exactly matching our construction of k=5!+4. So we just need an argument that not using some row on already used cards cannot remove enough columns... and this would generate proof for k-card trick in general.
After 4 more days remaining portion is 0.00061, 136000 rows remaining ... floating average search for swap touches 3000000 columns (300000 parents in BFS) about 3 swaps are required in average.
Having 10 times more memory generating the graph would speed the computation. My implementation generates the rows/columns on the fly, what I expect consumes most of the computation time (as the calculation is repeated).
Maybe hash table as cache of last scaned rows/columns would speed the computation.
And after 4 more days the computation is successfully finished.
If anybody is interested, I can make "pages with the trick".
|
| « Last Edit: Sep 23rd, 2017, 4:30pm by Hippo » |
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print