Thoughts of a geek

15 August 2013

Dwarves and hats

Filed under: Maths — Tags: , , , — qwandor @ 6:44 am

Well! I have been meaning to post this for quite some time. Here, at last, are four puzzles involving dwarves and hats.

Puzzle 1, perhaps the easiest:
(I heard this one from Josh Baker when we went for a walk in Otari-Wilton’s Bush earlier this year.)

There are 4 dwarves. A goblin (who hates dwarfs, as all goblins do) has buried them in the ground up to their chins, such that they can see directly in front of themselves but not turn their heads. They are in a straight line, but with a tall wall between dwarves 3 and 4. All the dwarves are facing towards the wall, so dwarf 1 can see dwarves 2 and 3, dwarf 2 can see dwarf 3, and dwarves 3 and 4 can only see the wall. Their tormenter has also put a hat on each dwarf’s head, such that they cannot see their own hat.

He then tells them that he has given two of them red hats and two of them green hats, and that if any one of them calls out his own hat colour he will let them all go free. However, if any of them calls out the wrong hat colour, says anything else, or makes any noise or attempt to signal the others, he will leave them all buried to starve.

Assuming the goblin is telling the truth about the hats he has given them, and will keep his promise, what should the dwarves do?

Puzzle 2, along similar lines and also from Josh, but more difficult:
This time 5 dwarves are buried in the ground, but they are in a circle so that they can all see each other. Again, each has a coloured hat which he cannot see, but this time they can all see all hats but their own.

They are told that they have each been given a hat that is either red, yellow, green, cyan or blue. It may be that they all have different coloured hats, or it may be that some of them (or even all of them) have the same colour. This time they must all call out at once what colour hat they think they are wearing, and if any one of them gets eir colour right then they will all be set free. If they all get the wrong colour they will be left to die. What should they do in this case?

Puzzle number 3 came from Emily:
There are 100 dwarves in prison. They were probably falsely accused of their crimes; it is a hard life being a dwarf, and the justice system is all biased against them. Anyway, they have been in prison for a while, and their jailer is getting bored, so she decides to play a game with them. She takes them all into a room, which contains nothing but a single light hanging from the ceiling, and a lightswitch on the wall to turn it on and off, and explains the rules to them:

“Once you leave this room you will all be put in solitary confinement. I will then bring you back in one by one. When I bring you back you may choose to switch the light on or off, or to leave it as it is. You will then go back to your cell, and I will bring the next dwarf in. I will keep on doing this until one of you tells me that e is sure you have all been brought back at least once. If e is right, then I will let you all go free. If, on the other hand, e is wrong and not all of you have yet been brought back to this room, then I will hang you all. I will bring you in in whatever order I feel like, at whatever speed I feel like, and will keep on doing so until one of you says something. I will not touch the lightswitch.”

She then takes them each to their cells, and begins her game. They all have identical grey prison-issue hats.

a) Assuming that the jailer leaves the light on when they leave the room, so it is on when the first dwarf is brought back in, what should they do?

b) If the dwarves do not know whether the light will be on or off initially, what should they do?

Puzzle number 4 is from Christo’s blog (but do not look their until you have solved it, as there are spoilers):
100 dwarves are in a line, so each can only see the dwarf in front of em. Each is hatted in either magenta or brown. They are told that they must each call out their guess at their own hat colour, but they can do so in any order they choose. If any of them says anything other than a hat colour, speaks more than once, or tries to look around or gesticulate e will be immediately defenestrated. Once they have all made their guesses those who got the right colour will be freed, while those who guessed wrong will be defenestrated.

Dwarves like to work together, so what should they do to minimise defenestration?

Interestingly there at least two quite different approaches to this, so see if you can get them both.

Comment below if you want hints or clarification. If you think you have a solution please email me directly so as not to spoil the puzzles for other people, and I will post a comment to confirm you got it. Feel free to post how many dwarves you think can be saved for puzzle 4 though.

(And yes, for all their flaws, these dwarf-haters do like to use Spivak pronouns.)

[Edit 2013-08-15: Corrected typo in puzzle 2.)

18 February 2013

String colouring

Filed under: Maths — Tags: , — qwandor @ 8:08 am

One of my colleagues has an interesting combinatorial problem, perhaps the mathematically-minded among you might be interested to think trying to find a solution:

“I’m trying to work out the minimum size of a colouring of strings on a finite ordered alphabet, as follows.

Let Q be the set of integers from 1 to q, {1,…,q}

We consider all strings of length n on Q represented as path graphs with labelled edges:

Let G be the set of all qn path graphs consisting of n+1 nodes and n edges where there is an edge between node ni and ni+1 for each i = {1,…,n} and each edge is labelled with a integer from Q.

For any two nodes e and g on a graph in G, let max(e,g) be the highest label on the path between e and g.

Each node x in each graph in G is assigned a colour colour(x) from a set of colours C such that the following constraint holds:

For any pair of colours (a,b) from C, there is an integer f(a,b) in Q, such that whenever a and b appear on a graph in G, say colour(x) = a and colour(y) = b, then max(x,y) = f(a,b).

Question:

  • If q is constant, what is the minimum size of C?
  • What is the minimum number of colours I need to colour there graphs so that the maximum label between a pair of colours is always the same?

So far, I’ve manage to bound the minimum size of C between O(nq) and Ω(n logn). ie. O(nq) colours are sufficient but it can’t be done with fewer than Ω(n logn) colours.

Can you

  1. Show that there is a colouring of size O(n logn) or
  2. Come up with a higher lower bound? For example, show that a colouring has to be at least say 0.5n0.5q to respect this constraint

This problem has ratifications on unsolved problems in complexity theory related to the complexity of parity games and modal mu.”

Any thoughts? It has been far too long since I have done any real maths.

13 May 2008

Essay writing as graph traversal

Filed under: Maths, University — Tags: , , — qwandor @ 2:17 pm

As one of the assignments for COMP425 (Computational Logic) we have to write an essay about ‘logic and computation’. We were discussing this in class yesterday, and it was suggested that essay writing is essentially graph traversal (or perhaps flattening). I wonder how true this is.

3 July 2007

Fourier’s Song

Filed under: Humourous, Maths — qwandor @ 5:41 pm

This is brilliant: Fourier’s Song

Integrate your function times a complex exponential
It’s really not so hard you can do it with your pencil

It can be a little hard to make out what he is singing, so I suggest reading the words as you listen to the song.

Create a free website or blog at WordPress.com.