FU. Arp and Bif Shake Hands

May 25, 2009 · The Mathcast · Permalink

«« FT. Sum and Double, Double and Sum· · · Morris: The Kate Bush Conjecture »»

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.

Standard Podcast [ 9:47 ] Play Now | Play in Popup | Download

7 Comments »

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!

It looks like the Wikipedia article is pretty good…
Stephen Morris said,

June 3, 2009 at 12:08 pm

A very nice puzzle. This is my solution.

I can’t make the spoiler tag work properly, maybe I post too much for the system to cope with. In any case don’t read this unless you want a spoiler.

[spoiler]Perhaps I’ve missed somthing but I think there is a unique solution for any particular number of guests.

I’m going to present each solution in two ways: first listing the number of handshakes of each guest in ascending order; second showing a diagram (until that becomes impractical). In the diagrams I represent each guest by their number of handshakes.

I’ll explain my reasoning after listing some solutions. Don’t worry there is a very simple way of generating these solutions.

2 Guests:

1, 1 1-1

Art and Bif are the only guests and they shake each other’s hand.

3 Guests:

1,1,2 1-2-1

4 Guests

1,2,2,3

2-3-1

|/

2

5 Guests

1,2,2,3,4

2

|\

3-4-1

|/

2

6 Guests

1,2,3,3,4,5

Now the diagrams get tricky.

2—

| |

–4 – 5 – 1

| | / |

| 3 |

| | |

–3—

7 Guests

1,2,3,3,4,5,6

8 Guests

1,2,3,4,4,5,6,7

That’s enough examples. So how do you generate these solutions?

Firstly the solutions for 2 and 3 guests are unique. It’s easy to check this by hand.

Given a solution for n guests it’s easy to generate a solution for n+2 guests. You add a guy who shakes everyone’s hand (GWSEH) and a guy who only shakes the hand of GWSEH. They will have handshake counts of n+1 and 1 respectively.

The handshake counts of the existing guests increase by 1. Since they start in the range 1…n-1 they will finish in the range 2…n.

Putting the old guests and the new guests together gives handshake counts in the range 1…n+1. So we have a solution for n+2 guests.

If you look at my examples each one (after 4 guests) is generated from the solution two places behind. So the solution for 4 guests is based on the solution for 2 guests and so on.

Clearly we can go on like this and generate solutions for any number of guests.

Why do I think that these solutions are unique?

The process is reversable. Given a solution with four or more guests I can remove the guy who shakes everyone’s hand and the guy who shakes one persons hand. Everyone left has their handshake count reduced by1. This gives a solution for two fewer guests.

Note that Art and Bif can never be the guy who shakes everyone’s hand. In that case the lowest handshake count would be 2, but we need it to be 1.

Neither can they both have a handshake count of 1. In that case they would only shake the hand of the guy who shakes everyones hand. But then the guy who shakes everyone’s hand but one wouldn’t have enough people to shake hands with.

QED or as they say in some parts, “job’s a good’un”[/spoiler]
Stephen Morris said,

June 5, 2009 at 2:56 pm

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

[spoiler]Suppose you want to find the solution for n guests. Depending on whether n is odd or even you have a different starting point.

If n is even you start with:

  Arp and Bif are first to the party. They shake hands. They both have a count of one. This is a solution for two guests.

If n is odd you start with:

  Arp, Bif and Clair are first to the party. Clair shakes hands with Arp and Bif. Clair has a count of two; Arp and Bif have counts of one. This is a solution for three guests.

Now you add groups in pairs until you have the required number.

  Two more guests arrive. They shake hands with each other. One of them shakes hands with everyone who was already at the party.

Just repeat this until you have the required number of guests.[/spoiler]
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.