Rudolphogram #1

Find the smallest perfect square with exactly 2 zeroes, 2 ones, 2 twos, …, 2 nines.

The perfect square may not start with a zero.

This weeks bonus puzzle was suggested by new contributor ruudvanderham.

[ruud1]

JJ’s Gem 10: Farmer vs. pig

From Computing, 1970s [link]

Here is a puzzle that intrigued me for some considerable time many years ago.

A farmer at F sees a pig in the corner of a field at A.

Simultaneously, the pig sees the farmer and starts to run along the side of the field AB in the direction of B at constant speed.

The farmer gives chase and runs at twice the speed of the pig. However, his direction is such that he is always running directly towards the pig.

Can he ever catch the pig? And, if so, given that FA is 100 yards, how far from A is the pig when he is caught.

Thanks to Richard W for providing the original of this puzzle.

[jjsgem10]

Conway’s wizard puzzle

Last night I sat behind two wizards, A and B, on a bus. I heard this conversation:

A: I have a positive integer number of children, whose ages are positive integers. The product of their ages is my own age, and the sum of their ages is the number of this bus.

B (looking at the number of the bus): Perhaps if you told me your age and how many children you had, I could work out their ages?

A: No, you could not.

B: Aha! At last I know how old you are! (B had been trying to find A’s age for a long time).

What was the number of the bus?

This puzzle is attributed to John H. Conway (who died earlier this year), and is similar to a couple of puzzles we have already tackled. Although if it were to appear as an Enigma puzzle I’m sure the participants would be described as logicians, so that we know that they are making their deductions based on logic, not magic.

The Prisoner of Benda

I’ve recently been re-watching Futurama (the entire series is available to Amazon Prime subscribers).

In the episode “The Prisoner of Benda” (original air date: 19th August 2010) the Professor and Amy build a machine that allows them to swap minds (so Amy’s mind is in the Professor’s body, and the Professor’s mind is in Amy’s body). However when they try to switch their minds back they discover that the machine will not operate twice using the same pair of bodies. However the Professor (still in Amy’s body) suggests that they might be able to swap back using a third body as temporary storage space.

Bender volunteers and swaps his mind into Amy’s body (and so the Professor’s mind is swapped into Bender’s body). The Professor (in Bender’s body) realises that if the Bender and Professor bodies now swap minds (which is permitted), then the Professor’s mind ends up inside his own body, but Bender and Amy still have swapped minds and the Bender and Amy bodies have already used the machine, so they cannot use it to swap back. Amy (in the Professor’s body) then asks: “Is it possible to get everyone back to normal using four or more bodies”. The Professor (in Bender’s body) replies: “I’m not sure. I’m afraid we need to use … (dramatic pause) … math!”[s].

In the meantime, and for various sub-plot reasons, a fair amount of mind/body swapping goes on. The following is a complete list of the bodies involved in the swaps:

Amy ↔ Professor
Amy ↔ Bender
Leela ↔ Professor
Amy ↔ Washbucket
Fry ↔ Zoidberg
Emperor ↔ Washbucket
Hermes ↔ Leela

If we denote the body of B contains the mind of M as BM, then we can show the sequence of swaps as:

start: (AA) (PP)
A↔P: AP PA (BB)
A↔B: AB PA BP (LL)
L↔P: AB PL BP LA (WW)
A↔W: AW PL BP LA WB (FF) (ZZ)
F↔Z: AW PL BP LA WB FZ ZF (EE)
E↔W: AW PL BP LA WE FZ ZF EB (HH)
H↔L: AW PL BP LH WE FZ ZF EB HA

At this point in the story, two of the Harlem Globetrotters (Ethan “Bubblegum” Tate and “Sweet” Clyde Dixon) prove mathematically that no matter how many swaps have taken place, everyone can be returned to normal with the addition of two extra players (answering Amy’s question from earlier). And they proceed to perform thirteen swaps, using the Globetrotters as the extra players to restore everyone to normal.

This has become known as the Futurama Theorem, and is believed to be the first (and onliest) mathematical proof created specifically to further the plot of a TV show.

The proof is constructive, and operates as follows:

We can form the subjects into a collection of cycles where the minds need to follow the arrows to be restored. For example, the situation we have consists of two cycles:

FZ → ZF [→ FZ] (2-cycle)
AW → WE → EB → BP → PL → LH → HA [→ AW] (7-cycle)

With the addition of two extra players, X and Y, we can use them to transfer the minds along the cycles. We don’t need to know which combinations have already been used because we are going to use X or Y in every swap, and they have not been involved in any of the cycles.

So for the 2-cycle, we use X and Y to take the wrong minds from F and Z and replace them with the right minds:

start: FZ ZF | XX YY
F↔X: FX ZF | XZ YY
Y↔Z: FX ZY | XZ YF
F↔Y: FF ZY | XZ YX
X↔Z: FF ZZ | XY YX

X and Y end up swapped, but we don’t need to resolve them until the end. In sorting out the other players X and Y only ever interact with the other players and not each other, so they can always swap at the end (if necessary).

For the 7-cycle, we can use X to transfer the minds down the line until we get down to the final two, at which point we bring Y into play to avoid having to use the first two bodies again:

start: AW WE EB BP PL LH HA | XY YX
A↔X: AY WE EB BP PL LH HA | XW YX
W↔X: AY WW EB BP PL LH HA | XE YX
E↔X: AY WW EE BP PL LH HA | XB YX
B↔X: AY WW EE BB PL LH HA | XP YX
P↔X: AY WW EE BB PP LH HA | XL YX
L↔X: AY WW EE BB PP LL HA | XH YX
H↔Y: AY WW EE BB PP LL HX | XH YA
A↔Y: AA WW EE BB PP LL HX | XH YY
H↔X: AA WW EE BB PP LL HH | XX YY

And X and Y have ended up restored anyway, so we don’t need to sort them out.

So for any permutation we can break it into cycles and sort out the cycles individually using X and Y, and then swap X and Y at the end (if necessary).

The method uses (k + 2) swaps to resolve each k-cycle, and then maybe an extra 1 at the end to sort out X and Y (if required – which it is if there are an odd number of cycles).

So in this case we use 4 + 9 = 13 extra swaps and 2 extra people to resolve the situation.

The following questions remain to be answered:

(1) Could Amy, the Professor, Bender, Leela, Washbucket, Fry, Zoidberg, the Emperor and Hermes have got themselves restored to normal with fewer than 2 extra players? If so what is the minimum number of extra players required?

(2) Could they have got themselves back to normal in fewer than 13 extra swaps? If so what is the minimum number of swaps required?

[futurama]

Grid puzzle

I drew a 2×2 grid with the numbers 1-4 in it, odd numbers on the top row, even numbers on the bottom row, as below:

Starting at 1 and moving to adjacent squares (diagonal moves are allowed). There are 6 paths that visit all the squares in the grid:

(1, 2, 3, 4), (1, 2, 4, 3), (1, 3, 2, 4), (1, 3, 4, 2), (1, 4, 2, 3), (1, 4, 3, 2).

I then extended my grid to 2×8 grid, as shown:

How many paths are there on the new grid? (Each path must start at 1, and by moving to adjacent squares visit every square in the grid exactly once).

And how many paths are there on a 2×20 grid?

Pizza Puzzle

This puzzle is inspired by a combinatorial problem that surfaced in the Feedback section of New Scientist in early 2011. (See issues #2794 and  #2798), and was brought to my attention by Hugh Casement. [link]

Here is the puzzle:

When ordering a pizza from the Enigmatic Pizza Company you can specify the toppings on your pizza. There are 34 possible toppings to choose from, and you can have up to 11 toppings on your pizza. But you can have no more than three helpings of any individual topping.

The most basic pizza available would be one with no toppings at all. And a fully loaded veggie pizza might have 3 helpings of cherry tomatoes, 3 helpings of mixed peppers, 3 helpings of jalapeño peppers and 2 helpings of mozzarella cheese, using up all 11 toppings.

What is the total number of different pizza combinations that are available?

Singapore School Logic Puzzle

This puzzle has been getting a lot of attention recently, for example on the Guardian and BBC websites. It is quite similar to some of the Enigma puzzles published here.

Here it is slightly paraphrased to improve readability:

Albert and Bernard have just become friends with Cheryl, and they want to know when her birthday is.

Cheryl gives them a list of 10 possible dates, one of which is her birthday:

May 15, May 16, May 19,
June 17, June 18,
July 14, July 16,
August 14, August 15, August 17.

Cheryl then says she is going to tell the month of her birthday to Albert (but not to Bernard), and the day of her birthday to Bernard (but not to Albert). She does this.

The following conversation then took place:

Albert: I don’t know when Cheryl’s birthday is, but I know that Bernard does not know either.
Bernard: I didn’t know when Cheryl’s birthday is, but now I do.
Albert: Then I also know when Cheryl’s birthday is.

So, assuming they are all telling the truth and are all perfect logicians and have no further information, when is Cheryl’s birthday.