Newcastle MathsJam April 2012 Recap

2012-04-21

April’s MathsJam was very enjoyable. We did a bit of arts and crafts, a bit of playing games, and if it had been NBA Jam instead of Maths Jam I would have been entirely on fire because I used up all my IQ points solving some very fun puzzles. Durham were still on their Easter holidays so the attendance was a modest six people. That was just enough for everyone to be doing the same thing at the same time, so we had a good time.

Sprouts

Eamonn brought in the rules for Sprouts. He and Sarah played a few games and quickly realised that games can’t go on forever, so they set about trying to work out the perfect strategy.

Somebody asked what it means to “solve” a game, because I say that quite a lot. It means describing what happens when both players are playing perfectly, in particular which player wins.

I thought that Sprouts had been completely solved, but according to the wikipedia page and this paper it hasn’t! It also seems that the link between Sprouts and Nim isn’t as straightforward as I thought. Good job I didn’t mention it, then.

Matthew Taylor showed us something to do with integer partitions. I didn’t really understand how it worked, and he didn’t have a proof that it does what he says it does, so maybe he can explain it in the comments.

We answered Katie Steckles’ question about whether we considered ourselves mathematicians. She’s written a very interesting article based on the responses she received, which should be on the Aperiodical soon.

Hyperbolic spaaaaaaaace!

Prompted by last month’s discussion about games in hyperbolic space, I’ve been collecting all sorts of interesting hyperbolic things. I printed out some heptagons which we glued together to make a model of the ${7, 3}$ tiling of the hyperbolic plane.

I had also seen a video showing how to make the same model using buckyballs so we had a go at that as well. Steven seemed to be the only person capable of reliably making heptagons, but we got enough together in the end to make this small model. It doesn’t look like much in the photo but it was fantastic to hold and flexed in rather pleasant ways.

I tried to talk about how fibonacci trees have something to do with this tiling but I forgot most of the details. I think I managed to just about get across how every positive integer can be represented uniquely as a sum of non-adjacent fibonacci numbers, aka Zeckendorf’s theorem.

Matthew took the opportunity to make Nessie.

Wine tasters on a plane

We eventually got bored of playing with models of weird space and looked on twitter for some puzzles from the other MathsJams.

MAN: We’re attempting to prove @aPaulTaylor‘s claim that 219…978, with any number of 9s in the middle, reverses its digits when quadrupled.

— Maths Jam (@MathsJam) April 17, 2012

Click here for the proof. As usual, please try to have a think about it yourself before checking the solution, it’s much better that way.

Think about the numbers being carried forward when multiplying the number by $4$ . The $78$ bit gives $312$ , so the $3$ is carried forward to the first $9$ digit.

$(4 \times 9) + 3 = 39$ , so each 9 digit produces $9$ with another $3$ carried forward. Because the same number is carried forward at each $9$ digit, you can have as many as you like.

Finally, $(4 \times 21) + 3 = 87$ , so we’ve shown that $4 \times 219 \dots 978 = 879 \dots 912$ .

GLA: 1000 barrels of wine and 10 tasters.1 barrel is poisoned and kills the drinker in 30 days.Can you single out the bad barrel in 31 days?

— Maths Jam (@MathsJam) April 17, 2012

I’ll add another rule that Glasgow didn’t mention, but I think is needed for it to be an interesting puzzle: the poison kills a taster at some point on the 30th day after being drunk, not after an exact number of seconds. So you can’t get a single taster to drink from each barrel in turn and then use a stopwatch on the 30th day to work out which barrel killed him.

Click here for a hint

You might be thinking that the solution has something to do with the fact that $1000 = 10 \times 100$ . Instead, notice that since you want to find the bad barrel in 31 days, and it takes 30 days for the poison to take effect, the tasters only have two days to do their drinking. With that in mind, $1000$ is suspiciously close to $1024 = 2^{10}$ .

Click here to see the solution.

Number the barrels from $0$ to $999$ . Then each barrel’s number can be written down as a 10-digit binary string. Assign a digit to each taster.

On the first day, the $N^{th}$ taster drinks from each barrel whose $N^{th}$ digit is $0$ . On the second day, they drink from the barrels with a $1$ in that digit.

On the 31st day, all the tasters are dead. A tragic yet unavoidable consequence of our brilliant logic.

Each taster can tell you one digit of the binary number of the poisoned barrel: if it was $0$ , then they drank the poisoned wine on the first day and so died on the 30th. If it was $1$ , then they drank the poisoned wine on the second day and died on the 31st. So if the guy who was assigned the first digit died on the 30th day, then the first digit of the poisoned barrel’s number is $0$ . By applying that logic to each digit, we can work out the label of the poisoned barrel, and throw a heck of a wake for the dead tasters with the remaining safe wine.

I thought this problem came from twitter but I can’t find the originating tweet. Whoever brought it up, can you say in the comments where it came from?

100 passengers are waiting to get on a plane with 100 seats. The first dude gets on, but has forgotten which seat is his, so he picks a seat at random. The rest of the passengers board one by one. If their seat is free, they sit in it, otherwise they pick another free seat at random.

What is the probability that the last passenger sits in his assigned seat?

Click here for the solution, but give this one a proper thinking about first because it’s a good question.

Opinion was divided on this one. Some thought the probability was $\frac{1}{2}$ , while others thought it was $\frac{1}{100}$ .

Eamonn tried drawing probability trees and came up with an answer of $\frac{1}{100}$ , but he made a mistake with conditional probabilities. Joseph reduced the problem to a smaller number of passengers and tried writing out all possible seating arrangements, also deciding that the answer for the original puzzle is $\frac{1}{100}$ . He had missed that some arrangements can’t be produced by the passengers’ behaviour.

My solution took a while to formulate in precise words but is quite wonderfully concise: the first passenger comes in and either sits in his own seat, in which case everyone else sits in their own seat, or he sits in someone else’s seat. Everyone else files in until the guy whose seat the first passenger took boards the plane. You can then say that the usurped passenger agrees to swap seats with the first guy, who has forgotten which seat is his. So this new passenger is in the same position as the first one was, but with fewer available seats. That might be enough to convince you the answer’s $\frac{1}{2}$ , or you might think there’s some weirdness lurking somewhere, unacknowledged.

We can prove by induction on the number of seats that the probability the last passenger sits in his own seat is $\frac{1}{2}$ . Let $P (n)$ be the probability that the last passenger sits in his own seat in a plane with $n$ seats.

If there are two seats, the probability the last passenger sits in his own seat is $\frac{1}{2}$ , clearly. So $P (2) = \frac{1}{2}$ .

If there are $N$ seats, then the following are true:

with probability $\frac{1}{N}$ , the first passenger sits in his own seat and hence everyone else sits in the right seats.
with probability $\frac{1}{N}$ , the first passenger sits in the last passenger’s seat, so the last passenger has to sit somewhere else.
If the first passenger sits in seat $i$ , $2 \leq i < N$ , then the last passenger sits in his own seat with probability $P (i)$ .

So by summing up all those eventualities, we can get $P (N)$ ,

$P (N) = \frac{1}{N} \times 1 + \sum_{i = 2}^{N - 1} (\frac{1}{N} \times P (i)) + \frac{1}{N} \times 0.$

By using the inductive hypothesis that $P (i) = \frac{1}{2}$ for $2 \leq i < N$ , the previous equation means that

$\begin{aligned} P (N) & = \frac{1}{N} + (\frac{N - 2}{N}) \times \frac{1}{2} \\ = \frac{2 + N - 2}{2 N} \\ = \frac{1}{2} . \end{aligned}$

So for any number of seats greater than 1, the probability that the last passenger sits in his own seat is $\frac{1}{2}$ .

Finally, we played with some rolling cube puzzles from mathpuzzle.com.

The aim is to roll the cube so that you can read the word “Finish” the right way up. You can’t spin the cube on its face, and you can only roll the cube about green edges in contact with the table. They’re sort of like mazes in a bit of the symmetry group of the cube. I had to add some marks to distinguish the green edges because of how bad my eyes are at looking at colours.

That’s it for April’s MathsJam. I thoroughly enjoyed myself yet again and I think everyone else did too. If I’ve missed anything, please mention it in the comments, and I hope I’ll see you next month!

Comments

Andrew

2012-04-22 14:19:51

In Manchester, we did the wine-tasting puzzle without the second day of ponce-slaughter. We encoded bits by life or death rather than death on Monday or death on Tuesday.

I suppose you could argue you can’t use the second day as someone could die at 23:59:59 and you’d have to move really fast to keep up. Or use it to moveinto ternary – would that be likely to save any tasters?

Christian Perfect

2012-04-22 14:40:37

Oh yes of course, drinking the 1s is redundant.

I think the reaons you’re given the second day is because you can only say someone has survived a day once that day is over.