This fox has been discussed extensively. See here...1. Calculus by Bleaug
He says: "I spotted this problem in a Paul Halmos book "Problems for mathematicians, young and old, 1991", actually in a French translation. He provided the solution below (reformulated by myself) as being proposed by Hugh Montgomery in 1985 in some Math Conference."
2. Checkerboard Solution by Rochberg and Stein:
- Call sub rectangles as TILEs.
- Start from the lower left corner of the overall rectangle (let's call this point as the origin)Draw horizontal and vertical lines separated by 1/2=0.5 units starting from the origin.
- This will create 0.5 x 0.5 squares (and possibly rectangles around 2 edges -top and/or RHS)
- Color the first square (that has the origin as one of its corners) as black the next one as white, and so on to generate a checkerboard-look.
- Each TILE will have equal areas of black and white (Why?)
- Therefore the overall rectangle will have equal areas of black and white.
- So overall rectangle has at least one integer side.
H means the horizontal side is integer, and V means that the vertical side is integer. a1 is the square at the origin. There could have been a smarter combination, but this simple one illustrates the process clearly. This looks like the closest geometric solution we can get -at this time.
When there's hardly no day nor hardly no nightThere's things half in shadow and halfway in light
3. Induction by Robinson
- Assume that each H-tile has a width of 1, and each V-tile has a height of 1. Note that any rectangle can be converted this way without distorting the original problem. (This may increase the number of tiles significantly though)
- Chose any H-tile, say T(0). (If there is no H-tile, then the result is immediate)
- If there are H-tiles whose lower border shares a segment with T(0)'s upper border, choose one and call it T(1).
- Otherwise only V-tiles share this border. In this case, we can expand T(0) upward 1 unit. This does not increase the number of H-tiles. Also, the cut V-tiles still have height 1. (They are still V-tiles)
- Continue expanding T(0) until either the top of the rectangle is reached or a choice of an adjacent H-tile T(1) is possible.
- Then repeat the same process from T(1). (Continue upward similarly from T(1) to get T(2), and so on...)
- This will result in a chain of T(0), T(1), T(2), ... , T(m).
- Starting from T(0) again, work downward similarly to obtain a bigger chain:
T(-n), T(1-n), ... , T(0), T(1), ... , T(m-1), T(m) of H-tiles stretching from bottom to top. - Remove these tiles and slide the rest together to get a rectangle with fewer H-tiles.
- Induction applied to this smaller rectangle yields the result for the original rectangle.
