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.

One At A Time

Alright, time for the solution to the blind maze puzzle from last time.

The solution is pretty simple, the main point to notice is that, for a particular N, there are only finitely many mazes that can exist, so you essentially solve them one at a time. Specifically, you number the mazes 1 through M, then begin by writing instructions for the solution for maze 1, which is easy to find explicitly. Next, assume you are in maze number 2, and see where you would be given the instructions you have written so far, and then continue with the instructions to solve maze 2. Step by step, solve all the mazes that you could possibly be in. This will only create a finite list of instructions.

As for the more difficult problem of finding a solution that guarantees ending the program on the final square, imagine running all of those M mazes in parallel, each using the same set of instructions. The goal is to make sure that we are on the final square of every maze simultaneously, then we stop the program.

To prove that there exists a program to do this, let us consider a randomly generated program that is S steps long. The randomly generated program will move north with probability e, south with probability 1/2-e, west with probabilty e and east with probability 1/2-e. I claim that for a sufficiently small e, and sufficiently large S, the robot following this program will be on the final square of every maze simultaneously at some point. In a sense, even if the claim is true, it does little to help us find a program for our solution, since we don't know how long we should run our randomly generated program for. This objection doesn't really matter though, we are only trying to prove existence of a program, we don't need to actually find it. If our program has any non-zero chance of getting to all the endings at the same time, then there exists a program that terminates on the ending of any maze we could be in.

Next, for a particular maze m, the robot is wandering around the maze at random, with probabilities as above. By the Perron-Frobenius theorem, there is a unique steady state distribution of probabilites p(i,j) for the robot to be at location (i,j), and after a large enough number of steps any starting distribution will converge to this one. The main idea will be to show that when e is sufficiently small, p(N,N) becomes close to 1 (in other words, over a very large timescale the wandering robot will spend almost all of its time at the exit).

The main point of the proof is that p(i,j) is proportional to ((1/2-e)/e)^(i+j) for any reachable (i,j) in the maze M (this is the point that I am not sure how to prove, I'm sure its something simple using random walk theory, but my education is deficient there). Since p(N,N) < 1, we must have p(i,j) < e/(1/2-e) ≤ 4e for (i,j) not equal to (N,N) (this happens because if we choose e < 1/4). Thus p(N,N) is at least 1-((N^2-1)*4e). It will take some number of steps to do this for each separate maze, but you can just take the maximum over all the mazes.

Now, note that if we have two events A and B, with probabilities 1-x and 1-y of happening, then the probability of A and B happening is at least 1-x-y (you can prove this from P(A and B) = P(A) + P(B) - P(A or B) and P(A and B) is at most 1). In our case, we have M events (getting to the end of the maze in each maze) and the chance of each happening is at least 1-M*((N^2-1)*4e). So, with a suitable choice of e, such as 1/(2((N^2-1)*4), the probability of all of the events happening is at least 1/2.

So there is some nonzero chance of getting to the end of every maze at once, and so there must exist some set of instructions that will end at the end of the maze. This proof gets us no closer to finding it, I suppose, but who cares about that.

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.

One At A Time

Alright, time to finish off the solution to the balls in jars problem from before.

The essential proof is that it is possible to find an algorithm that will move from a position (a,b,c), with a>b>c, to a position (x,y,z) such that z is less than c. Thus by repeating this algorithm no more than c times, you must reach zero (given that we can only have integer values).

OK, suppose we start in some position. Call the bucket with the most marbles A, the one with the fewest marbles C, and the other one B. The names of those jars will not change throughout the algorithm, specifically even though C has the fewest at the start it might not at some later point. Let a, b, and c be the number of marbles in jars A, B, and C respectively. Note that even though A, B, and C will not change throughout the algorithm, the values of a, b, and c will.

The algorithm is: Check the value of floor(b/c). If it is even, move marbles from A to C. If it is odd, move marbles from B to C. If C has more marbles than B then stop, otherwise go back to the start.

Simple enough, now, to prove it works. We must prove that at the end B will have fewer marbles in it than C started with.

At the start, we know that b is greater than c, let us write b=qc+t with t less than c, so q being the floor of b/c. For this proof, we will not change the values of a, b, and c, I will assume those values are locked at the start.

Let us suppose b is not at least twice as big as c, so then q=1 and when we move marbles from B to C (as per the algorithm), B will have t marbles in it, and t is less than c.

Now, if q is bigger than 1, I will show that the algorithm will reduce the number of marbles in jar B without changing the value of t, so eventually q will be 1.

So, if we suppose q is even, so we move marbles from A to C. Now C contains 2c, and B contains b. Since b=qc+t=(q/2)(2c)+t, so b mod c and b mod 2c both give t (note that q being even was needed).

If q is odd, we will move marbles from B to C. Now C contains 2c and B contains b-c. Since b=qc+t we can also then show b-c=((q-1)/2)(2c)+t, so b mod c and b-c mod 2c both give t (in this case q being odd is needed).

Each time, B contains fewer marbles, so eventually q will be 1 and then next move B will have t marbles, which was less than the starting value of C. So, this finishes the proof. One simply needs to repeat the algorithm many times (renaming the jars A, B, and C after each iteration) to win the game.

Two In One

Alright, time for the partial solution to the balls in jars problem from last time.

I guess since the two-jar problem is a decent amount easier, I'll solve that out first.

First of all, it is absolutley trivial to see that if the total number of balls in the jars is not an even number, there will be no way to win, since to win you must first arrive at a position of the form (p,p). Next, it is easy to see that any common divisor has no effect on the ability to win from a position, that is to say: the position (p,q) is winnable iff the position (np,nq) is winnable.

At this point, we might be inclined to work out a few winning positions. OK, so what are the winning positions of the form (1,q)? Well, clearly (1,1) is a winning position, and (1,q) can only be a winning position if q is odd. From the position (1,q) we move to the position (2,q-1), but since q is odd for any position of interest this is the same as (1,[q-1]/2) so if we suppose this is another position, say (1,k), we see that q=2k+1 so if (1,k) is a winning position then so is (1,2k+1). From here we can list off the positions as (1,3), (1,7), (1,15)... clearly (1,q) seems to be a winning position if q is 1 less than a power of two. You can prove that by induction if you like, and with a bit more work we can also be sure that there aren't other winning positions of the form (1,q), but I won't bother with that yet.

Next, what about positions of the form (3,q)? Well, first of all q=1 would be a winning position. Next, from (3,q) we can move to (6,q-3) (this assumes that q>3, but other positions are finite enough anyway). Now since we might as well assume q is odd, we can half this position to (3,[q-3]/2) so calling this (3,k) again, we see that if (3,k) is a winning position then so is (3,2k+3). Listing off positions we can see that the winning positions seem to be (3,1), (3,5), (3,11), (3,29)... again summing to a power of two. This makes it seem that a position (p,q) is a winning position iff the sum p+q is a power of two. Well, thats easy enough to disprove, (3,9) is a winning position, but it is merely a multiple of 3 away from (1,3).

The main thing that will finish this off is the realiziation that once you have divided off any multiples in your problem, no new ones will show up, besides 2, and that one will show up every move. Lets prove that. Suppose we are in some position (p,q) with p and q both odd (so that their sum is even, but we do not need to divide off an overall 2), and we assume that p and q are not both multiples of some prime number n (n>2). Now we move to (p-q, 2q) (setting p as the larger one), I claim that p-q and 2q are also not both multiples of n. If they were then q would be a multiple of n (since 2q is) and then p would be (since p-q is and q is). Naturally this argument won't work for n=2, an overall multiple of 2 shows up every single move.

Now I will prove the main result: from position (p,q) with p and q having no common factors, we are in a winning position iff p+q is a power of 2.

You can prove one direction by induction. Prove it for p+q=2^n. It is trivial for n=1, then if it is true for n=k and you are in position (p,q) with p+q=2^(k+1) you can make one move and then half p and q so that p+q will now equal 2^k.

For the other direction we must show that if p+q is a multiple of a prime other than 2 and p and q have no common factors, then it is a losing position. Suppose p+q is z*k where z is a prime other than 2. k must be even, for if p+q is odd then we are trivially in a losing position. In order to win, we must first reach (z*k/2, z*k/2) but we have already proven that once you have divided off multiples, no new ones can show up. A new multiple of z (for z>2) cannot happen, so the position (z*k/2, z*k/2) cannot be reached, so the game cannot be won.

This finishes the proof. While working on the problem I also noticed that the legal move from (p,q) is to (2p,2q) mod p+q, which I thought was sort of cool. Perhaps people who are better at number theory than I can make use of that. Anyway, feel free to try to use this to solve the three jar problem, I was never able to.

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?

Just One

OK, time for the solution to the coins puzzle from last time.

Not much derivation to do, so I'll just sort of post my solution:

Ask if he knows if one of Porthos or Aramis got at least two gold coins. If Athos got two of the three gold coins, he knows the answer is no. If Athos got no gold coins, then given that all three were given out he knows that the answer is yes. If Athos got one gold coin then he will not be sure.

Of course, you can switch "gold" for "silver" in that solution if you like. Anyway, simple, like I said, but I sort of thought it was neat. I would love to hear any alternate solutions, I haven't thought of any but they probably exist.

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.

One Way Or The Other

Solution time! Puzzle last time was that game about breaking chocolate.

I know of two ways to come about the solution, the one is easy and elegant (and was how I solved it initially), while the other is a bit more roundabout and uses a bunch of game theory that I think is sort of cool. Anyway, I'm going to do the long game theory version first, if you want to just read the elegant quick solution, skip to the second last paragraph.

First of all, I'm going to set up a bit about game theory of impartial games, games where both players always have the same options available to them (other games are called partizan, chess and go are partizan games with one player playing black and the other white, I cannot move your pawn). I will also be focused exclusively on the type of game where the players alternate turns in the usual way. It is clear that for any impartial game, in any position either the active player has a winning strategy or the inactive player does. As is standard, we will call the former kind of position an "N-position" (for next player wins) and the latter a "P-position" (for previous player wins). It is clear that from any position you always want to move to P-positions, when possible.

At this point will be looking just at games that use the "normal play" rule that is, if you have no moves available on your turn you lose the game (as opposed to the "misère play" rule where having no legal moves is a win). So the game state with no legal moves is a P-position. Generally speaking, if from a game state you can move to a P-position, then that game state must be an N-position (since P-position moves are winning moves, having a P move available means that the active player has a winning strategy). On the other hand, if all the legal moves from a game state are N-positions (including the specific case of no legal moves), then that game state must be a P-position. So if a player has used this to completely map out the game space (first by labeling the end state P then moving outward labeling things P or N) that player will always try to move to a P-position, the opponent will have to choice to move to an N-positon, from which a new move to a P-position is available, and eventually the game must end with the winning player being the one who can move the game into P-positions (the end state also being a P-position).

Next we must figure out how game types combine when you add them together as we do in the breaking chocolate game. Suppose we start the breaking chocolate gmae from a 5x6 position and we move to the 5x2 + 5x4 position, what does that "+" mean? It means that we can make a move in either game. So, if G and H are both games, then G+H is the game where you can legally move in either G or in H, you must move in one of them, but not in both. Convince yourself that this addition is associative, that is (G+H)+J is the same as G+(H+J), it is also commutative but that is trivial.

Now we can prove something, I claim that if G is a P-position and if H is a P-position, then G+H is also a P-position (yay, a theorem), the proof is to simply show the strategy. If G is a P-position, then the inactive player has a response to any move the active player can make, and the inactive player can guarantee that it is the active player will run out of moves first (note how much more difficult it is if we used misère play instead, the fact is normal play is much easier to analyise in most cases). All this is true about H as well, so by simply always responding to the opponents moves in G with moves in G and respond to moves in H with moves in H you can always get to another position of the form P+P. So, we see that:

P+P=P

Good good.

Next, I claim that if G is an N-position and H is a P-position then G+H is an N-position. To prove this I simply need to show that there is a legal move in G+H to a state that is a P-position. We know that there is a legal move in G to a game state K with K being a P-position, but then K+H is a P-position by the previous theorem. So we see that there is a legal move in G+H to a P-position, specifically the move from G to K. So, we have:

N+P=N

Actually, we can quite generally show that if H is a P-position, then for any game G, G+H=G because you can just use your strategy in G and always respond to opponent moves in H with moves in H.

Alright, it is natural to wonder about N+N next, unfortunately you can come up with situations in actual games where N+N can be P and other games where N+N can be N. You can show that any game plus itself is a P-position, because in G+G you can always answer your opponents move in one with the same move in ther other, so they will run out of moves first, so G+G is a P-position, but if G and H are both N-positions, but not the same N-position, you can't prove much.

Alright, now for the chocolate game, I will prove the following statement for some arbitrary AxB position (I would have used NxM, but N is being used for something else here, and that notation is more standard):

AxB is a P-position if both A and B are odd and is an N-position if either A or B is even

The proof will be by induction, we can see this are true if AxB is 1x1, now to prove it by indution suppose we have want to prove this statement for a particular AxB and we are going to assume it is true for all ixB (with i less than A) and all Axj (with j less than B).

Now, I must show that AxB can reach a P-position if either A or B are even, this is easy, just move to (A/2)xB+(A/2)xB or Ax(B/2)+Ax(B/2), whichever exists. Then you mirror the opponent from there and cannot run out of moves first, so AxB can reach a P-position, it must be an N-position. Now if A and B are both odd, a generic legal move is to RxB+SxB with R even and S odd. But then RxB is an N-position and SxB is a P-position by the induction assumption and we know that N+P=N, so any legal move leads to an N-position meaning AxB must have been a P-position.

This completes the proof of the theorem, so we know from any start position if it is a P-position or an N-position so we can clearly say who wins and how (and the typical winning move is to break even sides directly in half), now I will show that that is totally unneeded and if you are in a winning position you can just make random moves and you won't ruin it.

Consider, at the start of the game we have a single block of chocolate on the table (of size NxM), each move causes one break in an existing piece of chocolate, increasing the number of blocks of chocolate on the table by exactly 1. The game ends when there are NxM blocks of chocolate on the table, so exactly NxM-1 moves have gone by, no matter what people chose as their moves there were exactly NxM-1 moves in all cases. The first player wins if NxM is even as there will be an odd number of moves, and the second player wins if NxM is odd as there will be an even number of moves.

Anyway, game theory is cool, but this game is really trivial. The P and N-position things come up alot in other games though, for example the game where you are removing sticks from a pile of N sticks but you cannot remove more than 4 (or K) at a time. You can also be a bit more general and use the Sprague–Grundy theorem to make any impartial game under the normal play condition into nim, but that takes more work (though not much more).

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).

Trinary Answer

Two posts in one month? Unheard of. Anyway, I found a new puzzle recently, so now I have two puzzles I haven't posted and I want to waste them as soon as possible (also, post them before I forget what they are).

Alright, solution to last times light bulb puzzle:

You turn on one switch and leave it on for a reasonable amount of time, then turn it off and turn on a different switch. Go to the other building and check to see if the light bulb is on, warm, or cold, each of these results points to a different switch.

Not much to it, there are proably other answers, but its hard to come up with one as reasonable as this one. If you have any, I would love to hear them.

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).

Off The Edge

I still blog, I swear. Anyway, I suppose I should put up the solution for the plane puzzle from last time.

There is a standard puzzle of this form where you have camels going into a desert and you have to feed them, bananas or something, but each camel can only carry a finite amount of food. Suppose a camel can carry enough food to go 90 meters (I choose 90 so I can take fractions of it easily), then with two camels you head out 45 meters, transfer all the food from camel 2 to camel 1 and can then go another 90 meters with camel 1 making a total of 135 meters. With 3 camels we can go 30 meters out, move all the food from camel 3 to 2 and 1 and then make it another 135 on top of the 30 for a total of 165. In general if one camel can carry the food for distance x, then the n^th camel adds an extra x/n to your total distance.

Anyway, then with our planes we can use this sort of strategy to go 1+1/2+1/3 times the distance half-way around the world, but that is only 11/6, so we are short. The solution to this is to make use of the fact that the puzzle is happening on the world, so we can go around the other way. Use two planes to go 3/2 the distance of one plane (that is 3/4 of the way around the world) and have the other plane meet you by going the last bit in the other direction.

Its not much of a puzzle, but its sort of cute and I thought it was a neat variation on a standard puzzle.

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.

Find The Circle

OK, time to post the solution to the sums of squares problem I put up a little while ago.

I once heard of a game that Feynman used to play with his classmates called "find the circle" in which somebody would state some mathematical fact that has a pi in it and the other players would have to figure out what circle came up in the math behind the fact that resulted in a pi showing up (I can currently find no evidence of this game ever being played, so its possible I was imagining this story, or the relavent character was not Feynman). Essentially, the point is that the only places that pi ever would show up involve a circle, and when it shows up other places you can bet there is a circle hiding somewhere. Personally I don't agree with that philosophy, I think that pi is more fundamental than that, but this puzzle will not be a demonstration of my belief, a circle will show up quite nicely for us.

Alright, let us suppose we have a function, called g(k), which is the number of times that k can be written as the sum of two squares as outlined in the puzzle. Next we will let f(m) be the sum of 1 through m of g(k), then the average number of ways that numbers can be written as the sum of two squares is f(n)/n, that is, we seek to prove that for large N

f(N)/N = π

Consider taking some value k, for each way it can be expressed as the sum of two squares, we can write x²+y²=k for some (x,y), and for each pair (x,y) that solves x²+y²=k, we have a way to write k as the sum of two squares. That is, for each point in the plane with integer coordinates on a circle of radius √k, we have a way to express k as the sum of two squares. So we can say that g(k) is the number of integer points on a circle of radius √k. This means that we can say that f(m) is equal to the number of integer points that lie on a circle of radius equal to root some integer less than or equal to m. But every point with integer coordinates lies on a circle of radius equal to the square root of some integer (specifically (x,y) lies on a circle of radius √(x²+y²)) so f(m) is simply equal to the number of integer points that lie inside a circle of radius √m.

So, how do we calculate the number of integer points that lie inside a circle of radius R? Suppose for each such point, we shade the 1x1 square that is to its lower left. Then the total area shaded is equal to the number of points, and we can easily see that the shaded area is approximately equal to the area of the circle of radius R. I always hate using the term "approximately" in a non-technical sense though, so lets be technical about it.

It is easy to see that the shaded area equal to the circle area up to an error term that is, at most, the area of a strip with width √2 that runs around the circumference of the circle. In reality the error will be much smaller than this, we tend to have missing area in the upper right parts and extra area in the lower left parts and these will typically cancel pretty well, but nevermind that, I want an easy upper bound on the size of the error term. Since the shaded area is known to equal f(m) and the area of a circle of radius √m is πm, we can see that

f(m)=πm+C√m

where C√m is our error term, C can be positive or negative, and can depend on m, but its absolute value is bounded by a constant (the constant being 2π√2, for those paying attention).

So finally we can see that

f(N)/N=π+C/√N

for large enough N to consider the second term small, the average number of ways the first N numbers can be written as the sum of two squares is π.

Sums Of Squares

New puzzle time? New puzzle time.

I first found this one at Futility Closet:

Consider the number of ways a positive integer can be written as the sum of two integer squares, for example, 8 can be written four ways, m²+n² as (m,n)=(2,2), (-2,2), (2,-2), (2,2), while 5 can be done eight ways (2,1), (-2,1), (2,-1), (-2,-1), (1,2), (-1,2), (1,-2), (-1,-2), and 7 cannot be written as the sum of two squares at all.

Over a very large collection of integers from 1 to N, the average number of ways a number can be written as the sum of two squares approaches π, why should this be?

Just in case we are using different browsers, π is supposed to render as pi, it looks a bit funny in firefox.

The puzzle is a bit of a weird one, being something of a proof more than anything, but there is a proof that can be understood only using high school math, so I don't think its too tricky. There are probably more convoluted proofs, of course, being that π is involved.

Frogs In A Line

Time to put up the solution to the frogs puzzle from last time.

First of all, let us analyse what sort of move a frog can make, since we are trying to prove that the frogs cannot reach some configuration it makes sense to find some conserved quantity. First let us assume that the frogs start out on the locations [0,0], [0,1], [1,0], [1,1], that is the square they begin on.

Suppose we have a frog at [x₁,y₁] and another at [x₂,y₂] and frog 1 jumps frog 2. He then moves to [x₁+2(x₂-x₁),y₁+2(y₂-y₁)], that is, his position increases by double the distance between 1 and 2. First of all, this shows that if they start on integer coordinates, they must remain in integer coordinates, they cannot leave the integer grid through any moves. Anyway, our new frog position is [2x₂-x₁,2y₂-y₁]. Specifically, if the x location was even before the jump, it remains even after the jump, and if it was odd, it remains so, similarily for the y coordinate. So we have a conserved quantity for our frog motions. In particular since they start out [even,even], [even,odd], [odd,even], [odd,odd], they will remain so forever. So now we know that it is impossible for two frogs to ever be on the same location, since our frogs all have different parities. This also quickly shows we cannot ever have three frogs on a line that is lined up along our coordinate grid (the lines x=constant or y=constant), but it is less obvious that you cannot have three frogs on an angled line (ax+by=constant), I will show that now.

So, suppose you were to reach some configuration where the frogs are all on a line (at different places on the line of course, we know they cannot share a location). That line goes through infinitely many points on our grid, all spaced out a distance d apart. Identify the middle frog, and the other two frogs are distances u and v away from it. We can see that u and v must both be positive integer multiples of d, and if u=v we can have one frog jump to get two frogs on the same location, so u cannot equal v. Suppose u is less than v (if not, rename u and v), have the frog that is distance u away jump over the middle frog. The jumping frog will become the new middle frog and the distances are now u and v-u. Call the smaller of these two u' and the larger one v'. We can see that u'+v'=v, so u'+v' is smaller than u+v. If u' does not equal v', then repeat the process, have the frog u' away jump the middle frog. We will keep repeating this process, and each time we do, we make u and v smaller numbers. But they are always integer multiples of d so eventually we will get to a point where two frogs must share a location (it cannot take more than the initial (u+v)/d steps to do this). At this point we have a contradiction.

I suppose one could also analyse ax+by=c for values of x and y being even and odd and show that you won't have three frogs on a line without breaking the parity rule, but then you have to go through all sorts of arguments about a, b, and c being integers first. Its not really any harder that way, but I find the argument of the previous paragraph more compelling.

If you want a follow up problem to this, it was given in the comments last time, show that you cannot ever have the four frogs arrange themselves into a larger square. The solution was also given in the comments, so I won't go over it.