Hi guys,Just came up with 2 possible proofs almost at the same time.1. Define a function that is periodic along both axes x and y such that ( I think should do the trick ). Then the surface integral over one rectangle would equal to zero if either side is of integer length. Since the surface integral over the big rectangle is the sum of the integrals over the smaller rectangles, it is also equal to zero. QED.2. Paint all the rectangles that have a horizontal integral edge black and those with a vertical integral edge white. Then it is a matter of finding a path from the left edge of the big rectangle to the right edge of the big rectangle hopping along black rectangles only. This is not possible only if there is a wall of white rectangles running from the top to the bottom completely blocking our path. Either way we are done. Voila!

QuoteOriginally posted by: vixenHi guys,1. Define a function that is periodic along both axes x and y such that ( I think should do the trick ). Then the surface integral over one rectangle would equal to zero if either side is of integer length. Since the surface integral over the big rectangle is the sum of the integrals over the smaller rectangles, it is also equal to zero. QED.This is (IMHO, anyway) the most beautiful proof, well done! The shorter version is .

Vixen's proof is truly awesome!!!I checked my proof with ppl. I think it works only when there are finitely many "small" rectangles.

This problem is truly amazing. Another contender for the most beautiful proof is the "checkerboard" one mentioned earlier. You generate a checkerboard with a cell size 1/2 x 1/2 and paint it in a standard manner. Then it is easy to see that a rectangle has an integer side iff it has an equal amount of black and white, no matter its position relative to the grid. The latter quality is of course additive. QED.In fact, this is essentially another flavour of the "integral" proof, with .

QuoteOriginally posted by: sevvostThis problem is truly amazing. Another contender for the most beautiful proof is the "checkerboard" one mentioned earlier. You generate a checkerboard with a cell size 1/2 x 1/2 and paint it in a standard manner. Then it is easy to see that a rectangle has an integer side iff it has an equal amount of black and white, no matter its position relative to the grid. The latter quality is of course additive. QED.In fact, this is essentially another flavour of the "integral" proof, with .(*shouting) COOL!!! (for the 1000th time today).

For people who don't have immediate access to the AMM article, I would like to list the 14 proofs it contains:(1) complex integral(2) real integral(3) checkerboard(4) counting squares(5) polynomials(6) prime numbers(7) Eulerian path(8) bipartite graph(9) induction(10) induction, variation(11) minimal cut-set(12) sweep-line(13) step functions(14) Sperner's lemma.The author then considers some generalizations of the theorem and finally makes an effort (somewhat arguable, in my view) to demonstrate that these 14 proofs are indeed different since they all allow for different generalizations.Amusing reading!

I like this proof better (I didn't come up with it):For each subrectangle, pick a pair of parallel edges which are integral in length, and draw red lines along these edges. The graph whose edges are the red lines has vertices of degree 1 at each of the corners of the large rectangle, and of even degree everywhere else. So if we start at a corner of the large rectangle, walking along edges and making sure we never repeat an edge, we must finish at another corner of the large rectangle. But each time we changed either our x or y coordinate in the course of this walk we changed it by an integer, so our overall change in coordinates must be integral too.I like this proof better than the integration one because I could explain it to my children, and because it generalises nicely to other 'special' properties of edges and to higher dimensions. It also seems to me to explain a little more about what is going on than the integral/checkerboard one, which has a bit of a deus ex machina flavour to it (though this probably a matter of personal taste).

Sure, this one is very nice, too - (7) Eulerian path on the list. And I absolutely agree that it is largely a matter of personal preference. BTW, when I first got this problem many years ago - at a high-school contest in the city where I grew up - I had actually attempted to come up with something similar to the Eulerian path proof. Did not quite succeed (and did not get any other ideas, either...)Speaking of children, the checkerboard seems doable, doesn't it?

QuoteOriginally posted by: sevvostSure, this one is very nice, too - (7) Eulerian path on the list. And I absolutely agree that it is largely a matter of personal preference. BTW, when I first got this problem many years ago - at a high-school contest in the city where I grew up - I had actually attempted to come up with something similar to the Eulerian path proof. Did not quite succeed (and did not get any other ideas, either...)Speaking of children, the checkerboard seems doable, doesn't it?I could explain the individual steps to my kids, but I think it would leave them unenlightened. The key point is that a rectangle contains equal areas of black and white if and only iff at least one of its sides is an integer: 'If' is easy, but I don't see how to make 'only if' intuitive (as opposed to proving it, which is different). I suppose this means that I don't really understand the proof yet, in the sense that the result is not yet obvious to me.

In my case, it was the first proof I ever learned, so I guess I got used to it by now .Strictly speaking, it was a little different flavour: first of all, the problem dealt with subrectangles having a side of length 1 (which is of course an exact equivalent of our problem). And instead of the checkerboard, draw the lines y=x+k for all integer k. Then a rectangle has a side of length 1 iff the sum of lengths of all the segments of those skew lines "caught" inside the rectangle is constant, no matter the rectangle's position in the plane (because it equals the length of the other side times sqrt(2) - just draw it, and it immediately becomes obvious.) The rest is the same as the checkerboard proof.

QuoteOriginally posted by: zarnywhoopI like this proof better (I didn't come up with it):For each subrectangle, pick a pair of parallel edges which are integral in length, and draw red lines along these edges. The graph whose edges are the red lines has vertices of degree 1 at each of the corners of the large rectangle, and of even degree everywhere else. So if we start at a corner of the large rectangle, walking along edges and making sure we never repeat an edge, we must finish at another corner of the large rectangle. But each time we changed either our x or y coordinate in the course of this walk we changed it by an integer, so our overall change in coordinates must be integral too.I am not sure if the above works. This is similar to another 'proof' given earlier that consists of finding a continuous path from one side to another. However these continuous paths may not 'add' up to integers in x or y directions. The problem is that while going in x direction you may get cut off by a rectangle that has integral length along y - but the integral length had started from a value of y that is lesser/greater than the vertex where you change directions. The following proof is based on conservation of a charge (which I call fractional height). Charge is however not conserved locally in the sense of being able to find a continuous path of integer rectangles. The proof was suggested to me by a colleague. The non-local nature of the problem is captured really well by the alternative proof using integrals of trigonometric functions. 1. Suppose the rectangle has one corner at (0,0) and is in the positive quadrant. The dimensions of the rectangle are X and Y. 2. Consider vertical lines at integer values of x: x = 0, 1, 2, 3 etc. The first line at x = 0, intersects n_0 rectangles of non-integer heights: h_0_i with i = 1, 2, ... n_0. The second line at x = 1 intersects n_1 rectangles of non-integer heights h_1_i with i = 1, 2, ... n_1 . Then Sigma_i (h_0_i) mod 1 = Sigma_i(h_1_i) mod 1 = Sigma_i(h_m_i) mod 1 = p say, where m is any integer with m < = X. If p is zero then Y is integral and we are done. p is assumed to be non-zero below.3. In other words these rectangles carry the fractional height p between them. These rectangles can only end at x = 1, 2, 3 etc. Call this set R_0. The fractional height associated with R_0 is p. Write this as f(R_0) = p. 4. At any non-integral value of x, x = x_k, a new set of rectangles with fractional height can start as one moves right. These rectangles must end at values like x_k + n where n is an integer. Call the set of all rectangles carrying fractional height that begin or end at x_k + n, R_x_k where x_k is defined modulo 1 (that is x_k < 1). Then the intersection of R_x_k with R_x_j is null if x_k is not equal to x_j. 5. Using the fact that fractional height is additive modulo 1 for any value of x, it can be seen that f(R_x_k) = 0 if x_k != 0 and f(R_x_k) = p if x_k = 0. In other words - all the fractional height is carried by R_0. 6. Because the fractional height is conserved for all x, at least one rectangle from R_0 exists and ends at x = X. But R_0 can end only at integral values. Therefore X is integral.

I am sorry, I don't see any problem with the Eulerian path proof given by zarnywhoop. I think it works just fine (and is in fact very elegant.)

QuoteOriginally posted by: sevvostI am sorry, I don't see any problem with the Eulerian path proof given by zarnywhoop. I think it works just fine (and is in fact very elegant.)I guess then that I don't see how the local route imposes the condition that the external container of the graph must also be a rectangle. Can someone help?