Friday, July 23, 2010

A Magic Trick

What aspect of Compressive Sensing or Group Testing is most magical or surprising ?

In the cards shown below, the magician asks a person in the audience to choose a number between 1 and 63 and ask her to keep it in her head. The magician then proceeds and asks the spectator which card holds that number. As soon as the six cards have been queried, the magician knows exactly what the initial number is. How does she do it ?


Answer on Monday. Have a good week-end!




If you think this blog provides a service, please support it by ordering through the Amazon - Nuit Blanche Reference Store

10 comments:

JackD said...

Well... this is perhaps the answer:

Each card corresponds to the knowledge of one bit of the hidden number in its binary coding. Taking the same representation as in the picture, each card contains information about the following bits

[1st] [4th] [3rd]
[5th] [6th] [2nd]

Knowing in which card the hidden number is provides therefore its value, e.g.,

[True ] [False] [True ]
[False] [True ] [True ]

gives the binary code 100111, that is, 1+2+4+32=39.

Jack

Igor said...

Laurent,

You are pretty close.

Igor.

Anonymous said...

order the cards as:
2^0(1,...),2^1(2,...),
2^2(4,...),2^3(8,...),
2^4(16,...),2^5(32,...).

IF the number is in first card,
thus it is 2^0=1;

IF the number is in first and second card,
thus it is 2^0+2^1=3;


IF the number is in first,second, and third card,
thus it is 2^0+2^1+2^2=7;

Igor said...

It's the same solution as Laurent's but it is still a little too complex. Is there any way to do this faster ?

Remember the magician is in front of a crowd, she can't do binary conversion on the fly without incurring a potential setback.

Igor.

Zainul said...

The trick for the magician is to query the cards in a specific order.

Let's assume the cards are numbered
[1] [2] [3]
[4] [5] [6]

Querying the fourth card tells you that the number is either in the first half (1-31) or the second half (32-63).

Querying the fifth card tells you which quadrant of the half you just picked, the number is in.

Querying the second card tells you which octant of that quadrant the card is in.

Querying the third card which sixteenth you are in.

Querying the sixth card leaves you with just two candidates and the first card tell you which one it is.

If I understand BCS correctly, this is how it works too.

Is this the right solution ?

Zainul.

PS: Querying the cards in this order might give the impression that the magician is asking questions in "random" order. This is, of course, the trick with CS too. The magician knows it is merely fake-random.

Igor said...

Zainul,

There is no need for a specific order.

Cheers,

Igor.

JackD said...

ok, I think I get it. Simply add the first cell of the cards containing the hidden number.

The right binary coding representation was also

[1st] [4th] [3rd]
[6th] [5th] [2nd]

Jack

Igor said...

Laurent/JackD,

You win !

Cheers,

Igor.

John A. Gates, Sr. said...

How was this an under determined system? I do not see its relationship to CS at all.

Igor said...

John,

This instance is not an underdetermined system. However, other aspects of it reminded me of CS, namely:
- There is a unique solution out of many.
- The "measurement" sequence is non-adaptive
- The reconstruction requires a non trivial operation (albeit a simple one)
- Each "measurements" are equally important (each cards gives out information in base 2 of the number.)

Ever since this entry, I have been wondering in the back of my mind about how a magic trick could make CS more obvious. AS I said in a latter entry, what stuns people in this trick is the non-adaptivity of the measurement sequence when a simple solution would be to perform an adaptive binary search.

CS does the same thing to people, one is generally not comfortable with the non-adaptive nature of the process in the first place.

I hope this clears the matter,

Cheers,

Igor.

Printfriendly