You're reading: Posts Tagged: exposition

Another black and white hats puzzle

A classic maths puzzle involves a line of one hundred prisoners, who have each been given a black or white hat by their nefarious captor, and must each correctly shout out the colour of their hat to win freedom. The twist is that the prisoners don’t know the colour of their own hat, and though they can see the colours of the hats in front of them, they don’t know many of each colour there are overall. They can confer on a strategy beforehand, and the aim is to get as many of them to correctly identify their hat colour as possible. You can find a full explanation here (and in many other places!)

There are several ‘sequels’ to this puzzle, some involving an infinite number of prisoners and requiring the axiom of choice to solve. This post is about a nice variation on the theme that I heard about at a recent MathsJam. It can (just about) be solved without knowledge of higher mathematics, and though it seems impossible at first glance, the prisoners in this situation can in fact save themselves with 100% certainty.

Using a zero-knowledge protocol to prove you can solve a sudoku

I’ve just uploaded to youtube a video I made with Katie Steckles to demonstrate why zero-knowledge protocols exist and how one works.

Katie is a habitual liar, so we followed the zero-knowledge protocol described in the paper, “Cryptographic and Physical Zero-Knowledge Proof Systems for Solutions of Sudoku Puzzles” which you can download from http://www.mit.edu/~rothblum/papers/sudoku.pdf

By following this protocol, Katie can prove that she isn’t lying to me about being able to solve the puzzle, without revealing anything about how she solved it.

The paper I mentioned, “How to explain zero-knowledge protocols to your children” is an excellent explanation of the ideas behind zero-knowledge proof.

Click here to continue reading Using a zero-knowledge protocol to prove you can solve a sudoku on cp’s mathem-o-blog

Fractal dimension in IKEA

A long time ago, I realised that IKEA’s shopfitters must be experts in fractal dimension – they manage to lay out their shop so that you have to walk past every single thing they’re selling. You can’t just nip into IKEA – you have to go through the whole hour-long “It’s A Small World” of affordably wobbly furniture even if all you want is some kitchen utensils from the bit at the end.

I’d been meaning to add something about this to the Maths in the City site but it required going in to IKEA and taking a picture of their floor plan for illustration.

Click here to continue reading Fractal dimension in IKEA on cp’s mathem-o-blog

Playing Games With Squares

Katie talks you through some of the interesting mathematical objects that can be made starting from an ordinary square.

Google+