Puzzles With Handicap

Handicap_Sign

If you by any chance read about The Laser Gun puzzle you may have also watched the embedded video featuring the presenter Peter Winkler who is currently a professor in Mathematics and Computer Science at Dartmouth college.
Beside his regular occupation as a professor he is also a keen puzzlist, having published two books with some of his first couple of hundred (or so) favourite puzzles.

I purchased one of his books the other day from Amazon for 20 bucks.
It is called “Mathematical Puzzles: A Connoisseur’s Collection” and contains around 100 challenging puzzles.

As Peter points out puzzles and mathematics are not quite the same thing.
Although puzzles may be constructed based on mathematical principles, puzzles are for our amusement and makes no direct attempt at building theory or solving important problems. Puzzles are so often called puzzles because they are elegant, entertaining and exhibit some non-obvious mathematical truth without necessarily containing a lot of mathematical “meat”. On the other hand many of the problems in the book once existed as unsolved mathematical problems before someone found a sufficiently elegant solution for it to make it into the book, so puzzles can certainly originate from serious work.

I have only looked at a fraction of all the puzzles in the book, but I am already certain I will find many more excellent problems to write about as I get more time to work on them.

In this post I was planning to write about a few algorithmic problems that imposes some sort of handicap, like human memory constraints or communication of secrets in a non-private situation. These are the kind of problems you can tell your friends about at lunch and have a realistic chance at getting solved while “on your feet”.

I was personally able to complete the argument for the first two but was defeated by the last, although found it to be a very interesting problem to think about.
The solutions presented here describe my own thought process, so discussions may be a bit less concise and elegant than the intended solution you can find in the book (apologies in advance).

Problem 1 (Find The Missing Number):

All but one number between 1 and 100 is called out exactly once every 10 seconds in some arbitrary order.

How can you find the number which is missing if you have no aid (such as paper and pen)?

Solution:

Clearly if you have memory like an average person it is very difficult to memorize a set of 99 numbers.
Fortunately there is a better way!

Quite often when information is sent over a “noisy channel”, i.e a line of communication which may mess up or lose data, data integrity is verified using checksums (particularly if the data is numeric).

Checksums are useful because they can cheaply tell you if data has been compromised by comparing some short amalgamated representation of the received data with an expected checksum at the other end.
Conversely however if checksums match, it does not necessarily mean the data is uncompromised since two integrity failures may for instance “cancel out” to create a matching checksum.

In this problem we know precisely how “noisy” the channel is – it will not distort data but erase exactly one number.
Since there is exactly one number missing we may be able to design a checksum which after comparison can allow us to correct for the error.
This way we would only need to maintain one number, namely the checksum.

Quite clearly the most sensible option for the checksum is to take the plain sum of all numbers called out.
Since the missing number is one between 1 and 100 we know the checksums are going to differ by most 99.
We therefore don’t even need to maintain a very large sum.
We may equally well work (mod\;100) since this makes arithmetic mind calculations significantly faster and this is important since we only have 10 seconds between each number being announced.

The expected checksum is obtained by first summing all numbers between 1 and 100.
Most of you are probably familiar with the identity
\sum_{k = 1}^{n} k = \frac{n(n+1)}{2}.
If not, you can prove it by induction or solve the Difference Equation s_n = s_{n-1} + n.

The expected checksum is therefore \frac{100.101}{2} = 5050 \equiv 50\;(mod\;100).

Once all 99 numbers have been called out we are left with a checksum between 1 and 99.
The expected checksum is 50 so the missing number is given by the smallest positive integer congruent to 50 - checksum\;(mod\;100).

 

The next problem (slightly reworded from the book) relates to finding the majority vote using limited resources.
According to Peter Winkler this topic arose as a serious problem in computer science not too long ago.
Devising efficient online algorithms with limited resources (i.e algorithms dealing with streams of data) is a major area of research in compute science. Indeed a lot of data in the real world is available incrementally as opposed to being statically accessible offline.
This is an example of an online problem with a very elegant solution.

Problem 2 (Which Restaurant?):

Suppose you are organizing a large lunch takeaway (say for a whole department).

You would like to know which restaurant people would like to order from, so at the end of the large department meeting you stand at the exit and ask everyone which restaurant they prefer, one at a time as they pass.

Your boss thinks that a restaurant should only be selected if it receives a majority of the votes.
Otherwise he/she thinks you should select an arbitrary restaurant.

You have bad memory so you can only remember the name of one restaurant at a time.
At your disposal you also have a counter which can be incremented or decremented.

How can you figure out which restaurant, if any, received the majority of the votes (i.e more than half)?

Solution:

In this problem you have a long stream of information that is made available incrementally, and you have extremely small storage capacity.

It is clear that the last name you store in memory needs to be the majority restaurant, if there is one.

With the available resources there is really only one way to proceed, and that is to increment the counter if you hear the restaurant currently stored in memory and decrement it if you don’t.

The key observation is that once the counter has been decremented to zero, you replace the current name stored in memory with the name you just heard and increment the counter to one.
That way when the majority restaurant is in memory the counter is incremented more often than it is decremented.
Any other restaurant in memory is going to get decremented to zero since they are covered by decrementing votes for the majority restaurant alone.
You are therefore guaranteed to end up with the majority restaurant in memory by the end (if there is one), since it is the only restaurant that can survive with a positive count at the end.
If there is no majority then you end up with some arbitrary restaurant, but that is fine according to the problem statement as long as there is no majority.

Hence you choose the restaurant you last had in memory after everyone has had their say.

 

The final problem is a stunner and related to how two people who have never met can encrypt common knowledge into a secret over an insecure channel. Think about the implications of this for a moment!
Peter Winkler himself is actually the man behind this fact, and applied this knowledge to the game of bridge in his research. According to some author info I found on the web, his methods are currently illegal for tournament play in most of the western world.

Problem 3 (The Detectives):

Two detectives who have never spoken to each other are investigating a murder separately.

They both have the same list of eight suspects and through hard detective work they have both narrowed down the field to two suspects each.

They have now been told to talk to each other over the phone to compare information, and if their pairs overlap in exactly one suspect, identify the murderer and arrest him. If not then both detectives need to go back to work.

The complicating factor is that the mob has tapped the phone line and can hear everything that is being said in the conversation. They also know the list of eight suspects the detectives are talking about but are not aware of the two main suspects identified by each of the detectives.

If as a result of the conversation, the mob can determine with certainty who the common suspect is then they will kill off that suspect before he is arrested and get a chance to tell on the whole criminal organization.

What conversation can take place between the detectives so that they both know their common suspect if there is one, but the mob is still left in the dark?

Solution:

The obvious problem is that the detectives have never spoken before so somehow they need to manufacture their secret in public using the private information held by them both.

When I first read this problem, the first thing that came into my mind was whether this is any different from any old public-key encryption protocol like RSA or Diffie-Hellman.

Then I figured that the definition of secure depends on the context in which it is used.
Both RSA and Diffie-Hellman impose very difficult practical obstacles for breaking the encryption, like prime factorization of large integers. These schemes are not mathematically secure because given sufficient compute resources one can find trivial brute-force attacks on both protocols. Integer prime factorization is certainly not a mathematical impossibility. In fact it is always made possible by the Fundamental Theorem of Arithmetic.

Here we are looking for some mathematically secure way, in which anyone subscribing to the insecure channel, is unable to unlock the secret with certainty in any way logically conceivable.

Clearly if the first detective gives away both his suspects over the phone the second detective will know the answer but has no way of securely communicating it back, since now the mob has exactly the same information as the first detective, and hence can reach any conclusion made by that detective.

Somehow based on the private information held by both detectives they need to create some ambiguity for the mob.
After a couple of failed attempts of trying to construct certain ambiguity I decided to look up the answer in the book (hey, I couldn’t miss the football game…..excuses).

The intended solution went along these lines:

Since everyone has the same list they may agree to number the suspects from 1 to 8.

Suppose the detectives, let’s call them A and B, also agree to organize the possible pairs of suspects into below table as follows:

DetectivesTable

Let’s assume detective A holds the pair \{1,2\}.
Then detective A will tell detective B that his pair is in the first column.

Either detective B finds his own pair in the same column or he does not.
If he does, then he knows both pairs either coincide or are completely disjoint, since pairs in every column are disjoint. Either way there is no point in continuing the conversation so he may just say so.
If he doesn’t find his pair in the same column then either the pairs are disjoint or they intersect in exactly one suspect (if they intersect at all). The latter case needs to be communicated without the mob finding out.

Detective B may now look at the two pairs in the first column that contain either of his numbers.
If he has \{1,4\} for example, these pairs would be \{1,2\} and \{3,4\}.
Detective B would then split the eight numbers up into two pieces based on the two pairs as \{1,2,3,4\}, \{5,6,7,8\} and tell detective A that his pair is either in \{1,2,3,4\} or in \{5,6,7,8\}.

Detective A can now deduce that if their pairs intersect then detective B‘s pair must lie in \{1,2,3,4\}, since his own pair belong to that piece.
However the mob on the other hand only have the information that detective A‘s pair is in the first table column and that detective B‘s pair is in one of the two pieces.

Thus the detectives have constructed their own common secret since they can from now on refer to “The Piece” without the mob possibly knowing which piece they are talking about, \{1,2,3,4\} or \{5,6,7,8\}?

This is supposed to be the key idea.
Now they can keep on referring to “The Piece” and exploit this ambiguity to transfer other information.

Detective A can now respond and say to detective B that his pair is either \{1,2\} or \{5,6\}.

Since they both know which piece their pairs belong to (if they intersect), detective B now knows that detective A‘s pair must be \{1,2\}, whereas the mob is clueless because the conversation thus far would sound exactly the same to them if detective B was holding the pair \{5,6\}.

If detective B‘s pair does not intersect with \{1,2\} then there is no point continuing the conversation, so he might as well say their pairs are disjoint.

If detective B notices that their pairs intersect, say he holds the pair \{1,4\} then he tells detective A that his pair is either \{1,4\} or \{5,8\}.

Detective A now knows detective B‘s pair to be \{1,4\} since it is the only pair in the relevant piece, and again the mob cannot tell which.

Hence both detectives know which suspect they have in common without the mob knowing for certain.

 
 

Here are a couple of more puzzles from the book that I liked on similar theme:

Exercise 1 (Field Soliders – Easy):

An odd number of soldiers are stationed in a field, in such a way that all the pairwise distances are distinct.

Each soldier can only keep an eye on the nearest other soldier.

Prove that at least one soldier is not being watched.

 

Exercise 2 (Prisoners Problem – Intermediate):

Each of n prisoners will be sent alone into a certain room, infinitely often, but in some arbitrary order determined by their jailer.

The prisoners have a chance to confer in advance, but once the visits begin, their only means of communication will be via a light in the room which they can turn on or off.

Help them design a protocol which will ensure that some prisoner will eventually be able to deduce that everyone has visited the room.

Advertisements
This entry was posted in Algorithms, Uncategorized and tagged , , , , , , , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s