Enigmas and puzzles

June 29, 2007

Colorado Smith batted away a war-axe as it spun past his left ear, and consulted a tattered leather-bound notebook.

"Only the Procession of a Hundred Sphinxes to traverse," he said. "Then we can enter the temple of Beth-Shimmeroth and find the priceless emerald idol."

"What do we have to do?" said his sidekick Brunnhilde, looking at the long line of crocodile-headed sphinxes arrayed in single file alongside the paved path that led to the temple.

"You have to run down the procession 100 times," Smith explained, ducking a javelin, "while I keep the natives at bay. The first time, you touch every sphinx. Then you come back here, run down the procession again, and touch every second sphinx. You do the same for every third sphinx, and so on, until on the final pass you touch only the hundredth sphinx."

"Sounds suspiciously easy. There must be more to it than that."

"Yes. When you first touch a sphinx, its head will glow with an unearthly blue light. Touch it a second time and the glow will disappear. Touch it again, the glow will come back, and so on," said Smith. "But before you start, I have to place a number of sacred stones in this receptacle, That number has to be equal to the number of sphinxes that are glowing after you have made your hundredth run. If I get the number right, the temple door will open."

"And if you get it wrong?"

"You don't want to know. Believe me. Very messy."

How many sacred stones should Smith place in the receptacle?


Scroll down for the answer


The answer
Smith should put ten stones in the receptacle.  The n th sphinx changes state (on to off or vice versa) on the
dth run if and only if n is exactly divisible by d. So the number of changes of state is equal to the number of divisors of n.  Sphinx n ends up glowing if this number is odd, but does not glow if it is even. But n has an odd number of divisors if and only if n is a perfect square—a pattern that quickly emerges if you experiment. (It is also fairly straightforward to prove this.) The perfect squares that arise are 1, 4, 9, 16, 25, 36, 49, 64, 81, and 100. So those are the sphinxes that end up glowing, and there are ten of them.

The winner is Gess Laving from Dorking, Surrey