One would be hard put to ﬁnd a set of whole numbers with a more fascinating history and more elegant properties surrounded by greater depths of mystery — and more totally useless — than the perfect numbers.
— Martin Gardner
There are countless ways to classify integers. Happy, perfect, friendly, sociable, abundant, extravagant, cute, interesting, frugal, deficient, hungry, undulating, weird, vampire… the list goes on. But how useful are such classifications, beyond their inherent interestingness, and as a hook to get people into number theory?
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.
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.
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.