New Scientist Puzzle 73 – Changing Guard
by Rob Eastaway
From Issue #3296, 22nd August 2020 (link)
Fifteen members of the King’s 99th Dragoons are standing on parade. “Right turn!” screams the sergeant, and each soldier makes a 90° turn. Unfortunately, many of the squad struggle to know their left from their right. After this manoeuvre, five soldiers end up facing left, including Private Perkins, who is in the middle of the row.
X X X X X X X P X X X X X X X
Any soldier that ends up face to face with another soldier now does a 180° turn. This awkward ritual continues until no soldier can see another soldier’s face.
Can we be sure that Perkins will end up facing the right way?
One Comment
Leave one →
-
Brian Gladman permalink12345678910111213141516171819202122232425262728293031323334from itertools import combinations# repeatedly scan the line of soldiers for facing# pairs and reverse them until a stable position# is reacheddef faceoff(ln):nd = len(ln) - 2while True:i, ch = -1, Falsewhile i < nd:i += 1# if we find a facing pair reverse them bothif ln[i] and not ln[i + 1]:ln[i:i+2] = [False, True]i += 1ch = True# exit if the configuration is stableif not ch:returnsol = set()# choose four non-middle positions for soldiers facing leftfor c in combinations(range(15), 4):if 7 not in c:# set up the line of soldiers with True for facing right# and False for facing leftln = [x not in c + (7,) for x in range(15)]# remove all facing pairs as specifiedfaceoff(ln)sol.add(ln[7])print('Yes' if len(sol) == 1 and sol.pop() else 'No')