Eight workstations, six conditions: testing which constraint earns its place
Eight probationary Junior Engineers - A, B, C, D, E, F, G and H - are to be allotted eight numbered workstations in a single row on the shop floor, numbered 1 to 8 from left to right as seen by the supervisor, all facing the supervisor's desk. The placement plan must satisfy six conditions: (i) A is at the left end; (ii) exactly two persons are placed between A and G; (iii) E is immediately to the right of C and immediately to the left of G; (iv) B is second to the left of D; (v) H is immediately to the right of B; (vi) F is at the right end. The supervisor is convinced that all six conditions are needed to fix the layout, while a trainee argues that at least one of them is doing no work at all. Before the allotment is published, a ninth trainee, X, is added, and the supervisor wants X placed so that exactly as many persons sit between X and C as between X and D.
1. Derive the complete workstation layout from the six conditions and verify it against each condition.
Read the worked answer
Work from the most constrained clues rather than guessing.
- (i) puts A at seat 1. (ii) then forces G to seat 4, because seats 2 and 3 must lie between them.
- (iii) makes C, E, G a consecutive block ending at G, so C = 2 and E = 3.
- (iv) and (v) together mean B, H, D occupy three consecutive seats in the order B, H, D (H immediately right of B; D two to the right of B). The only free run of three is 5-6-7, so B = 5, H = 6, D = 7.
- (vi) leaves F = 8.
Layout: 1 A, 2 C, 3 E, 4 G, 5 B, 6 H, 7 D, 8 F.
Check: A and G have C and E between them; E sits between C and G; B is second to the left of D; H is immediately right of B; F is at the right end. All six conditions hold, and no seat is left over, so the solution is unique.
2. Identify which single condition can be deleted while the layout remains unique, and prove by counter-example that at least one other condition cannot be deleted.
Read the worked answer
Condition (i), A at the left end, is redundant. Remove it and re-derive from the rest: (ii) allows A at seat 1 with G at 4, A at 2 with G at 5, or A at 7 with G at 4 (allowing E and C to sit to the left of G).
- A = 2, G = 5 gives C = 3, E = 4, and then B, H, D must take three consecutive seats from 1, 6, 7, 8 - and (vi) already holds seat 8, so no run of three exists. Branch dies.
- A = 7, G = 4 gives C = 2, E = 3, and B, H, D must fit 1, 5, 6, 8, again with no run of three available. Branch dies.
Only A = 1 survives, so (i) restates something the other clues already imply.
Counter-example for (vi): drop F at the right end and A = 2, C = 3, E = 4, G = 5, B = 6, H = 7, D = 8, F = 1 satisfies every remaining clue - a second valid layout. Similarly, drop (ii) and C-E-G can slide to 5-6-7 with B, H, D at 2-3-4. So the plan is over-specified by exactly one condition, and it is (i), not (vi).
3. Trainee X must be seated so that the number of persons between X and C equals the number between X and D. Using your layout, decide whether any seat satisfies this, and state what has to change if none does.
Read the worked answer
No seat works as the row stands. C is at seat 2 and D at seat 7, five seats apart, with E, G, B and H - four persons - between them. For equal numbers on each side, X must sit at the midpoint, seat 4.5, which does not exist.
The general condition is that C and D must be an even number of seats apart (an odd number of persons between them). Five is odd, so the requirement is arithmetically impossible, not merely hard. Adding X at either end fails too: at seat 0 the counts are 1 and 6; at seat 9 they are 6 and 1.
Something must move. The cleanest repair is to insert a ninth seat between C and D: everything to the right of the insertion shifts up by one, so C stays at 2 and D moves to 8, and the midpoint becomes seat 5 - that is, X goes between G and B (positions 1 A, 2 C, 3 E, 4 G, 5 X, 6 B, 7 H, 8 D, 9 F), giving two persons on each side. Alternatively, shift C or D by one seat to make the gap even. The trainee should be told plainly that the demand as stated cannot be met.