Brainteaser 1343: Mecca bound
From The Sunday Times, 29th May 1988 [link]
When Sheik Abdul heard that some pilgrims were leaving the district and travelling south to Mecca he immediately offered his well-appointed bus so that they could travel in comfort. Unfortunately, there were just too many pilgrims to travel comfortably. Abdul asked them to form a straight line facing south towards Mecca. He explained that he would carry out an operation that would result in some pilgrims facing north. These pilgrims would not go on the bus. Just then, Abdul noticed that his nephews were in the line-up. They occupied the end positions and the centre position.
Abdul went along the line asking each man to make a half-turn. Then he went along the line asking every second man to make a half-turn and so face south again. Next he asked every third man to make a half-turn; if he was facing north, he was to face south, and if he was facing south, he was to face north. And so on, When Abdul went along the line for the last time only the man at the end was asked to make a half-turn. Abdul found that his nephews were all facing north.
“That is only half of the operation”, he announced hastily. We continue and do the same again”. When it was pointed out that all the pilgrims would then be facing south, he said that this time he would start at the other end.
How many of the pilgrims went on the bus to Mecca?
[teaser1343]
Ruud van der Ham and 
Frits, and 
NigelR are discussing. 
Jim Randell 2:48 pm on 21 October 2026 Permalink |
See also: Teaser 3131, Puzzle #08.
This Python program runs in 66ms. (Internal runtime is 379µs).
from enigma import (irange, inf, rev, printf) # apply the process to <ss> def process(n, ss): for k in irange(1, n): # flip every k'th item for i in irange(k, n, step=k): ss[i - 1] ^= 1 return ss # consider odd numbers of participants (so there is a "centre") for n in irange(3, inf, step=2): # start with everyone facing south (= 1) ss = [1] * n # run the process in the forward direction ss = process(n, ss) # all the nephews are now facing north (= 0) if not all(ss[i - 1] == 0 for i in [1, n, (n + 1) // 2]): continue # run the process in the reverse direction ss = rev(process(n, rev(ss))) # count number facing south printf("n={n}: S={S}\n-> {ss}\n", S=sum(ss)) breakSolution: 41 pilgrims went on the bus to Mecca.
There were 49 pilgrims in the queue.
At the end of both operations the pilgrims in positions: 4th, 9th, 14th, 16th, 34th, 36th, 41st, 46th positions are facing north.
These can be paired as follows to give sums of 50 (= 49 + 1):
Where one position (underlined) in each pair is a square number (counting from the start). The other position corresponds to a square number position counting from the end.
The 25th (centre) position, is paired with itself, and so ends up facing south.
The next solutions occur with 1681 pilgrims, and 57121 pilgrims:
If we consider solutions to the Pell’s equation: X² − 2Y² = −1, the we get solutions of the form:
See: OEIS A002315 [@oeis], OEIS A001653 [@oeis].
LikeLike
Ruud van der Ham 3:29 pm on 21 October 2026 Permalink |
import itertools for n in itertools.count(5, 2): p = [True for _ in range(n)] for i in range(n): for j in range(i, n, i + 1): p[j] = not p[j] if p[0] == p[n // 2] == p[n - 1]: for i in range(n): for j in range(i, n, i + 1): p[n - j - 1] = not p[n - j - 1] print("number in line:", n) print("number of pilgrims on the bus:", sum(p)) print("line:", "".join(map(lambda x: "NS"[x], p))) breakLikeLike