Coming to Agreement, a logic puzzle for Oxford admissions interviews

Let me dive right in with the main puzzle.

Main puzzle. You are a contestant on a game show, known for having perfectly logical contestants. There is another contestant, whom you’ve never met, but whom you can count on to be perfectly logical, just as logical as you are.

The game is cooperative, so either you will both win or both lose, together. Imagine the stakes are very high—perhaps life and death. You and your partner are separated from one another, in different rooms. The game proceeds in turns—round 1, round 2, round 3, as many as desired to implement your strategy.

On each round, each contestant may choose either to end the game and announce a color (any color) to the game host or to send a message (any kind of message) to their partner contestant, to be received before the next round. Messages are sent simultaneously, crossing in transit.

You win the game if on some round both players opt to end the game and announce a color to the host and furthermore they do so with exactly the same color. That is, you win if you both halt the game on the same round with the same color. lf only one player announces a color, or if both do but the colors don’t match, then the game is over, but you have lost.

Round 1 is about to begin. What do you do?

Before getting to solutions, I should also like to mention several variations of the puzzle.

Alternation variation. In this variation of the puzzle, the contestants alternate in their right to send messages—only contestant 1 can send on round 1, then contestant 2 on round 2 and so forth, but still they aim to announce the same color on a round. You are contestant 1—what do you do?

Collision variation. In this variation, players may opt on each round either to end the game and announce a color, to send a message, or to do nothing. But the new thing is that if both players opt to send a message, then the messages collide and are not delivered, although an error message is generated (so the players know what happened). What do you do?

Pigeon variation. This version is like the alternating turn variation, except that now the contestants are separated at much greater distance, and the messages are sent by carrier pigeon, so neither can be sure that the messages actually arrive. You are contestant 1—what do you do?

—————————–

Several of these puzzles are rather open-ended, not necessarily with a clear-cut objectively correct answer, although there are certain important issues that arise and that we had hoped the candidates would realize. So let me now discuss the puzzles in detail and the aspects of them that I find interesting.

For the main puzzle, it seems clear that one should not announce a color to the host straight away in round 1, because it seems not likely enough that the other contestant would also do so with exactly the same color. Rather, one should use the messaging capability somehow to agree on the color and round number on which to end the game. We should only announce, if we have both clearly expressed a plan to announce a specific color on a specific round.

At first, it might seem reasonable to send a message along the lines of “Let’s both announce red on round 3; please confirm in round 2.” The hope would be that the other player would indeed confirm on round 2, and then both would announce the final color of red on round 3.

That idea would work, if we were taking turns in sending messages, as in the alternation version of the puzzle. But in the main puzzle, the players are sending their messages simultaneously, and there is a difficulty for the previous proposal that can be realized by considering what kind of message we might expect to be receiving from our partner on round 1. Namely, perhaps they had a similar idea. It would be a lucky case indeed, if they had had exactly the same idea, also proposing to announce red in round 3. In that event, we would both confirm in round 2 and win with red in round 3.

But a more problematic case would occur if our partner had had a very similar idea, but happened to have made the proposal with a different color. Perhaps in round 1 our partner would have sent the message, “Let’s both announce blue on round 3; please confirm in round 2.” What shall we do then in round 2? If I decide to try to stick with my original red color, I might say, “Let’s use red in round 3”, then the other player might similarly decide to stick with blue, and we would still be at an impasse. Alternatively, if I decide to defer and switch to blue, perhaps they also defer and switch to red. What is clear is that we can’t be sure of confirming on the same color in round 2, and clearly we shouldn’t announce in round 3 with the color choice still unsettled. So the procedure we have discussed so far seems unsuitable.

A deeper contemplation of the problem reveals that this issue of the other contestant doing something very similar, but perhaps with a different color, is a fundamental obstacle to many solution attempts. There is a fundamental symmetry in play between the contestants. Since the messages are sent and received at the same time, and both players are equally logical, it could be that we both end up sending the same kind of message each time, except with different colors. We need somehow to agree on a color and a round number, but it seems that however we decide to make a proposal, it would be equally logical for our partner to make a similar proposal, but with colors permuted somehow.

We seem to need to break the symmetry somehow. Perhaps one might hope to use the alphabetically least color, amongst the two colors that have been proposed so far. That would seem to be a perfectly reasonable way to break the symmetry. But the problem here is that there are also many other perfectly reasonable ways to break the symmetry—the shortest wavelength color, the shorter color word, the color proposed by the younger person, by the older person, and so on. The difficulty is that any given proposal might be faced with a similar but equally reasonable proposal about how to break the symmetry. If I had proposed one such criterion, perhaps my partner proposes another, and we haven’t made any progress, but rather only replaced the difficulty of agreeing on the color with the difficulty of agreeing on the decision criterion of how to decide.

A key insight comes with the idea to use randomness. Suppose I had said in round 1, “I suggest we both announce red next round; I shall do so, if you also suggest this,” but you had said, “I suggest we both announce blue next round; I shall do so, if you also suggest this.” But I have got a coin in my pocket, and from now on, I intend each round to flip the coin, sending the red message on heads and the blue message on tails. If you do likewise, then we are very likely in a few rounds to hit upon the same message, and then we shall win on the next round by following through, announcing the agreed-upon color. That is, if in the first round we each happen to mention a color (whether or not my partner’s message was of the specific form I had mentioned), then I am going on every round to send a message as above, but using one of the two colors randomly. If you logically also choose to do this, then we are very likely to happen to choose the same color on some round eventually, and then win on the following round. This randomzing strategy thus seems fairly sound as a means to come to agreement, and if the partner also realizes this we should expect to win quickly, in just a few rounds with high likelihood. For this reason, I find this to be the best strategy.

A slightly more abstract way to describe the strategy I am proposing is that the symmetry between the players will need to be broken by us agreeing which of us will be leading the process and which of us will follow. I can flip a coin each round to decide if I should try to be leader or follower on that round. On heads, I shall propose a specific plan, “let’s say red next round, if your message indicates that you will follow my suggestion.” On tails, I shall send a message saying, “I am going to follow your plan of action, if you send one this round.” In this way, we are likely in a few rounds to have established a leader and follower, and win shortly afterward.

Some student candidates and commentators had proposed an interesting idea of trying to blend the two colors. This would be a way of coming to an agreement, but without needing to break the symmetry between the players. If I had proposed initially that we should announce red and you had proposed blue, then the idea is that logically we should both try to average these colors and say purple. I like this idea a lot, but it seems problematic in light of the fact that we don’t have such a clear and unambiguous means of combining colors. For example, should we mix the colors in the manner of mixing paint or rather in the manner of mixing colored light, which produces completely different results? Even when mixing red+blue, I might say purple and you might say violet. And what of stranger color combinations, such as orange+green? If we were using rgb colors, then some colors are simply adjacent in the color space (or an even distance away), and so they have no exact average mixing. Furthermore, why should we use rgb rather than cmyk or another color space system? And color mixing does not work identically for these two systems. For these reasons, I find the color mixing idea ultimately less than completely successful.

The alternation variation of the puzzle admits an easy solution, since the symmetry is broken already by the rules of the game. Player 1 will be the first to send a message, and can simply say, “I shall announce red on round 2; if you do so as well then we shall win.” There would be no reason for player 2 not to follow along, and so the players can expect to win on round 2.

Some candidates had suggested a confirmation round, having player 1 say, “let’s say red on round 3, confirm if that is agreeable.” Then both players would confirm the intention on round 2, and win on round 3. This is also successful, but it seems to me that the confirmation step is not strictly needed.

The collision variation is an interesting hybrid, because although there is a symmetry between the players in terms of how the rules apply to them, the symmetry is broken in the event that one sends a message and the other does not. The best solution here seems to be a random solution. Namely, flip a coin to decide whether to send a message or stay silent. On heads, send the message “Announce red on next round, if this message gets through.” On tails, do nothing, and plan to follow whatever is suggested on the message that might be received. Because of the randomness, it is very likely that in a few rounds a message gets through one way or the other, with a quick win straight afterward.

The pigeon variation is simply a version of the two-generals problem. The first player can try to propose a specific plan, naming a round and color, and ask for confirmation. But the confirmation itself will need to be confirmed, if the other player is to want certainty. But in this case the confirmation of the confirmation will need to be confirmed, and so on ad infinitum. No finite number of confirmations of receipt will be enough, even if all are received, since if $n$ confirmations suffice to attain mutual certainty, then the last confirmation needn’t be sent, since the protocol would work even if it didn’t arrive, and so $n-1$ should also suffice, a contradiction.

In the admissions interviews, which were generally less than 25 minutes, we were happy if a candidate got to the realization of the symmetry issue in the main puzzle, before going on to the alternating version, which most students got quickly, and then the collision version, where the randomness idea seemed to arise more naturally. The best candidates were then able to realize how to apply the randomness idea to the main version. With the pigeon version of the puzzle, successful candidates realized the need to achieve confirmation and confirmation of confirmation, and a few put this together to mount the impossibility argument for the case of certainty, and most realized how to increase the likelihood of success by picking a distant round and repeating messages. It was quite enjoyable for me to discuss these problems with so many very sharp student candidates.

Let me close by mentioning a few observations that surprised me about using the puzzles in an interview setting.

The first observation is the remarkable amount of personality that was revealed by the candidate’s choices in the puzzles. Some candidates tended to follow what might be called a leader’s approach (or the bully strategy?), attempting in the main puzzle to achieve agreement by conveying obstinateness in the color choice, to convince the other person to change sides as a way of coming to agreement. An equal number of other candidates tried instead to be deferential, sending messages that they would agree to use whichever color the other person wanted. Of course, each of these strategies works fine when paired with the other, but when paired with exactly the same personality, the methods face the symmetry problem we discussed earlier. Some brilliant candidates pointed out that the role that these personality differences played in the puzzle—it was very unlikely that the two contestants would be perfectly balanced in their personalities, and so the symmetry would be broken simply because one candidate would be slightly more insistent or slightly more deferential. And I have to say that realistically, this is how the puzzle would actually be solved in practice.

Another observation was that the candidates overwhelmingly chose red as their color, whenever they mentioned a specific color. About 2/3 or more did so. Far behind this was blue, in second place, and then we had a very small number of mentions of orange, green, yellow, and black.

I really enjoyed using this puzzle for the interviews, and I feel it helped us to choose a really great incoming class.

Art by Erin Carmody.

Quoted in New York magazine: The Chalk for Math Professors

The Chalk for Math Professors: Hagoromo Fulltouch, by Alex Ronan for the current issue of New York magazine, part of the Status Survey on various items for professionals.

The smooth texture flows so easily across the chalkboard like a fountain pen … One puts up mathematics on the chalkboard as if tracing out an idea in the air.

Meanwhile, I happened to be at a conference at the Research Institute for Mathematical Sciences in Kyoto last week, and I gave my talk using the chalkboard and the plentiful supply of Hagoromo chalk provided there.

Related MathOverflow post.

Moved to a new server, new WordPress installation

I’ve recently moved my site to a new server and apologize for the brief disruption in service. Many thanks to Sam Coskey and Peter Krautzberger for all the help with the move, and for all their help over the years with getting me started on WordPress at Boolesrings.  They really opened my eyes to the possibilities.

I am currently still fixing various technical issues with the new installation, but please post a comment if you see any issue that needs attention. My intention is that all links to jdh.hamkins.org will still work as before.

– Joel David Hamkins

Doubled, squared, cubed: a math game for kids or anyone

The number that must not be named

Doubled, squared, cubed is a great math game to play with kids or anyone interested in math.  It is a talking game, requiring no pieces or physical objects, played by a group of two or more people at almost any level of mathematical difficulty, while sitting, walking, boating or whatever.  We play it in our family (two kids, ages 7 and 11) when we are sitting around a table or when walking somewhere or when traveling by train.  I fondly recall playing the game with my brothers and sisters in my own childhood.

The game proceeds by first agreeing on an allowed number range.  For youngsters, perhaps one wants to allow the integers from 0 to 100, inclusive, but one will want to have negative numbers soon enough, and of course much more sophisticated play is possible. Eventually, one lessens or even abandons the restriction altogether. The first player offers a number, and each subsequent player in turn offers a mathematical operation, which is to be applied to the current number, which must not be mentioned explicitly.  The resulting number must be in the allowed number range.

The goal of the game is successfully to keep track of the number as it changes, and to offer an operation that makes sense with that number, while staying within the range of allowed numbers.  The point is to have some style, to offer an operation that proves that you know what the number is, without stating the number explicitly.  Perhaps your operation makes the new number a nice round number, or perhaps your operation can seldom be legally applied, and so applying it indicates that you know it is allowed to do so.  You must offer only operations that you yourself can compute, and which do not rely on hidden information (for example, “times the number of grapes I ate at breakfast” is not really permissible).

A losing move is one that doesn’t make sense or that results in a number outside the allowed range. In this case, the game can continue without that person, and the last person left wins.  It is not allowed to offer an operation that can always be applied, such as “times zero” or “minus itself“, or which can always be applied immediately after the previous operation, such as saying “times two” right after someone said, “cut in half”.  But in truth, the main point is to have some fun, rather than to win. Part of the game is surely simply to talk about new mathematical operations, and we usually take time out to discuss or explain any mathematical issue that may come up.  So this is an enjoyable way for the kids to encounter new mathematical ideas.

Let me simply illustrate a typical progression of the game, as it might be played in my family:

Hypatia: one

Barbara: doubled

Horatio: squared

Joel: cubed

Hypatia: plus 36

Barbara: square root

Horatio: divided by 5

Joel: times 50

Hypatia: minus 100

Barbara: times 6 billion

Horatio: plus 99

Joel: divided by 11

Hypatia: plus 1

Barbara: to the power of two

Horatio: minus 99

Joel: times itself 6 billion times

Hypatia: minus one

Barbara: divided by ten thousand

Horatio: plus 50

Joel: plus half of itself

Hypatia: plus 25

Barbara: minus 99

Horatio: cube root

Joel: next prime number above

Hypatia: ten’s complement

Barbara: second square number above

Horatio: reverse the digits

Joel: plus 3 more than six squared

Hypatia: minus 100

and so on!

As the kids get older, we gradually incorporate more sophisticated elements into the game, and take a little time out to explain to young Hypatia, for example, what it means to cube a number, to take a number to the power two, or what a prime number is.  I remember playing the game with my math-savvy siblings when I was a kid, and the running number was sometimes something like $\sqrt{29}$ or $2+3i$, and a correspondingly full range of numbers and operations. It is fine to let the youngest drop out after a while, and continue with the older kids with more sophisticated operations; the youngsters will rejoin in the next round.  In my childhood, we had a “challenge” rule, used when someone suspects that someone else doesn’t know the number: when challenged, the person should say the number; if incorrect, they are out, and otherwise the challenger is out.

Last weekend, I played the game with Horatio and Hypatia as we walked through Central Park to the Natural History Museum, and they conspired in whispering tones to mess me up, until finally I lost track of the number and they won…

A brief history of set theory…

A few months ago, Peter Doyle sent me a cryptic email, containing only the following photo and a subject line containing the title of this post.

I was mystified, until François Dorais subsequently explained that he had given a short presentation on recent progress in foundations for prospective graduate students at Dartmouth.

I’m glad to know that the upcoming generation will have an accurate historical perspective on these things!  🙂

The Myth of Just Do It

Barbara’s piece this week in the Philosopher’s Stone in New York Times:

OPINION   | June 09, 2013
The Myth of ‘Just Do It’
By BARBARA GAIL MONTERO

The idea that thinking interferes with doing is often taken for granted. But the realities at the highest levels of athletic and artistic performance are more complex.

→ go to The Myth of ‘Just Do It’

How well do you think this applies to expert action in mathematics? Go and post comments at the NYT…

Barbara was interviewed by Christie Nicholson at CBS News, Smart Planet, in the Pure Genius series:

CBS News, Smart Planet | June 28, 2013
Innovation / Pure Genius
Q&A: Barbara Montero, philosopher,
on the myth of ‘Just Do It’

Christie Nicholson interviews Barbara Gail Montero

There is a widely held view that thinking about one’s performance while performing ruins our ability to perform well. Many athletes say that once you’ve mastered the skill, one ought to let go of thinking and well, to quote Nike’s tag line, “Just do it.” Professional golfer Dave Hill said, “Golf is like sex. You can’t be thinking about the mechanics of the act while you are performing.”

I first heard that quote from Barbara Montero, associate professor of Philosophy at College of Staten Island and Graduate Center, City University of New York and author of a forthcoming book, Mind, Body, Movement: The Relevance of Consciousness to Expert Performance. (This is a working title, to be published by Oxford University Press.) Montero holds that thinking is not detrimental to successful expert performance. She describes the kind of thinking that might interfere but also the type of thinking that is actually necessary for an expert to improve upon his or her top performance.

SmartPlanet spoke with Montero, to hear more about the ‘just do it’ philosophy and why she feels it is misguided.

→ go to the interview

In memory, Clark John Hamkins (1930- 2013)

Clark John Hamkins at            Hoyerswort, 2005

My father, Clark John Hamkins (1930 – 2013) passed away May 11, 2013 at his home in Brunswick, Maine. He was a good man, witty, kind, intelligent, honest, hard-working, caring, curious, patient, philosophical, mathematical, practical, fair.  The world has just lost a great human being. He was a loving family man, married to my mother, Monica, for 55 years (their wedding anniversary was yesterday), with six children and thirteen grandchildren.

US Patent 3756058

He was an engineer’s engineer, one who could take apart any machine and put it back together and tell you all about the ways in which the design was flawed or how it was clever.  I think of his work as a kind of meta-engineering, for he designed the machines for manufacturing a product, bending pipes and twisting wire, rather than the product itself.   He held a number of patents for his inventions, including some for his design of a manufacturing apparatus for winding semi-toroidal transformers. When I was a kid, he designed and built in his wood shop a hand-crank centrifugal honey-extractor, which we used to harvest the crop from our bee hives.  He taught all his kids their way around a wood shop, how to cut, saw, nail, drill, screw, sand, bore, file, buff, solder, join, plane, dowel, glue, measure, how to use all manner of hand tools and the jig saw, the band saw, the table saw, the mitre saw, the drill press, the belt sander. He was beyond serious, with a lathe in his shop.  “Use the right tool for the job,” I can still hear him say, and “measure twice, cut once; measure once, cut twice,” a warning to those who would rush their work.  He made all manner of toys for his children and then for his grandchildren.  He made cabinets, tools, furniture, items of all kinds, large and small, fine and plain.  He kept and used a wood shop his entire adult life, insisting even in his final days that he go down into it.  One of his final projects was to design and build a beautiful, melodious whale-motif dulcimer.

He was an artist, and as a young man produced oil paintings, which move me to this day.  Long ago, before having kids, he made architectural drawings for the family home he had planned, and it is clear in retrospect that he hadn’t planned at that time on having such a large family.  (The joke in our family is that Dad wanted four kids and Mom wanted two, and they both got their wish!)  Later, he would inevitably win our family games of pictionary, where one is given the task to draw the meaning of a word selected randomly from the dictionary. His drawings always started with a clear simple line, capturing the essence of the concept, which was then fleshed out in fuller artistic flair until his partner said the word.  I found an old math book of his, from his own school days, with a chapter on Polar Coordinates in which he had drawn a wonderful Eskimo, carrying a harpoon and fish, and an igloo.

He was a teacher at heart.  He explained the slide rule to me when I was young, and gave a lesson on logarithms and log tables and the accompanying explanation of linear interpolation.  He explained to me as a child what $x^2$ and $x^3$ meant, and then, with a twinkle in his eye, as I listened wide-eyed and dumbstruck, about what $x^{2.3}$ meant.  Some of my fondest young memories with him include viewings of the moon and planets through a telescope, as I shivered in my pajamas in the cool night air, pondering the craters and drinking hot cocoa. He would discuss the various historical astronomical theories, comparing Copernicus with Ptolemy and the role of Tycho Brahe.  He loved a good scientific controversy, and liked even more to figure things out himself.  He liked to put a scientific explanation in a historical context.

He was a programmer, programming computers in the earliest days. I brought his cast-off computer cards, punched paper tapes and so on into my third-grade classroom for show-and-tell.  I remember him poring over expansive flowcharts spread across the kitchen table in the evenings. He made sure that his kids were learning how to program.

He was a voracious reader, consuming books in science, philosophy, literature, history, archeology, biology, physics, mathematics. You name it; he read it.

He was a skeptic.

He was a rebel physicist, refusing to accept the conclusion of the Michelson-Morley experiment on relativistic length foreshortening and time contraction.  And he backed up his beliefs by writing an account of this part of physics, re-developing the theory from an alternative perspective of his own invention, involving a notion of time translation, which avoided the need for those paradoxical conclusions, but ended up deriving the same fundamental equations.

I will miss him.

My younger brother Jon’s eulogy

Joining the Doctoral Faculty in Philosophy

I am recently informed that I shall be joining the Doctoral Faculty of the Philosophy Program at the CUNY Graduate Center, in addition to my current appointments in Mathematics and in Computer Science.  This means I shall now be able to teach graduate courses in philosophy at the Graduate Center and also to supervise Ph.D. dissertations in philosophy there.  I am pleased to become a part of the GC Philosophy Program, which is so highly ranked in the area of mathematical logic, and I look forward to making a positive contribution to the program.

Interviewed by Richard Marshall at 3:AM Magazine

I was recently interviewed by Richard Marshall at 3:AM Magazine, which was a lot of fun. You can see that his piece starts out, however, rather over-the-top…

playing infinite chess

Joel David Hamkins interviewed by Richard Marshall.

Joel David Hamkins is a maths/logic hipster, melting the logic/maths hive mind with ideas that stalk the same wild territory as Frege, Tarski, Godel, Turing and Cantor. He thinks we all can go there and that we all should. He gives tips about the Moebius strip to six year olds and plays around with his sons homework. He has discovered all sorts of wonders involving supertasks, infinite-time Turing machines, black-hole computations, the mathematics of the uncountable, the lost melody phenomenon of infintary computability (which really should be the name of a band), set theory and multiverses, infinite utilitarianism, and infinite chess. He’s also thinking about whether we really have an absolute notion of the finite and doubts if any of this is brain melting, which is just a testimony to his modesty. He also thinks that although maths is open to all he thinks mathematicians could use more metaphors and silly terminology to get their ideas across better than they do. All in all, this is the grooviest of the hard core maths/logic groovsters. Bodacious!

→ continue to the rest of the interview

The interview is now available at Marshall’s site 3:16, along with the full collection of his interviews.

The use and value of mathoverflow

François Dorais has created a discussion on the MathOverflow discussion site, How is mathoverflow useful for me? in which he is soliciting response from MO users.  Here is what I wrote there:

The principal draw of mathoverflow for me is the unending supply of extremely interesting mathematics, an eternal fountain of fascinating questions and answers. The mathematics here is simply compelling.

Mathoverflow has also taught me a lot about good mathematical exposition, both by the example of other’s high quality writing and by the immediate feedback we all get on our posts. This feedback reveals what kind of mathematical explanation is valued by the general mathematical community, in a direct way that one does not usually get so well when writing a paper or giving a conference talk. This kind of knowledge has helped me to improve my mathematical writing in general.

So, thanks very much mathoverflow! I am grateful.

The Logic Bike

In 2004 I was a Mercator Gastprofessor at Universität Münster, Institut für mathematische Logik  und Grundlagenforschung, where I was involved with interesting mathematics, particularly with Ralf Schindler and Gunter Fuchs, who is now at CUNY.

At that time, I had bought a bicycle, and celebrated Münster’s incredible bicycle culture, a city where the number of registered bicycles significantly exceeds the number of inhabitants.  I have long thought that Münster gets something fundamentally right about how to live in a city with bicycles, and the rest of the world should take note.  I am pleased to say that in recent years, New York City is becoming far more bicycle-friendly, although we don’t hold a candle to Münster.

At the end of my position, I donated the bicycle to the Logic Institute, where it has now become known as the Logic Bike, and where I have recently learned that over the years it has now been ridden by a large number of prominent set theorists; it must be one of the few bicycles in the world to have its own web page!