Each ‘puzzle series’ post will be a few puzzles, which I have learned about watching videos, reading some random books, or I did come up with gathering ideas from here and there. By word ‘puzzle’, I informally mean a problem that can be stated easily and has at least one known solution which doesn’t involve fancy math. Usually I put couple of hours a week thinking about some of these puzzles and I really enjoy the process, and want to share this joy with you.
Puzzle #1. The Castle & The Princess
In this video, Matt Parker explains the puzzle clearly. He actively works for popularizing math and he has a good sense of humor. Later I learned that he actually does stand-up comedy.
If you wanna keep reading, let me rephrase the puzzle here.
So there is a princess in a castle with N bedrooms, aligned on a line, each of which has an entering door from outside the castle. Beginning at the bedroom/door 1 and ending at the bedroom/door N.
Each night princess sleeps in one of the bedrooms, and next night she changes the bedroom to a neighbor one. For example, if she slept at bedroom 1, next night she will definitely be in the bedroom 2, but the next night to that, she might either go back to 1 or go to 3.
Now you are a knight and want to get to the princess and at first you have no idea where she is sleeping. You only know she will move each night as described above. Each night you try one and only one door. Find an algorithm to find the princess, and calculate the maximum number of nights you need for that algorithm (worst case scenario). Trying with N = 2, 3, 4, 5, 6 will clarify the problem.
Puzzle #2. No 18-faced Convex Deltahedron
Show that there can be no convex deltahedron with 18 faces.
Hint: First realize that you can only have vertices where 4 or 5 triangles meet (positive curvature at a vertex). Then using Euler characteristic formula, calculate the number of edges, vertices, and find how many vertices has 4 and how many has 5 triangles meeting. Here comes the main part of the puzzle, show that it is not possible to fit this all together.
Puzzle #3. One String To Rule Them All
What is the minimum length of a string which has all the possible n-digit numbers from 00…0 to 99…9 in it, i.e. as its substrings. For example, ‘001209’, includes three-digit numbers 001, 012, 120, 209.
Use base two instead, if you want. And use Python (or any other) to write down this string for any n.