Solutions: Don't step on the grass

See the original problem

The "Don't step on the grass" puzzle was something I saw once, but at first I couldn't find it.  It turns out it came from Wu : Riddles, under the header "Samwise and Gandalf".  It involves Samwise trying to dig up a telephone line being used by Lord Sauron.  My flavor text is much more banal in comparison.

I was surprised at the depth of this puzzle.  Not only was every initial solution I found wrong, but so was every second solution.  Here I'll show some of the suboptimal solutions.  (The final solutions will be hidden as spoilers.)  Below each solution is the length of fence, assuming that the polygon has unit sides.

My first solution was to have an X across the square.

Square: 2*sqrt(2) = 2.828

This of course suggested radially symmetric solutions.  So I looked for the best radially symmetric solutions for the pentagon and hexagon.  For the pentagon, this involved a tricky geometric construction which I show below (the circle crosses the center of the pentagon, and line segments are colinear with the centers of circles).

Hexagon: 6*sqrt(3)/2 = 5.196

Pentagon: 4.396

Commenter Secret Squirrel found better solutions, so I immediately realized that radial symmetry was a bad constraint.  I soon found the following solutions.

square: 1+sqrt(3) = 2.732

pentagon: 3.728
hexagon: 4.5

Finding that square solution was a breakthrough, because it made me realize the importance of 120 degree angles.  To make a physics analogy, it's like you have bubbles.  Bubbles shape themselves to minimize surface area.  If three bubbles are adjacent to each other, they'll form flat surfaces with 120 degree angles.  This led to an improvement in the pentagon solution.

Pentagon: 3.580

I also found another solution to the pentagon, which is not quite as good.  Also, commenter Rain found a solution for the square which was 2+1/sqrt(2).

Pentagon: 3.588

Square: 2+1/sqrt(2) = 2.707

Even though the above two solutions are excellent, they could still be improved with 120 degree angles.  The hexagon solution was the right idea, but could be improved with a little rearrangement.  Here are the final solutions:

Square: sqrt(2)+sqrt(6)/2 = 2.639

Pentagon: 3.544

Hexagon: 1+sqrt(3)*2 = 4.464

Draining a tank solution

See the original puzzle

You could just open all the walls, leaving only 10/9 gallons in the corner tank.  However, it's more efficient to drain it in three stages.

See spoiler image 

There are many variations on this solution, but they all leave 1/3 of a gallon.

Once you've seen this solution, finding the best solution for 16 tanks or 25 tanks is quick work--unless there's a more complicated solution that I haven't found.

Folding in thirds solution

See the original puzzle

This is one of those puzzles where the solution is very simple and easy to find, but only if you're looking at it the right way.

So here's what you do:
1. Fold the rectangle in half along a vertical line.  Unfold it.
2. Fold the rectangle along a diagonal.  Unfold it.
3. There's one last fold, shown in this diagram.  (The diagram shows a square, but this works for a rectangle of any dimensions.)  Unfold it again.
4. The diagram shows the intersection of two creases (made by steps 2 and 3).  Fold the bottom edge of the paper up to this intersection.  This is the one third fold.

No fault lines solution

See the original puzzle

Click to see spoiler images:
2x1 bricks solution
3x1 bricks solution

2x1 can be done with a 5x6 rectangle.  3x1 can be done with a 7x9 rectangle.  I'm fairly sure these are the best solutions (though they are not unique).  I do not think I could prove it.

Car parking game strategy

See the original puzzle

The Car Parking Game isn't really a "puzzle" in the usual sense.  It's a game.  But it's one of those games which is simple enough that it is feasible to analyze who is winning at any given time.  Given any game-state, either the current player can force a win, or the other player can force a win.  I will denote these game-states as W and L respectively.

W and L states have a particular structure:

1. If the current player cannot make a move, then it is a W state, since the rules say that the current player wins.
2. If the game is in a W state, and the current player can make a move, then it is possible for the current player to make a move leading to an L state.
3. If the game is in an L state, then the current player can only make moves which lead to W states.

If you know which game-states are W and which are L, then the strategy is simple: always make moves leading to L states.  The implied puzzle is: which game-states are W, and which are L?

There are several ways to figure it out.  One is to do it by hand.  Or you can do it with a computer.  I did it both ways.  But I'm not going to show you that.

I also solved the problem using the third method: research!

The most difficult part of researching this kind of problem is finding the right keyword.  The keyword is "Kayles".  Kayles is a game involving a row of bowling pins.  Each player can either knock down a single bowling pin, or knock down two adjacent bowling pins (if there is no gap between them).  Kayles is equivalent to the Car Parking Game, because you can either park your car efficiently, taking up one spot, or inefficiently, parking across two spots.

There are two versions of Kayles.  There is "normal play", where if the current player has no possible move, then the current player loses.  And then there is "misère play", where if the current player has no possible moves, then the current player wins.  In Normal Kayles, you can use a simple strategy, similar to that of the Coins on a Table Game.  From a mathematical standpoint, normal play is also easier to completely analyze than misère play, because we can apply the Sprague-Grundy theorem.

The Car Parking Game is equivalent to Misère Kayles.  I was pleased to find that Misère Kayles has been completely solved!  Unfortunately, the solution is very complicated, and will not fit in the margins of this blog.  If you are able to decrypt the paper, that's quite an accomplishment, and I welcome you to use it to beat me at the Car Parking Game.

Relatively prime graph solution

See the original problem

This is the solution I found:
N=105
M=6201

I tried searching for solutions for which N and M are odd.  That way I automatically get that 2 is a common factor of N+1, N-1, M+1, and M-1.

N needs to have a factor in common with M, M+1, and M-1.  Therefore, N needs at least 3 distinct prime factors.  N is odd, so the smallest N fitting this criteria is 3*5*7=105.

104 has prime factors 2 and 13.  106 has prime factors 2 and 53.  Therefore, M needs to have factors 13 and 53.  That is, M needs to be a multiple of 689.  The rest of my search consisted of trying different odd multiples of 689 until one worked.

There are many other methods to find a solution (and many other solutions), but that's mine.

Solution to Tower of Hanoi variant

See the original puzzle

Hint: The number of disks you can move increases exponentially as you add more rods.

Still give up?

It's relatively easy to simply show the steps when there are only five rods, but I want to generalize.  This requires some recursive algorithms.  Advanced puzzle solving ahead!

First, let's define a function G(N), which is the tallest tower we can move if there are N empty rods.  In the puzzle, I asked for the tallest tower we can move when there are five rods.  Four of those rods are empty, so I basically asked for the value of G(4).  I'll give it away right now, G(4) = 15.

But what happens if we have a tower with sixteen disks?  We can't simply move the top fifteen disks, and ignore the bottom one.  The bottom disk gets in the way, and can't be treated like an empty rod.  Therefore, I need to define another function F(N), which is the largest stack of disks we can move from an infinitely tall tower to an empty rod when there are N available empty rods.

Procedure 1: Moving F(N) disks from a big tower to an empty rod, when there are N available empty rods
If N=1, simply move one disk and you're done!
Otherwise...
1. Use Procedure 1 to move F(N-1) disks from the big tower to the first empty rod.
2. Use Procedure 1 to move F(N-2) disks from the big tower to the next empty rod.
3. Continue as above until we get to F(1)
4. Move one disk to the last empty rod.
5. Use Procedure 1 in reverse order to move F(1) disks from the second to last rod onto the last rod.
6. Use Procedure 1 in reverse order to move F(2) disks from the third to last rod onto the last rod.
7. Continue as above until we get to F(N-1).

This procedure allows you to move F(N) = 1 + F(1) + F(2) + ... F(N-1) disks.  F(N) is given by this recursive function, but we can also figure out an explicit formula.  F(N) = 2^(N-1).

Procedure 2: Moving a tower with G(N) disks to another rod, when there are N available empty rods.
1. Use Procedure 1 to move F(N) disks from the big tower to the first empty rod.
2. Use Procedure 1 to move F(N-1) disks from the big tower to the first empty rod.
3. Continue as above until we get to F(1).  By now we should have depleted the big tower of disks.
4. Reverse steps 1 through 3, only now we build the tower on the last rod instead of where it was before.

This procedure allows you to move G(N) = F(1) + F(2) + ... F(N) disks.  So G(N) = (2^N) - 1.

G(4) = 15
G(5) = 31
G(6) = 63
etc.

I am sure that this is the best you can do, but I will not provide a proof.

The ant and the universe

Because light in our universe has had a finite amount of time to travel, we can only see a finite part of our universe.  We call this the observable universe.  But did you know that, even though the age of the universe is 13.7 billion years, we can actually see further than 13.7 billion light-years?

According to Hubble's Law, distant galaxies are receding from us at a speed proportional to their distance.  In fact, beyond 13.8 billion light years away, objects are receding from us faster than light.  Did you know that the furthest objects we see are actually receding faster than light?

Believe it or not, these facts are easy to understand with only elementary knowledge of cosmology.

There is a classic puzzle involving an ant on a rubber band.  The ant tries to run from one end of the rubber band to the other, but every second we stretch the rubber band longer.  Will the ant ever reach the other side, or will it just get further and further from its destination as the rubber band stretches?

An ant comes across a rubber band... (Ant image from here)

The ant on the rubber band is a lot like the path of light through the expanding universe.  The ant crawls at a constant speed, but only relative to the rubber band.  As the rubber band stretches, the ant may become further from its destination.  Similarly, light travels at a constant speed.  But as space itself expands, light from far away galaxies may actually become further from us over time.

(Note that the far away galaxies aren't breaking any speed limit even if they recede faster than light.  They are receding because the space between us is expanding.  The relativistic speed limit only applies to the relative velocities of two objects at nearly the same location.  Analogously, we can say that even if we stretch the rubber band really fast, this doesn't mean the ant is breaking its own crawling-speed limit.  It just means the rubber band is stretching.)

So, will the ant make it or not?  It depends how quickly we stretch the rubber band.  If we were feeling devious, we could stretch the rubber band at exactly the right rate so that the ant is running in place, never getting any closer to its destination.  But let's consider a stretching rate which is a little more like our universe.  Suppose that the ant crawls one inch per second, and each second we stretch the total rubber band's length by one foot.

At first, the ant will gain an inch, and lose a foot.  But after the ant covers some distance, I waste a lot of effort stretching the part of the rubber band that is already behind the ant.  So eventually, the ant may catch up!  Indeed, we can show that it will catch up, if we consider the total fraction of rubber band that the ant covers each second.  In the first second, the ant covers 1/12 of the rubber band.  In the second second, it covers 1/12 * 1/2 of the rubber band (since now the rubber band has been stretched to twice its previous length.)  The next second, the ant covers 1/12 * 1/3.  And so forth.  We get a sequence like this:

The series in parentheses is known as the harmonic series.  The harmonic series can arbitrarily big, just by adding more terms (but it takes an exponentially large number of terms).  If we were to graph the ant's trajectory, it would look like this:

Note: I calculated this assuming continuous stretching, not by discrete stretching.  This is more true to cosmology.

So that's how the ant traverses the rubber band even though the rubber band was stretching faster than the ant could crawl.  Similarly, light can reach us from far away galaxies even if they're receding faster than light.

How far did the ant travel?  The ant is traveling an inch per second, and traveled for over 160,000 seconds.  Therefore, it traveled over 160,000 inches.  But there's another distance we can ask about: How far away is the point on the rubber band from which the ant started?  Because the opposite end of the rubber band moves at a foot per second, it must be over 160,000 feet away.

With light we can ask the same questions.  According to NASA, the furthest galaxy we know of is 13.2 billion light years away, by which they really mean that the light has traveled 13.2 billion light years to get to us.  But how far away is that galaxy now?  It is probably much further than 13.7 billion light years away, because it is receding from us very quickly.

But there are additional complications when we apply this to the universe.  As it turns out, the universe does not expand at a uniform rate, like our rubber band.  The two additional complications are matter and dark energy.  This will be explained in the next part.

Solution to coins on a table

See the original puzzle

The first player has the winning strategy.  The first move is to place right in the middle of the table.  After the second player places a quarter, the first player plays a quarter on the exact opposite side of the table.  The idea is to keep the arrangement of quarters perfectly symmetric about the center of the table.  No matter where the second player places a quarter, there will always be an empty spot on the exact opposite side of the table.  Eventually, the second player will have no place to put a quarter.

If you want a more serious version of this game (ie, one you could actually play, because the winning strategy is not at all obvious), you could try the "misère" version.  A misère game is simply a game where the win and lose conditions are switched around.  So to win the misère version, you must be unable to place a quarter during your turn.  As far as I know, there is no simple symmetry-based solution to the misère game.

Solution: ten rows of three

See the original problem

Image of solution

I had a book when I was much younger that had a handful of puzzles just like this.  Use X points to make Y rows of Z points each.  My blog has featured several variations of other puzzles that appeared in this book.  I rummaged through the house earlier and I found my copy!  100 Perceptual Puzzles.  I recommend it.

Rigged card game solutions

I am considering reducing the rate of puzzles on this blog.  I haven't been inspired to write many lately.

See the original puzzle

The three triplets are like rock paper and scissors.  If you pick the rock triplet, I'll pick the paper triplet.  If you pick paper, I'll pick scissors.  And so on.  The hard part is figuring out what card combinations will create the rock-paper-scissors structure.

Rock: 3, 4, 8
Paper: 1, 5, 9
Scissors: 2, 6, 7

If I pick the right one, then I have a 5/9 chance of beating you.

How did I get those numbers, you ask?  Each triplet contains a card from the set {1, 2, 3}, from {4, 5, 6}, and {7, 8, 9}.  If I pick a number from {1, 2, 3} and you pick one from {4, 5, 6}, then it's a lost cause for me.  But if we both pick one from the same set, notice that I will win 2/3 of the time.

Solution to the confused passenger

See the original puzzle

This puzzle can be solved by induction.  First consider the 2-passenger case, and then see what happens when we increment the number of passengers.  You will find that no matter how many passengers there are, there is always a 50% chance that the last passenger gets the correct seat.

However, there's another way to solve it.  Do like physicists do: ignore all details of the problem and just consider the symmetries.

Let's number all the passengers from 1 to 100 in the order that they board.  By the time passenger 100 boards, seats 2-99 are guaranteed to be filled.  Among the seats 1 and 100, exactly one is filled. But none of the passengers 1 to 99 make any distinction between seats 1 and 100.  (In other words, seats 1 and 100 are symmetric with respect to switching.)  Therefore, seat 1 and 100 are equally likely to be filled, each with a 50% chance.

The malicious passenger

1% of the time, the confused passenger sits in his own seat, which allows the final passenger to get the correct seat.  The other 99% of the time, the confused passenger acts exactly like the malicious passenger.  Therefore, we get the following equation:

0.5 = 0.01 * 1 + 0.99 * X

...where X is the probability that the final passenger gets the correct seat if the first passenger is malicious.

Solving for X, the probability is 49/99

Solution to the Tiger and the Lake

See the original puzzle

You can swim in two directions: the radial direction (towards the edge), and the tangential direction (around the center).  You need to swim in the radial direction to get out of the lake, but you also need to swim in the tangential direction in order to avoid the tiger.

The problem is, the further you get from the center of the lake, the less effective it is to swim in the tangential direction.  Near the center, you can just swim in little circles, and the tiger running around the edge of the lake will never be able to catch up.  But near the edge, the tiger can catch up.  At one fourth the radius of the lake, you can swim around the center just as fast as the tiger can run around the lake.

So here's the strategy.  Swim partly in the tangential direction and partly in the radial direction such that the tiger is always on the opposite side of the lake.  Eventually this spiral path should reach one fourth the radius, or at least very close.  And then you make a break directly for the edge of the lake.

It turns out you can reach the shore before the tiger catches up to you.  However, it turns out that you can't outrun the tiger after you reach the shore.  Also, in real life, tigers can swim.  So you can't really escape safely.

If you're curious what the spiral path looks like exactly, you're in luck!  This is exactly the kind of problem that physicists are good at solving.  It turns out that the correct spiral path is a semi-circle.  And you can actually reach one fourth the radius exactly.  See spoiler image

Solution to logicians with hats

See the original problem

As is always the case with these things, the best solution is to keep your colored hats in a safe place where logicians can't find them.  But let's play along with them for a moment.

Strategy

1. If the other two logicians have opposite-colored hats, then abstain.
2. If the other two logicians have the same-colored hat, guess the color not seen.

If all three hats are the same color, then all three logicians will guess incorrectly.  If two hats are one color, and the last hat is the second color, then that logician will guess correctly while the others abstain.  Thus, the logicians win 75% of the time.

Proof of optimality

Remember that each hat is colored independently.  Therefore, whenever a logician takes a guess, they have a 50% of getting it correct and 50% of getting incorrect.  Suppose that the logicians have a predetermined strategy.  There are 8 possible ways their hats can be colored.  Among these 8 possibilities, there must be an equal number of correct and incorrect guesses.

For example, consider the strategy above.  Here are the 8 possible colorings (R=red, B=blue) and the number of correct/incorrect guesses for each:

RRR 3 incorrect
RRB 1 correct
RBR 1 correct
RBB 1 correct
BRR 1 correct
BRB 1 correct
BBR 1 correct
BBB 3 incorrect

Here there are a total of 6 correct guesses and 6 incorrect guesses.  It's all a matter of distributing those guesses in an optimal way.  The best way to do it is to spread out the correct guesses and group together the incorrect guesses.  There can be at most 3 incorrect guesses for a single possibility.  Therefore 75% is the best you can do.

Adding more logicians
(Warning: advanced puzzle-solving ahead!)

If there are N logicians, we can prove that the best strategy can win no more than N/(N-1) probability.  Of course, there is no guarantee that there exists any such strategy, and it may be that the best strategy is worse than that.

It turns out, though, that for 2^k-1 logicians, we can devise such a strategy.  But describing this strategy is difficult.  I think the best way to describe it is by listing the "losing possibilities".  A losing possibility is a hat-coloring which will result in all the logicians guessing incorrectly.  For example, in the strategy I described for 3 logicians, the losing possibilities were BBB and RRR.

When each logician looks at the other hats' colors, she tries to determine if the hats may be colored like any of the losing possibilities.  If not, then she abstains.  If there's a chance that it's a losing possibility, then she bets against it by guessing the other color.

For 7 logicians, I need to pick 16 losing possibilities in such a way as to correctly distribute the correct guesses.  Rather than listing out all 16, I will list 4.  The rest of the losing possibilities can be found by taking bitwise XOR operations of other losing possibilities. (0=Blue, 1=Red)

1110000
1001001
0101010
0011100

This solution is not unique.  Rather than proving it, I will simply assert that this wins with 7/8 probability.

And here is a solution for 15 logicians, stated in the same format:

111000000000000
100100100000000
010101000000000
001110000000000
100000010000001
010000010000010
001000010000100
000100010001000
000010010010000
000001010100000
000000111000000

I leave it as an exercise to the interested and savvy reader to solve the general case for 2^k - 1 logicians.

Solutions to circular cutouts

See the original puzzle

Above, I've highlighted several regions which we will use as intermediate steps to find the area of the center.  The letters A through D represent the area of that region.  I'm taking the square to have unit length sides.

A is a sixth of a circle.
A = 1/6 pi

B is an equilateral triangle.
B = sqrt(3)/4

C can be found by combining A and B.
C = 2A - B = 1/3 pi - sqrt(3)/4

D is a quarter of a circle.
D = 1/4 pi

By tinkering around with C and D, we can find the area of the center region.
Area of center = 1 - 4D + 4C = 1/3 pi + 1 - sqrt(3)

Candy combinatorics solution

See the original puzzles

Candy Giveaway

Take 24 objects in a row.  Choose any 5 of them.  Call the chosen objects "candy" and the not-chosen objects "dividers".  Then arrange the 20 students in a row.  The first student gets the amount of candy to the left of the first divider.  The second student gets the amount of candy between the first and second divider.  The third student gets the amount of candy between the second and third divider.  And so on.

Each way to choose 5 objects out of 24 corresponds to a unique way to distribute candy.  And each way of distributing candy corresponds to a unique way of choosing 5 objects out of 24.  Therefore, the number of ways to give out the candy is C(24,5).

In general, for N students and K pieces of candy, it's C(N+K-1,K).

Class Candy Clash

I think this one is a bit of a headbanger, though it's hidden underneath some math.

In the two classes, there are a total of 40 students.  Choose any 20 of them.  The students chosen in my class participate in the competition.  The students in my colleague's class that were not chosen participate in the competition.  In this way, both my class and her class have equally sized teams.

Thus, there are C(40,20)-1 different possibilities (subtracting off 1, so as to eliminate the possibility of having zero students participate).

Acute dissection solutions

See the original puzzle

Triangle: spoiler!

Square: spoiler!

Fractal Maze hints

Last month, I designed and posted a fractal maze.  I'm not sure that anyone could solve it.  Haha, sometimes I get a little overzealous with my puzzles.  Rather than posting the solution, I'm going to explain how I designed the maze.  If you understand the process, it will provide insight into how to solve it.

When designing this maze, drawing out the maze was the last step.  The first step was to consider the maze more abstractly, and decide what would connect to what.

So I decided that there would be two smaller copies of the maze, called A and B.  Each copy of the maze can be specified with a finite sequence of As and Bs.  For instance, if I go down a level into B, and then down a level into A, this can be described with the sequence BA.

But to fully describe a position within the maze, we need more than just As and Bs to specify which copy of the maze we're talking about.  We also need to specify where we are within that copy.  So I decided there would be two checkpoints, called 1 and 2.

From each of these checkpoints, there is a set of actions you can take to move from one place to another.  For instance, starting at position 2, you can go down A, down B, and end up at position 1.  I denoted this action as 2-AB-1, because it starts at 2, ends at 1, and goes down AB.

Some of the actions would also go up a level.  I denoted those with inverse notation, like A^-1.  Note that you can also take any of these actions backwards.

Here's the list of actions I came up with:

1. 1-BBA-1
2. 1-A-2
3. 1-B^-1A^-1-2
4. 1-A^-1B-2
5. 2-A^-1BA-2
6. 2-A^-1-1
7. 2-AB-1
8. 2-B^-1A-1

And with this simple list of eight actions (some of which are redundant), I was practically done!  The rest was just a matter of presenting the above in a somewhat aesthetic fashion.

Solution to "Parachuting Robots"

See the original puzzle

Each robot executes the following program:

Move to the right at half-max speed (or if you like, alternate moving and stopping)
Until a parachute on the ground is encountered...
Then, move to the right at max speed.

As far as I know, this is the fastest possible program.

Solution to Parity Puzzles

See the original puzzles

Puzzle #1: See image

If we color the shape in a checkerboard pattern, then each domino must cover exactly one blue square and one green square. The problem? There are 23 green squares and 25 blue squares. Therefore it's impossible.

Puzzle #2: See Image

Here, we imagine that the entire plane is tiled with a checkerboard pattern like shown in the above image. Each N tetromino covers an odd number of green squares. So an odd number of N tetrominoes covers an odd number of green squares. But each O tetromino covers an even number of green squares. Therefore it's impossible to find a shape that can be tiled by an odd number of N tetrominoes or an odd number of O tetrominoes.

Similar proofs can be constructed for any pair of tetrominoes.  But I leave this as an exercise to the reader.

Reader Secret Squirrel proposed another proof that was a little more complex.  I summarize it here:

1. Each N tetromino is either vertically or horizontally oriented.  So out of an odd number of N tetrominoes there must either be an odd number of vertical tetrominoes or an odd number of horizontal tetrominoes.
2. Let's say that there are an odd number of horizontal N tetrominoes (if not, then rotate the plane 90 degrees).  Consider the number of squares covered in each column, and consider whether this number is odd or even in each column.  Each horizontal N tetromino contributes an "unpaired" square to two columns (and vertical tetrominoes contribute nothing).  It's impossible to pair up all the unpaired squares with an odd number of tetrominoes.
3. If we build a shape with O tetrominoes, each column must have an even number of squares covered.  Therefore, we can't build the same shape with O tetrominoes.

On some reflection, you might see that Secret Squirrel's solution is the same as mine.  Consider this image. If we just consider the horizontally oriented N tetrominoes, then each covers an odd number of green squares.  This is equivalent to step 2 above.  However, we're ignoring the vertical tetrominoes, so we also need to add on a pattern of horizontal stripes.  The horizontal and vertical stripes add up to a checkerboard pattern.

I think this is a case of polished vs unpolished proof.  When you first figure out how to prove a proposition, it's often clunky and difficult.  But from there you can remove the scaffolding and polish it.  But you would never think of the polished proof at first.  When I first formulated a proof, it didn't look much like looks now.

Sometimes this is a problem with math and physics textbooks.  They only present the most polished proofs, leaving it a mystery how anyone ever thought them up.  I sure felt this way all the time in abstract algebra.