Brain-Teaser 457: [March-past]
From The Sunday Times, 15th February 1970 [link]
The Duke of Teresa and Baron von Barin agreed to have a march-past of their respective men-at-arms to celebrate the wedding of the Duke’s son with Baron’s daughter. Each troop would march past in column of three (i.e. 3 men per file). The Duke has a few thousand men and the Baron about half as many.
On the appointed day however, one of the Duke’s men could not go on parade and so the men were ordered into column of four, but 3 men were left over, whereupon they formed column of five and 4 men were left over, and this pattern of behaviour persisted as the Duke consecutively increased the number per file until all the men made an exact number of files.
Meanwhile, the Baron has the same problem. One man reported sick and he consecutively increased the number per file and in column of four had 3 left over, column of five had 4 left over, etc., and eventually he reached a number per file that left no man spare.
The Baron’s men proceeded to march past but the Duke was in a dilemma as each body of troops had a different number of men per file. He immediately solved this by ordering his men to form files with the same number of men as the Baron’s. This they did without any men being left over.
How many men respectively had the Duke and the Baron on parade?
This puzzle was originally published with no title.
[teaser457]
S2T2 
Jim Randell 2:09 pm on 28 February 2019 Permalink |
The total number of men (including the indisposed man) must be able to form 3, 4, 5, … lines, if they are unable to form lines when one of them is missing, being short by one man.
So, if we can form 3, 4, 5, … lines, the total number of men must be a multiple of 3, 4, 5, …, i.e. a multiple of lcm(3, 4, 5, …).
This Python program looks for possible total numbers of men for the Duke D and the Baron B, and then finds the solution where the ratio D/B is closest to 2. I assumed the Duke had somewhere between 2,000 and 10,000 men. The program runs in 84ms.
Run: [ @repl.it ]
from itertools import count, combinations from collections import defaultdict from enigma import irange, mlcm, fdiv, Accumulator, printf # suppose the number of men (n - 1) end dividing into k equal sized lines (k > 6) # for all lowers numbers they are one short, so n must be a multiple of all lower numbers # minimum/maximum numbers to consider for D (m, M) = (2000, 10000) # record lcms up to M by k d = defaultdict(list) for k in count(7): n = mlcm(*irange(2, k - 1)) if n > M: break d[k] = n # choose the result with D/B nearest to 2.0 r = Accumulator(fn=(lambda x, y: (x if abs(x - 2.0) < abs(y - 2.0) else y))) # choose k's for D and B (kD < kB) for (kD, kB) in combinations(sorted(d.keys()), 2): (mD, mB) = (d[kD], d[kB]) # the Duke has "a few thousand men" for D in irange(mD, M, step=mD): if D < m: continue # (D - 1) is divisible by kD and kB if not ((D - 1) % kD == 0 and (D - 1) % kB == 0): continue # the Baron "about half as many" for B in irange(mB, M, step=mB): # (B - 1) is divisible by kB if (B - 1) % kB != 0: continue # output the solution (the numbers on parade are B-1, D-1) r.accumulate_data(fdiv(D, B), (D - 1, B - 1)) printf("kD={kD} kB={kB}, mD={mD} mB={mB}, D={D} B={B} [D/B ~ {f:.3f}]", f=fdiv(D, B)) # output the solution (D, B) = r.data printf("parade: B={B}, D={D}")Solution: The Duke had 5159 men on parade. The Baron had 2519 men on parade.
The ratio D/B is approximately 2.05.
The Duke’s men are one man short of forming 3, 4, 5, 6 lines, but can form 7 lines (5159 = 737 × 7).
The Baron’s men are one man short of forming 3, 4, 5, 6, 7, 8, 9, 10 lines, but can form 11 lines (2519 = 229 × 11).
The Duke’s men can also form 11 lines (5159 = 469 × 11).
There is a further solution where the Duke has 9779 men on parade (and the Baron still has 2519), but in this case the D/B ratio is 3.88.
If we allow the Duke and the Baron more men then we can get the ratio closer to 2. There is a solution with D=60599 and B=30239, giving a ratio of 2.004, but it is hard to describe 60,600 men as “a few thousand”.
LikeLike