From The Sunday Times, 25th January 1970 [link]
The card of the course at Triangle Park Golf Club gives the total length of the first 9 holes as 3,360 yards. Par for the individual holes (numbers 1 to 9 respectively) being 5, 4, 5, 4, 3, 4, 4, 3, 5 (total 37).
Closer inspection of the card would show that the lengths of the holes (each a whole number of yards) are such that holes 1, 2 and 3 could each form a different side of the same right-angled triangle (Triangle A) and that other right-angled triangles could similarly be formed from lengths equal to those of holes 4, 5 and 6 (Triangle B); 7, 8 and 9 (Triangle C); 1, 4 and 7 (Triangle X); 2, 5 and 8 (Triangle Y) and 3, 6 and 9 (Triangle Z).
Moreover, the total length of the three holes forming Triangle A, the total length of the three holes forming Triangle B, and the total length of the three holes forming Triangle C could similarly form the three sides of another right-angled triangle (Triangle ABC) while yet another right-angled triangle could similarly be constructed from the total lengths of the holes forming triangles X, Y and Z (Triangle XYZ).
In triangle ABC the sides would be in the ratio 5:3:4.
The length of each of the par 3 holes is between 150 and 250 yards (one being 168 yards); the par 4 holes are between 250 and 450 yards; and the par 5 holes are between 475 and 600 yards (one being 476 yards).
What are the lengths of holes 2, 6 and 7?
This puzzle is included in the book Sunday Times Brain Teasers (1974).
[teaser454]
GeoffR and 
John Crabtree and 
Frits, 
S2T2 
Jim Randell 8:15 am on 25 February 2019 Permalink |
Although the given number (let’s call it N) is large (it is 36,306 decimal digits), it is not too large for Python to cope with.
We need to find the smallest whole number n that does not divide N. This is a much smaller number.
The following Python program runs in 107ms.
Run: [ @replit ]
from enigma import (irange, inf, printf) # construct the large number N x = 6**6 N = (6**x) - (x**6) # find the smallest number that does not divide it for n in irange(2, inf): if N % n != 0: printf("n={n}") breakSolution: There were 17 battles.
(N mod 17) = 14, so the best the evil horde could manage would be 16 armies the same size and 1 army that had 3 fewer demons.
LikeLike
Jim Randell 4:46 pm on 2 March 2019 Permalink |
We can use the technique given in Enigma 1494 to compute the residues of large powers without the need to construct the huge numbers.
The internal runtime for the following program is significantly less than the simple program given above (169µs vs. 961µs for the program given above). Although in practise both programs run instantaneously.
from enigma import (irange, inf, printf) # compute a^b mod n def mpow(a, b, n): s = 1 while b > 0: (b, r) = divmod(b, 2) if r > 0: s = (s * a) % n a = (a * a) % n return s # N = 6^x - x^6 x = 6**6 # find the smallest number that does not divide it for n in irange(2, inf): # find the residue N mod n if mpow(6, x, n) != mpow(x, 6, n): printf("n={n}") breakUsing the 3-argument version of the Python builtin [[
pow()]] instead of [[mpow()]] gets the internal run time down to 40µs.For a manual solution we can use “the difference of two squares” method to express the number as:
From which it is easy to see that N will have a large number of factors of 2 and 3, and the fact that any power of 6 ends in a 6 means that the difference of two powers of 6 will end in a 0, so it will also be divisible by 5.
So we can start by considering the primes: 7, 11, 13, 17, 19, 23 when looking for a suitable n.
When evaluating mpow(6, x, n) the exponent can be reduced modulo (n − 1) (as n is prime) using Euler’s Theorem, and we can always evaluate the mpow(x, 6, n) in 3 iterations.
In the end we don’t even need to consider all these primes in order to get the answer, so we can arrive at the solution with only a modest amount of calculation.
LikeLike
Jim Randell 12:14 pm on 3 March 2019 Permalink |
Here’s my complete manual solution:
Writing:
We can start to examine divisors:
For n = 2, it clearly divides the (6^36) term. Similarly for n = 3, 4, 6, 8, 9, 12, 16, ….
For n = 5, it doesn’t divide the (6^36) term, so let’s consider the value of (6^23310 mod 5):
5 is prime, so we can use Euler’s Theorem to reduce the exponent mod (p − 1):
And if (6^23310 mod 5) = 1 then 5 divides the (6^23310 − 1) term.
For n = 7, we consider the value of (6^23310 mod 7):
So 7 divides the (6^23310 − 1) term.
For n = 10 we already know 2 divides the (6^36) term and 5 divides the (6^23310 − 1) term.
For n = 11:
So 11 divides the (6^23310 − 1) term.
For n = 13:
And 12 is equivalent to −1 mod 13, so 13 divides the (6^23310 + 1) term.
For n = 14, we already have divisors of 2 and 7.
For n = 15, we already have divisors of 3 and 5.
for n = 17:
9 is not equivalent to +1 or −1 mod 17, so 17 does not divide any of the terms, and gives our solution.
LikeLike