Fog Creek Software
Discussion Board




Card Trick

Hi,

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.

Regards,

levy

Levente Mészáros
Monday, December 06, 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
etc.

The table can be filled although it's not trivial even if you write a program for it.

levy

Levente Mészáros
Wednesday, December 08, 2004

*  Recent Topics

*  Fog Creek Home