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

20 September 2009

Faith, God and all that jazz

Filed under: Christianity, Me — Tags: , , , , , , , , , , , — qwandor @ 11:10 pm

I have been meaning to write this post for quite some time now, a couple of months I guess, following a few conversations with a couple of people.

I guess I will start off with where I stand. I consider myself a Christian. Certainly I have all the obvious trappings: I go to church every Sunday, read the bible daily, go to a bible study with people from church most weeks, try to pray. I try to live my life, make decisions, from a Christian worldview. I try to be open to discussing my beliefs, ‘faith’ if you will, with others, as this is interesting, worthwhile and indeed a vital part of a Christian life (I Peter 3:15, Mark 16:15).

However, I do find it difficult to explain, and I think this largely comes down to not having a very clear idea in my own mind. On that note I would like to post a few questions, and list (my interpretations of) some people’s answers to them so far. I also include my own in some cases.

I would be interested to hear your thoughts (different answers to the questions, comments on the existing answers) and discuss further, either here or — better — in person. I have been particularly frustrated over these things over the last two or three months, and have found it difficult to talk to people, so this is an attempt to get some of my thoughts out in the hope of being able discuss them further. This is mainly aimed at Christians, but extends to anyone.

What is faith?

  • Blind belief, in the absence of evidence — obviously, I find this an unsatisfactory definition. There needs to be some way to discriminate between things in which you should have faith and things in which you should not.
  • Belief that something is a certain way, or that something will happen, based on past experience and testimony (direct or indirect) of people whom I trust. ‘Faith’ then is very closely related to ‘trust’, perhaps even the same thing. This is my current working definition, but some people I have talked to find it unsatisfactory. I do not really understand why; apparently it is insufficient in some way?

What is the basis of Christian faith?

  • The Bible — this requires first an argument for the historical accuracy of the bible, and then trust in the people whose witness is recorded in it (for example in the gospels). This is difficult due to the lack of a personal relationship, so it becomes a rather indirect thing.
  • Other people’s testimony — friends, family. Again this comes down to accepting what people say based on personal trust in them, which in turn comes from knowing them, observing their words and actions and judging their trustworthiness from that.
  • Supernatural experience — some sort of experience beyond the usual which provokes or confirms a belief in the God conceived by Christianity and described in the Bible. Some people certainly describe such an experience, to greater or lesser extent, or even it being a regular thing.

How does God talk to you?

  • The written word of the Bible is God talking to you — but, it is hardly personal then.
  • While reading the Bible — how?
  • Through other people — He sends people to say things to you, and so what they say is in a sense God talking to you. But then, how does He tell them what to say?
  • Just talking directly to you — again, how? What does this mean, how is it experienced?

How do you know that God is talking to you, and how do you know what He is saying?

  • You hear distinct words
  • It is more of a general feeling of some sort — but then how do you know that it is from God?
  • A ‘prompting’, you just think of doing something — but we often think of doing things. How is this ‘prompt’ different? ‘Prompting’ is a vague term. Perhaps this is the same as or similar to the previous answer.

What does it mean to ‘believe’?

  • A belief is a theorem (in the sense used in mathematics). That is, a statement is ‘believed’ if it there is a proof for it. I know that Peirce’s law holds in classical logic because I can write a proof using only the axioms of that logic, so I can say “I believe that Peirce’s law holds in classical logic”. Nothing can be believed beyond what can be proven, so belief is limited to the formalisms of mathematics. This does not include any of the sciences, as even physics is just a matter of attempting to find a consistent model which fits observed phenomena; no proof is possible as physical laws are only guesses which happen to match reality in a few observations.
  • A belief is a working assumption. I ‘believe’ that the sun will rise tomorrow insofar as I assume it will based on past experience, and so I base my decisions and plans on that assumption. Beliefs then are not certain, cannot be proven, but are necessary for decision-making and, well, life.

Note that the first and last questions are of definition, so it is more a matter of how you choose to define faith and belief than any intrinsic reality. Consistent and agreed-upon definitions are, however, vital to any meaningful communication.

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.

Blog at