Comments on: FU. Arp and Bif Shake Hands

By: Shawn

Shawn — Fri, 23 Mar 2012 07:35:42 +0000

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

By: Stephen Morris

Stephen Morris — Sun, 12 Jul 2009 15:29:13 +0000

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

By: Phil Ryan

Phil Ryan — Sat, 11 Jul 2009 04:14:01 +0000

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

By: Stephen Morris

Stephen Morris — Fri, 05 Jun 2009 20:56:55 +0000

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]

By: Stephen Morris

Stephen Morris — Wed, 03 Jun 2009 18:08:14 +0000

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

5 Guests

1,2,2,3,4

3-4-1

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]

By: strauss

strauss — Tue, 26 May 2009 23:09:00 +0000

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...

By: jyoak

jyoak — Tue, 26 May 2009 19:21:44 +0000

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. :-)