The Robostanchion Exam (a puzzle about game-graph connectedness)

Question

The St. Čapek Crowd Control Academy, June, 2115.

Commander Gall is worried. On one hand, the graduating class this year is the most promising in the institution's history, every cadet's reasoning skills honed to perfection. On the other, General Domin is visiting and has insisted on writing and administering the robostanchion exam himself, despite the fact that robostanchion squads as a crowd-control technique came after his time, and he doesn't always grasp their limitations.

Fortunately, the format of a robostanchion exam is fairly standardized: a cadet takes control of a squad chosen for them by the examiner, all robostanchions initially inactive and in the hangar, and must maneuver it into a formation given by the examiner. There are only three kinds of commands that a cadet can issue:

• A cadet can deploy an inactive robostanchion, commanding it to teleport itself to any unoccupied point on the field—which happens to be an infinite integer lattice—and become active.

• A cadet can move an active robostanchion, commanding it to teleport to a different, unoccupied point on the field. The robostanchion remains active.

• A cadet can recall an active robostanchion, commanding it to teleport back to the hangar and become inactive.

Their primary function being crowd control, whenever two active robostanchions are adjacent, they automatically establish a laser barrier between themselves:

Laser barriers require power to maintain, which must be drawn from some active robostanchion's power supply; each robostanchion has just enough power to maintain one barrier, but it may share this power wirelessly. For example, the six robostanchions on the right side of this formation may use the left robostanchion to power their seventh barrier:

Ordinarily, there are only two ways to fail a robostanchion exam: (1) damaging the squad by running out of power or (2) not achieving the requested formation within the generous time limit. Now the general, to gratify his ego, has decided that his version of the exam should be more challenging, and he has added (3) ever not using all of the available power.

Commander Gall, appropriately mortified, has, after much obsequious persuasion, gotten the general to agree to some concessions. First, the general will allow cadets four commands before he enforces his additional requirement. Second, the general has agreed to only ask for connected formations, i.e., formations where every robostanchion is joined to the others by at least one laser barrier.

While further promises from the general are improbable, there is one more fact working in the cadets' favor: To prevent cheating, school policy is that cadets are always given squads of distinct sizes. For instance, if one cadet makes the exam with a squad of 90, no other cadet will have exactly 90 robostanchions at their command.

Unsure whether these facts are enough to contain the general's caprice, Gall consults with Chief Engineer Fabry, asking for a worst-case analysis. What does Fabry reply? That is, in the worst case possible, how many cadets can Gall expect to fail?

Clarifications: General Domin is sensible enough not to ask for formations that require more robostanchions than are in the squad, nor for formations that violate his condition (3).

Answer 1

In the worst case, the number of cadets who fail will be

one. The only impossible formation is a $3\times3$ square of robots with the center removed.

Since all legal moves after the first four are reversible, in order to show a formation can be created from nothing, it suffices to show that it can be reduced to a small square of four robots.

Call a robot with exactly one robot next to it a loner. We first show that any formation with loners can be reduced to a small square. Starting with such a formation, remove all loners, and continue removing newly created loners until there are none. What remains is a loop. Unless the formation is now a small square, the top edge of the formation must have 3 robots in a row, say at (0,0), (1,0) and (2,0). Deploy one of the removed robots to (1,1), then move (0,0)'s other neighbor to (0,1). This creates a small square of robots: after removing all loners until there are none, only this square will remain.

So, assume there are no loners. Suppose without loss of generality that the lowest row in the formation has a $y$-coordinate of $0$, and on that row, the lowest $x$ coordinate is $0$. This implies that there are robots at (0,0), (1,0), and (0,1). If there is a robot at (1,1), that means we have the small square, so assume there isn't one. Furthermore, (1,0) can't have his second neighbor to the south, so there must be a robot at (2,0).

There are several cases:

Case 1: Neither (2,1) nor (1,2) have a robot. Move (2,0) to (1,1). This means that (2,0)'s old neighbor at (3,0) will now be a loner, so the formation is now reducible.

Case 2: Exactly one of (2,1) or (1,2) has a robot. Move that robot to (1,1). The moved robot's two neighbors are now loners.

Case 3: Both (1,2) and (2,1) have robots.

(1,2) must have two neighbors. If they are both at (0,2) and (2,2), then this is the bad formation, so assume that only one of (0,2) and (2,2) is filled. By symmetry, we can assume (0,2) is unfilled. This means that the other neighbor of (0,1) must be at (-1,1). If there was a robot at (-1,0), that would mean there was a small square of four robots, contradicting that the entire formation was a loop. So, (-1,0) is empty.

There are now two final cases:

Case 3a: (-2,0) has a robot. Move that robot to (-1,0). The two neighbors that (-2,0) had are now loners.

Case 3b: (-2,0) doesn't have a robot. Move (2,0) to (-1,0). The two neighbors that (2,0) had are now loners.

Thus, in all cases except for the $3\times 3$ square without its center, the formation can be made. To see why this formation cannot be made, you can check that no moves can be made from it.

If you were only given the exact number of robots needed, no deployments are possible. No moves are possible: a move destroys two lasers, so it must create two as well, but every spot you can move a robot would make it have 0,1,3 or 4 lasers. Finally, no recalls are possible, since this will destroy two lasers and only one robot.