Enigma 1308 - Passing through

Enigma 1308 - Passing through New Scientist magazine, 25 September 2004. by Richard England.

If you are told to draw a rectangle along the lines of a sheet of graph paper such that its area is 40 squares you could choose rectangles measuring 8x5, 10x4, 20x2 or 40x1. Whether you chose the 8x5 or the 10x4 you would find that a diagonal drawn across your rectangle would pass though 12 of the squares.

(1) What is the smallest number of squares of the graph paper that can be the area of THREE different rectangles whose diagonals each pass through the same number of squares?

(2) How many squares does each of those diagonals pass through?

Ciao,

j u s s o s t m p s e o p i a l c e e r

144, 24

Heading the obvious extension off at the pass:

3024, 108

I think 14400 is the first 5-way solution, anyone care to confirm?

S P O I L E R

S P A C E

It's actually the second solution. The earliest solutions for 5 and 6 are:

5: 3600, 120 6: 32400, 360

(I only checked values up to 10^5.)

Cheers,

That's the problem when a fallable human looks at too much output from a (supposedly) infallible program. I should put more intelligence into the program to make up for the lack of my own!

120x30 = 30*(4x1)=30*(4)=120 90x40 = 10*(9x4)=10*(12)=120 80x45 = 5*(16x9)=5*(24)=120 75x48 = 3*(25x16)=3*(40)=120 72x50 = 2*(36x25)=2*(60)=120

360x90 = 90*(4x1)=90*(4)=360 270x120 = 30*(9x4)=30*(12)=360 240x135 = 15*(16x9)=15*(24)=360 225x144 = 9*(25x16)=9*(40)=360 216x150 = 6*(36x25)=6*(60)=360 200x162 = 2*(100x81)=2*(180)=360

Back to the original:

but restrict it to _odd_ areas.

barfvkmrebrvtuggjbsvirsvir baravarfriragjbsbhegjbsvir guerrmrebmrebavarrvtuggjbsvir

OK, that was significantly harder. The answer is:

3: 1608255, 2565

An almost certainly non-minimal value for 4 is:

4: 7828554825, 176715

Cheers,

Is there any way to come up with solutions for this without using brute

The 'noise' at the end of my prior post was the first three values ROT-13 encoded. I seem to remember that being the first of them (especially the 2565 rings a bell).

I didn't search that far, but as you got the same answer for 3, I'd be pretty confident that you've got this spot on too.

Ah, right. Up to 10^7, there are only 4 values which work:

3: 1608255 (2565) 3: 1972425 (2805) 3: 3009825 (3465) 3: 6380451 (5049)

(I like how that last one is not divisible by 5.) The first three of these are indeed the ones you reported.

Oh, no, this was a random find, where I started with something 'large enough' to be likely to produce an answer. (Specifically, I looked at multiples of 3^4*5^2*7^2, rather than trying for a specific upper limit. This was also how I found my first solution for 3; it produced so many that I reduced the value to 3^2*5^2*7^2, which gave the third of the solutions above, and then I searched that entire space to find the minimal value.) It would be quite surprising if it actually were minimal.

On the other hand, I can confirm that between 10^7 and 10^8 there are only 15 new solutions, all producing 3 but not 4. So the above is certainly not too far off minimal (in a logarithmic sense). Based on nothing in particular, I kind of expect a solution between 10^8 and 10^9; maybe I'll try and write something a bit more efficient to check this range.

Cheers,

[ Various attributions snipped, mostly Me and Phil Carmody ]

The two lowest solutions for 4 are:

4: 194598855 (28215) 4: 869839425 (58905)

Two other solutions found by random selection are:

4: 7828554825 (176715) (already mentioned) 4: 274096659375 (1047375)

Cheers,

Great work, Geoff!