Different approaches
- Problem 1: Several tumblers are placed in a line on a table. Some are upside down, some are right way up. It
is required to turn all the tumblers right way up. The only allowed move is to turn any two tumblers simultaneously.
From which initial states of the tumblers is it possible to turn all the tumblers the right way up?
- Free style: It does not make sense to flip a tumbler that is turned right way up. Since the only legal move is
to flip two tumblers at a time, the only way all tumblers can end up right way up is to have even number of tumblers
in upside down position.
- Disciplined: Let U be the number tumblers turned right way up. Let D be the number of tumblers turned upside down.
The pair (U, D) denote the state of the tumbler line up. The desired result is to have (U=n, D=0), where 'n' is the number of tumblers. Given
that the only allowed move is to flip two tumblers at a time, the possible moves are:
Possible actions:
- Move 1: Flip two tumblers that are already right way up. The effect is: (U, D) → (U-2, D+2)
- Move 2: Flip two tumblers that are upside down. The effect is: (U, D) → (U+2, D-2)
- Move 3: Flip two tumblers that are in opposite states. The effect is: (U, D) → (U, D)
The difference between the initial state and the resulting state (because of a move is) +/- 2 for U and -2 or 0 for D. Since the desired state
final state is to have D=0, move 3 and 1 won't be of much help. Move 2 should be the choice every time. Since this move changes D by -2, the initial
parity of D is maintained. Hence the only way the final state (D=0) can be achieved is to have Dinitial to have even parity.
Observations:
- It is also clear that the state of the tumblers (in this problem) could have been represented just by D [Abstracting].
- Given the rational move (Move 2), the problem is almost like having only cups turned upside down and target goal being to reduce it to zero.
- Problem 2: Eleven large empty boxes are on a table. In certain number of large boxes eight medium boxes are placed. In certain number
of medium boxes eight small boxes are placed. In the end there are 102 empty boxes. How many boxes are there in total?
- Disciplined (but detailed): Let X (≤ 11) be the number of large boxes selected. Each of the X boxes get eight medium boxes. After this step the
total number of empty boxes are: 11 -X + 8*X. Let Y (≤ 8*X) be the number of medium boxes selected. Each of these Y boxes get eight small boxes. After this
step the total number of boxes are:
- 11 - X + 8*X -Y + 8 * Y = 102
- → 7 * (X+Y) = 91
- → X+Y = 13
- Goal: 11 + 8*X + 8 * Y = 11 + 8 * 13 = 115
- Disciplined (but using right level of abstraction): The problem gives the final empty box count. Certain number of boxes are filled. The problem asks for the total number of boxes. Let 'e' be
the number of empty boxes and let 'f' be the number of filled boxes. The problem asks for e+f at the end of the specified action sequence.
- Given: einitial = 11, finitial=0; efinal =102. Goal: efinal+ffinal
- At every step (assuming X boxes are chosen to be filled): e' := e + 8* X -X and f' := f + X . This gives: e'-7*f' = e-7*f. At every step, e-7*f remains the same [Invariant]
- Since einitial-7finitial= 11, efinal-7*ffinal is 11. ∴ 7*ffinal = efinal-11 = 91. ∴ ffinal=91/7=13
- Goal: efinal+ffinal = 102+13=115
Observations:
- Right level of abstracting (dropping the details of medium box, small box and which boxes are filled etc), helps in keeping the state representation simple.