## FU. Arp and Bif Shake Hands

Arp and Bif are at a party; every guest shakes hands a different number of times — except Arp and Bif, who shake hands the same number times as one another.

How many times did Arp and Bif shake hands?

(Well, that’s not *quite* enough information, all you need to know is the exact number of guests — and it turns out that there are only two possibilities in any case.)

We also answer last weeks puzzle and ‘fess up about the cards in the dark problem.

## jyoak said,

May 26, 2009 at 1:21 pm

This comment really has little to do with actual podcast except that as I was listening to it on the way to work and visualizing the graphs involved, it triggered a memory of a game I used to play with my father when I was young. It was a lot of fun and has some pedagogical value in grounding an abstract notion of mathematical relationship. It also plays well on the back of restaurant place settings and is highly functional for keeping young children occupied. :-)

You start with three dots on a piece of paper. On your turn, you must draw a line starting at one dot and ending at any dot (including the possibility of it being the same one.) You then place a dot on the line you just drew. The only rules are that no dot may have more than three lines emerging from it and no line can cross any other line (or dot except in the sense that it terminates at one.)

The first person unable to make a legal move loses.

I haven’t thought about this game since I was about 10 until it popped into my head this morning, but it will be fun to think about it now. For instance, there is a strategy that can be employed by one side to ensure victory. Which side? The player that goes first or the one that goes second? How best can this strategy be described?

My knowledge of graph theory is pretty sparse, but one of the mathematicians around may be able to identify this in terms of theory. Who knows… it may even be a very classic example of something. My dad wasn’t above lifting such things to keep me occupied. :-)

## strauss said,

May 26, 2009 at 5:09 pm

This game is “Sprouts“, created around 1967 by John H. Conway and Michael S. Paterson. Conway once told me that one point of the game was that it would be hard to program up a computer to analyze positions — the topology of the graph in the plane plays such a important role!

## Stephen Morris said,

June 3, 2009 at 12:08 pm

A very nice puzzle. This is my solution.

## Stephen Morris said,

June 5, 2009 at 2:56 pm

I realised there’s a much simpler way of describing my solution.

## Phil Ryan said,

July 10, 2009 at 11:14 pm

Here’s the way I thought of it, which doesn’t need to take into account odd or even. If we have n guests and A_n is the set of hand-shaking that goes on, then let Comp(A_n) be the complement of that set of handshaking. If A satisfies the requirements of the puzzle then so does Comp(A) (except that someone might not shake any hands. Here is the solution:

n=2 A_2 is Arp and Bip shake hands

then A_(n+1)=Comp(A_n) and the new person shakes everybodies hand

## Stephen Morris said,

July 12, 2009 at 10:29 am

That’s very neat. It does give the same solution as mine without having to discinguish between odd and even.

## Shawn said,

March 23, 2012 at 2:35 am

Oh no, iTunes refuses to download this particular episode. It streams just fine here, though. Strange.