I have just read the card trick problem and I would like to share a note on it.
There's a solution for doing the same trick with 124 cards too. Actually both trick masters must learn an increadibly large table to be able to do that, but it's theoratically doable.
Actually if you can select N cards, then the trick can still be done if the deck is N! + N - 1 large.
Combination(N! + N - 1, N) = Variation(N! + N - 1, N - 1) * (N - 1)! and if you create a bipartite graph to represent the table, then all vertices will have N! edges attached. According to the Kőnig-Hall theorem there's always a full pairing in such a bigraph.
Monday, December 6, 2004
Just to show an example:
If you can select 2 cards from which 1 card will be passed over, then N is 2 and N! + N - 1 is 3 and here is the table:
0, 1 -> 0 -> tipp 1
0, 2 -> 2 -> tipp 0
1, 2 -> 1 -> tipp 2
If you can select 3 cards from which 2 cards will be passed over, then N is 3 and N! + N - 1 is 8 and the table is quite complicated, but it looks like this:
0, 1, 2 -> 0, 1 -> tipp 2
0, 1, 3 -> 0, 3 -> tipp 1
0, 1, 4 -> 1, 4 -> tipp 0
The table can be filled although it's not trivial even if you write a program for it.
Wednesday, December 8, 2004
Fog Creek Home