Re: Enigma 1452 - Crossed lines
- From: Chappy <petergregorychapman@xxxxxxxxxxx>
- Date: Tue, 04 Sep 2007 19:41:04 -0700
On Sep 4, 5:09 pm, Simon Tatham <ana...@xxxxxxxxx> wrote:
Chappy <petergregorychap...@xxxxxxxxxxx> wrote:
Enigma 1452 - Crossed lines
New Scientist magazine, 21 July 2007.
by Susan Denham.
+---+---+---+---+
| | | | | How many rectangles
+---+---+---+---+ can be seen in this
| | | | | 4-by-4 grid (show
+---+---+---+---+ on the left?
| | | | |
+---+---+---+---+ In fact there are
| | | | | exactly 100.
+---+---+---+---+
Which you can work out by considering each dimension separately: in
the x-direction each rectangle must have an extent of either 1 (4
possibilities), 2 (3 possibilities), 3 (2 possibilities) or 4 (1
possibility), leading to a total of ten (the 4th triangular number,
or 4(4+1)/2). In the y-direction there are also ten possibilities,
so the total number of rectangles is 10*10 = 100.
I made a much larger square grid with lines dividing it into little
squares (a three-figure number of little squares, in fact) and I
calculated the number of rectangles which could be seen in this new
grid. I then cut the grid along one of the lines in order to make
two rectangular pieces and I calculated the number of rectangles
visible in each of my two new pieces. The total of these two
numbers was exactly two-thirds of the number Visible in my original
large square grid.
Suppose the new pieces had dimensions a x (a+b), and b x (a+b).
Then the original number of rectangles would have been
((a+b)(a+b+1)/2)^2, and the new number of rectangles would be
(a+b)(a+b+1)/2 * (a(a+1)/2 + b(b+1)/2). The latter is equal to two
thirds of the former.
We can extract a common factor of (a+b)(a+b+1)/2, and end up with
the equation
2 * (a+b)(a+b+1)/2 = 3 * (a(a+1)/2 + b(b+1)/2)
=> 2(a+b)(a+b+1) = 3a(a+1) + 3b(b+1)
=> 2a^2+4ab+2b^2+2a+2b = 3a^2+3b^2+3a+3b
=> 0 = a^2 - 4ab + b^2 + a + b (*)
If we treat (*) as a quadratic in a, we find its solution to be
a = ((4b-1) + sqrt(12b^2 - 12b + 1)) / 2 (**)
(or the negative square root, of course), for any b such that 12b^2
- 12b + 1 is a perfect square.
However, similarly, 12a^2 - 12a + 1 must also be a perfect square
(which we can deduce in exactly the same fashion by rewriting (*) as
a quadratic in b). Hence, given any starting b such that 12b^2 - 12b
+ 1 is a perfect square, we can compute a valid a from it using
(**), then set b to _that_ and compute another valid a in turn, and
so on. Hence we derive an infinite sequence of (a,b) pairs.
An obvious starting value is b=1, which gives us 12b^2-12b+1 = 1
which is a perfect square. Hence we feed that value into (**)
repeatedly:
b=1 gives us a=2
b=2 gives us a=6
b=6 gives us a=21
b=21 gives us a=77
b=77 gives us a=286
b=286 gives us a=1066
b=1066 gives us a=3977
b=3977 gives us a=14841
and so on. Every one of these (a,b) pairs is a valid solution in
integers to the original equation (*), and hence has the desired
property that an (a+b) by (a+b) square contains exactly 3/2 times as
many rectangles as when it's cut into two pieces of dimensions a x
(a+b) and b x (a+b).
I haven't proved that these are _all_ the possible solutions, but I
think an infinite descent argument should be adequate to show that.
In the above sequence I'm repeatedly evaluating (**) with the
positive square root, to find an a greater than the input b. If
instead I were to use the negative square root, I would be able to
construct a _descending_ sequence starting from any valid b; there
can be no infinite descending sequence in the natural numbers, so we
would eventually have to reach zero - meaning that we must have
retraced exactly the above sequence, and not any other sequence
running parallel to it.
The final constraint in the problem was that the original square had
a three-digit area, i.e. (a+b)^2 is between 100 and 999 inclusive.
That allows us to pick a solution out of the above sequence: (2+6)^2
is too small, (21+77)^2 is too big, so we want (6+21)^2 = 729.
Hence the original grid was 27x27, containing 142884 rectangles; and
it was cut into a 6x27 piece and a 21x27 piece, containing
respectively 7938 and 87318 rectangles for a total of 95256, which
is exactly 2/3 of 142884 as required.
Nicely solved Simon. And correct of course.
Ciao,
Chappy.
.
- References:
- Enigma 1452 - Crossed lines
- From: Chappy
- Re: Enigma 1452 - Crossed lines
- From: Simon Tatham
- Enigma 1452 - Crossed lines
- Prev by Date: Re: Dell Variety Sudoku magazine
- Next by Date: new puzzle...try this........
- Previous by thread: Re: Enigma 1452 - Crossed lines
- Next by thread: Re: Celebrity Justice
- Index(es):
Relevant Pages
|
