Random People Numbers

So, a new puzzle that I was chatting about with Ben last night which has a slightly surprising solution in a simpler case:

Three people are assigned real numbers from (0,1), chosen uniformly at random. Each person knows their own number, but knows nothing about anybody elses number. You may ask a single yes/no question to the three people (one question, all three people will answer is at the same time). After that question, you must select which person has the largest number. What question maximizes your chance of success?

If you feel up to it, generalizing from three to N is the hard part. I'm still working on that.

Covering Problem

As promised, the follow up problem:

Find a connected arrangement of squares such that it is not possible to tile it with 2x1 dominoes, but if you increase the shape by adding a 2x1 shape to it, you can now tile the new shape with 2x1 dominoes.

Naturally, I mean 'tile' in the sense of the domino problem. Note that the solution to this problem requires a connected shape. I hope I don't need to define connected, I mean, I could, but its annoying.

Dominoes on a Board

Alright, time for a new puzzle. I have one I found recently I want to post, but some of the discussion first requires I post a puzzle I learned many years ago from my students in physics labs at UBC. It isn't a hard puzzle, which is why I never posted it, but the solution is very elegant, and it is one I like.

Consider an 8x8 chess board with two corner places deleted, in opposite corners. Attempt to tile this board with 2x1 dominoes. Prove or disprove whether such a tiling is possible.

Naturally such a tiling requires exactly (64-2)/2=31 dominoes to do this, as each domino will cover 2 squares and each square must be covered exactly once. Anyway, yeah, its not too tricky.

Josephus Problem

Ok, time for a new puzzle, I learned this one some time ago, it is a well known problem with a somewhat cool solution. This problem is well enough known as the "Josephus problem" that you can certainly just look it up along with its solution yourself if you hate my style of writing. The original problem involved N people who, having been captured by the enemy, are performing some sort of suicide pact, where they all kill eachother and there is one person standing at the end. There is a bunch of thematic bubble wrap to go with the puzzle, but I'm going to omit it just for the math. Anyway, here is the problem:

N individuals are in a circle, numbered 1 through N starting somewhere with 1 and increasing with each person to the left. Starting with person number 1, that person will kill the person to their left, and then the next person to the left will take a turn. This will continue until one person remains, which person is it?

Since that explanation is hard to do without an example, lets do one. Suppose N=5, then we start with 1 killing 2, 3 goes next, killing 4. 5 is next to take a turn, and 1 is to their left, so 1 dies and we only have 3 and 5 remaining. 3 goes next, killing 5 and the solution to the puzzle is 3.

So, in general, for an arbitrary N, who is the last person standing?

Knight Party

Oh right, I have a blog I'm supposed to maintain. All sorts of new puzzles these days, means I will proably forget them all before I manage to post them.

So, this is a knights and knaves puzzle, which I have in the past said I don't like, but I keep finding interesting ones (for those that don't recall, "knights" are people who always tell the truth, and "knaves" are people who always lie, not that that is actaully relevant for this puzzle, but it sets the tone a bit).

I got this puzzle from Presh Talwalkar's YouTube channel:

There is a party with 100 people, and each person is either a truth teller or a lair. At the party, some of the people may shake hands with eachother, and after the party you ask each person "How many truth tellers did you shake hands with?". The people each give a different answer, with each integer from 0 to 99 appearing as an answer.

How many truth tellers are at the party?

Naturaly, you can take it as given that if A shakes hands with B, then B also shook hands with A, you may also assume that nobody can shake hands with themselves. It is possible that everybody shook hands with everybody else, or simply that there were no handshakes, or anything in between of course. The solution is nothing special, but it is a nice logical solution.

Resistor Cube

Two posts in one month? Crazy. Anyway, I got a new puzzle, which I learned from the electromagnetism course I was teaching this term....well, sort of, I expanded a simpler puzzle into a surprisingly awesome one.

Consider a cube, whose edges are 1 Ohm resistors, what is the effective resistance between opposite corners of the cube?

Sad that its really a physics puzzle, I prefer doing more math when I can, but I'm not sure how to turn this puzzle into a fully mathematical one. Anyway, the real puzzle is to generalize that puzzle into N dimensions. So, have fun with that.

Numbers In A Room

Guess its time for a new puzzle, so I can claim to post at least once a month. This is one Ben showed me, but I am rewording it heavily from the original:

Walking through a building, you overhear a conversation two people are having in a room:
Person 1: I have written down a list of positive integers whose sum is the room number of this room.
Person 2: If you were to tell me how many numbers were on the list and their total product, would I be able to figure out what numbers were on the list, given that I already know the room number we are in?
Person 1: No, you would not.
Person 2: Alright, I now know the total product of the numbers.
What is the smallest room number they could be in?

The "theme" might be a bit thin, but it wasn't any better in the original, and at least this makes it clearer.

Magical Balloons

Alright, time to make a post so that I have at least managed to keep up 1 a year. I have a new puzzle Ben gave me ages ago, but I still haven't solved it and would feel wrong posting it when I have no ready solution. In the meantime, here is a puzzle I got from Tanya Khovanova's Math Blog:

You have 4 balloons (blue, red, green, and yellow, if you like) and some of them might be magical. You have a machine that you may put any number of balloons in and it will tell you how many balloons inside are magical. Find all the magical balloons using the machine not more than 3 times.

If you like you can also generalise, replace 4 with N and 3 with K, for which K can you solve the N balloon problem?

Box Stacking

New puzzle time I suppose, this is one that Ben told me, but it was pretty quick for me to solve since the correct approach uses some logic that I had been trying to use on that last puzzle:

There is a collection of boxes, and the boxes are coloured either red, green, or blue. You are going to be building a triangle of boxes, with a row of 10 on the bottom, 9 in the next row, 8 in the next row, and going all the way up to a single box on top. They are arranged in the sort of obvious triangle pattern, so that each box is on top of exactly two boxes below it.
The color of a box is chosen according to an algorithm, if two neighbouring boxes have the same colour, then the box on top of them is also that colour, if two neighbouring boxes are different colours, then the box on top of them is of the third colour.
Given the colours of the 10 boxes on the bottom row, is there a simple method to determine the colour of the box on top of the triangle?

"A simple method" essentially means one without having to actually go through the process of building the whole triangle.

Yeah, hopefully a simple one, but its sort of neat.

Hats Revisited

So, Ben has been quite a source of puzzles lately, but he gave me a really neat one the other day I just had to post.

There are 3 people in a room and they are each wearing a hat. The possible hat colours are red, green, and blue, and the standard hat rules will apply. The players must simultaneously write down a guess for their hat color, or write down "pass". The players win if somebody guesses right and nobody guess wrong, they lose if somebody guesses wrong or if everybody passes. Before the hats are assigned, they may strategise. Find a strategy that works more than 1/3 of the time.

Naturally 1/3 is trivial to reach by having Bob guess red and everybody else pass. Its a bit of a combination of two hat puzzles I have done before, but I never realised that the combination of these two puzzles is also interesting.

In The Line

Time for a new puzzle. I first found this one on the internets:

N people are standing in a lineup. There is a person at the front of the line (who is not one of the N) who can look down the line and see a given person if nobody taller than that person is in front of them. Each person in the line is of a unique height. What is the expected number of people that the person in front can see if each permutation of people is equally likely?

Just to make sure the wording is clear, with N=3, there are 6 cases (and assuming the line starts on the left and the person I name 1 is shortest and 3 is tallest):

123 -> three are visible
132 -> two are visible
213 -> two are visible
231 -> two are visible
312 -> one is visible
321 -> one is visible

So, on average, 11/6 people are visible in the N=3 case.

Robot Chasing

New puzzle time, because I actually have more than one in mind and I don't want to forget them.

I found this one somewhere random on the internets, I'll try to dig it up agian when I do the solution:

You are playing a game where you have to catch a robot. You and the robot are on an infinite 2-dimensional plane and you can see where the robot is. When the game starts the lights will be turned off and the robot will select a random direction and move in that direction at a constant speed. You may move around, and your top speed is some number which is greater than the robots constant speed (call them v_r and v_p for the robot speed and the player speed if you like). You naturally cannot see or hear the robot once the game begins. Find a strategy that guarantees you will find the robot.

So you must find a path (x(t), y(t)) which starts at a point (x₀, y₀) which never has a speed exceeding v_p and that path much intersect the robots path such that there is a t where they meet.

As a bonus problem, assume the game is played on a disc of radius R, with the robot starting in the center of the disc and the player on some point a distance P away from the robot. If the robot reaches the edge of the disc it escapes and the player loses. What is the smallest R for which your strategy works?

Guessing numbers

Time for a new puzzle, I found this one recently on the forums over at xkcd:

Alice comes up to Bob one day and says "I have selected a random number between 1 and 2000, and I will let you hand me a list of 1000 numbers, if my chosen number appears on your list I will give you a prize."

Bob wants to win the prize, but would like a better than 50% chance at it, so he asks "Alright, but may I ask you some yes/no questions about your number?"

Alice doesn't want to make this easy for Bob, so she replies "Ask as many questions as you like, but I am allowed to lie in giving my answers."

Bob says "Well, that isnt very helpful." He then thinks about it and realizes "Actually, as long as you promise never to lie more than nine consecutive times, I think I can do this."

Alice doesn't believe this is possible, and is willing to hand over the prize if Bob can actually come up with such a strategy, so she agrees "Very well, ask your questions, I will not tell more than nine consecutive lies."

What is a possible strategy for Bob that will guarantee that he can narrow down Alices number to no more than 1000 candidates?

So you may ask as many yes/no questions as you want, and in any string of ten consecutive questions, at least one of them will get a true answer.

There is one common false solution I will refute right here, asking the same question 10 times in a row won't work, Alice will just alternate "yes" and "no", and will not have told ten consecutive lies.

Not Not

Blogging sure slows down when my life is consumed with marking.

Anyway, heres a new one that was told to me by some people in the math room on KGS:

You have 3 boolean inputs, A, B, and C. You are to set up a circut that has 3 outputs, D, E, and F. You may use as many AND and OR gates as you like, but only 2 NOT gates. Arrange it so that D has the value of NOT A, E has the value of NOT B, and F has the value of NOT C, for arbitrary inputs of A, B, and C.

To put that into a bit more "math" and less "circutry"...give me expressions for NOT A, NOT B, and NOT C, if you can only use NOT twice. You may store variables and use them freely, but you may only call the NOT operator a total of 2 times. For example, you could define P = NOT (A OR B) and then use P as much as you like and that would only count as 1 use of a NOT gate.

For a more general version of the problem, you have 2n+1 inputs to negate, and only n+1 uses of NOT. The general version is fairly tough though, and not very fun.

Blind Maze

Puzzles? OK. So, this is one I found a little while ago on the xkcd forums:

There is a featureless maze that you must program a robot to navigate. The maze is an NxN square grid and each tile in the grid is either a floor or a wall. The robot may enter tiles that are floors but not ones that are walls. The robot can only be programmed a sequence of moves that can read only north, west, south, or east. The robot starts in the northwest corner of the maze and the exit tile is at the southeast corner of the maze. It is guaranteed that there is a path through the maze that the robot can navigate.

Upon entering the maze, the robot will follow your program. If a command would tell it to hit a wall, it will ignore that command and move on to the next command. If it lands on the exit tile, you win. If it hits the end of your commands without ever finding the exit, you lose.

Can you find a finite program that will guarantee that the robot will get to the exit at some point?

So, for clarity, your program can only read something like (East, East, South, South, West, South, South, East, East.....), just a chain of {North, South, East, West}, and must be finite in length.

For bonus points, try to make it so that the robot is guaranteed to end on the exit square rather than just getting there at some point. I haven't solved this harder version, and on the xkcd forums the best they had done (last I checked) was prove the existence of such a solution, and the proof was not something I 100% understood.

Balls In Jars

New puzzle time I suppose. I am going to put up a puzzle that I have been working on for about 2 years which I got from the Math Club room on KGS. Its possible that I spent alot of time overthinking the puzzle, but there was a very interesting diversion that I thought was a neat side puzzle that I will also post here. First, the main puzzle:

You have three jars that contain marbles. You are going to play a one-player game with these jars. On a turn, the legal move is to select two jars and move from the first jar to the second jar as many marbles as were in the second jar (naturally the "first jar" must be the one with more marbles). The goal is to set things up so that you can get one jar to be empty. Show that it is always possible, no matter how many marbles were in each of the three jars initially, to achieve the goal of getting an empty jar.

So, for example, you could start with (1,8,3) then move 1 marble from the second to the first, getting (2,7,3). Then move 2 marbles from the second to the first, getting (4,5,3). Next move 3 marbles from the second to the third, getting (4,2,6). Now move 4 marbles from the last to the first, getting (8,2,2). Finally move 2 marbles from the second to the last, getting (8,0,4) winning the game. I could have won that game more efficiently, but I wanted to just play around a bit to demonstrate the moves.

When I tried to solve the puzzle, I first tried to explore out the two-jar case, figuring that would help (it did not, by the way). In the end I saw a neat little result that I will also pose as a problem:

In the two jar version of the same problem, what is the complete list of initial situations (a,b) from which you can reach a winning position (q,0).

It is clear not all initial positions of the two-jar game can be solved, for example if you start with (8,2) you can only move to (6,4) and then to (2,8) and then to (4,6) and back to (8,2). However, (3,1) can be won, moving to (2,2) then to (4,0). You can see that there are no choices when playing this game, but from what initial setups can you win?

Coins Again

Alright, new puzzle time. I have a bit of a backlog of decent puzzles, so its important for me to waste them as soon as possible so I go back to not blogging again.

I got this one off of Tanya Khovanova's math blog, well, sort of, I misread the puzzle and solved a variant, but I think the variant is better so I'm going with it:

Athos, Porthos, and Aramis were rewarded with six coins: three gold and three silver. Athos got two coins. Athos doesn’t know what coins the others got, but he knows his own coins and he knows all the coins were given out. Ask him one question to which he can answer “Yes,” “No,” or “I do not know,” so that you will be able to figure out his coins.

My misread was that in the initial puzzle, instead of "Athos got two coins", it was "Each got two coins". My solution worked for both, and I somehow feel that my version is harder (being that you have less information), but its not clear that taking away information from Athos (which my variant also did) actually makes it harder.

Anyway, yeah, its simple, solve it out.

Breaking Chocolate

Alright, new puzzle time. I'm a bit surprised I hadn't posted this puzzle before, as I thought of it many years ago. Anyway, I sort of came up with it myself, but I may have had some influence from Carl Michal. Also, this game appears exactly in Winning Ways For Your Mathematical Plays, so I cannot claim that that book didn't give me inspiration. Anyway, on to the puzzle:

Consider a two player game in which the players take turns breaking up an NxM block of chocolate. On a players turn, they select one existing block of chololate and break it in a straight line along one of its break lines making two smaller blocks of chocolate. The players alternate turns, selecting a single block and breaking it into two smaller blocks. If on a players turn they have no legal moves (because there are only 1x1 blocks left), they lose. Determine the optimal strategy and who will be the winning player from a starting NxM position.

To clarify, a legal move is to select an available NxM block, then select a positive integer k less than N or a positive integer i less and M and turn that NxM block into either a (N-k)xM block plus a kxM block, or into a Nx(M-i) block plus a Nxi block. To give some examples, in the 1x1 case the first player loses (having no legal moves), and in the 1x2 case the first player wins (by making the only legal move).

A Silly Puzzle

New puzzle time? I am probably out of puzzles by this point, time to dig up the old bad ones from years ago. Actually, I also thought of a somewhat decent one, but I want to do this bad one first. I first heard this puzzle from Carl Michal:

There is a building with a lightbulb in it, and in the building next door there are three switches, one of which can turn the lightbulb on or off. You are in the building with the switches, and may manipulate them as you like, when you are done you may go to the building with the light bulb. You may not return to the bulding with the switches once you leave. You must determine which switch operates the light bulb.

The solution is somewhat silly, in that I mean to say that if you converted this problem into "math" then there is no solution (this isn't hard to prove). You can make use of the "reality" of the situation in your solution. The actual solution is quite reasonable, not actually bad at all, just not mathematical. It is a practical solution one could impliment and does not require anything unstated from the puzzle (such a calling a friend to come help, or being able to see the light from the next building over).

Flying Along

Ok, time for a new puzzle. I found this one a few months ago over at Tanya Khovanova's math blog:

You are sitting at the equator and you have three planes. You would like to fly around the equator. Each plane is full of gas and each has enough gas to take you half way around. Planes can transfer gas between themselves mid-air. You have friends, so that you can fly more than one plane at once. How do you fly around the equator?

Its sort of like an old puzzle involving camels going into the desert and you only have a finite amount of food for them, but a bit of a twist on this one. Anyway, thats it for now.