Brain-Teaser 28: Army squares
From The Sunday Times, 1st October 1961 [link]
Kublis Ghen was very particular about his army formations. Originally, each company consisted of a certain number of men who could be drawn up in the form of a perfect square. Nor was this all, for when the companies were drawn up one behind the other (each company being spread out to form a single row) the entire army itself thus constituted a square. It was an army to be proud of, but when the great conqueror determined to attack Thalbazzar he was not content, and summoned his chief of staff: “My army is not big enough”, he declared. “Double it”.
Knowing the temper of his master, the chief of staff saw to it that the size of the army was doubled — exactly. But an unforeseen difficulty arose: the army could no longer form a perfect square — there was just one man too many.
“Kill him”, ordered the conqueror on hearing the news, and the offending supernumerary was duly dispatched, so that the army marched into battle in the form of a square though, of course, its company formations had been completely disorganised.
A million men did Kublis Ghen
Against Thalbazzar thow;says the poet, but that is an exaggeration.
How many men were in the army that Kublis Ghen threw against Thalbazzar?
[teaser28]
John Crabtree and 
S2T2 
Jim Randell 8:58 am on 28 March 2021 Permalink |
If there are k² men in a company, then in order to form a square when each company is in a line there must be as many companies as there are men in a company. So (k²)² men in total.
When the army size is doubled, the remaining number is 1 more than a square:
We can consider possible values of k until (2(k^4) − 1) exceeds 1 million (at k = 27).
This Python program runs in 49ms.
Run: [ @replit ]
from enigma import (irange, inf, is_square, printf) # consider k values for k in irange(1, inf): n = 2 * pow(k, 4) - 1 if n > 1000000: break if is_square(n): printf("k={k} -> n={n}")Solution: There were 57121 men in the army marching into battle.
Each company consisted of 13² = 169 men, which could be formed into a 13×13 square or a 1×169 line.
The 169 companies can then be formed into a 169×169 square = 28561 men in total.
The army size is doubled to 57122 = 239² + 1. And one of these is removed.
So, the army of 57121 men marched into battle as a 239×239 square.
LikeLike
John Crabtree 4:34 pm on 30 March 2021 Permalink |
2x^2 = y^2 + 1 where x is square. y/x is an approximation to sqrt(2).
For 2x^2 = y^2 +/- 1, y/x = 1/1, 3/2, 7/5, 17/12, 41/29, 99/70, 239/169, 577/408, 1393/985 etc
x(k) = x(k-1) + y(k-1). and y(k) = 2 * x(k-1) + y(k-1).
169 = 13^2, and so there were 239^2 = 57121 men in the army.
As a check, 2 * 169^2 = 239^2 + 1
LikeLike