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.