12 circular pieces (A-L) white on one side and blue on the other, are arranged in a "Star of David" as shown below, with the white face up.

                          A
                         / \
                        /   \
                 B-----C-----D-----E
                  \   /       \   /
                   \ /         \ /
                    F           G
                   / \         / \
                  /   \       /   \
                 H-----I-----J-----K
                        \   /
                         \ /
                          L

The goal is to turn all the 12 pieces so that they all show its blue side. At any time, you can turn any piece you want, but doing this, all the pieces that are connected to it, must be turned too. That is, if you choose to turn the "A"-piece (so that it becomes blue), the "C"-piece and "D"-piece must be turned too, becoming blue. If next you choose to turn the "E"-piece (so it becomes blue) the "G" and "D"-pieces must be turned too (the "G"-piece becomes blue, but the "D"-piece now becomes white again).

Can you devise a sequence with minimum turns to achieve the goal? Just name the pieces that you should turn; you donīt need to name the pieces that must be turned by the rule.

Iīm not forbidding using a computer (in fact, I canīt) but those who do, please give the others some time before posting a solution obtained by this way.

(In reply to Accomplishing the goal by Charlie)

As any solution to any change of configuration can be reduced to 12 yes/no decisions as to whether to do a particular move (A, B, C, ... , K, L), there are in effect 2^12 effectively distinct combinations of moves.

The question can then be asked if any given configuration can be obtained by more than one of these distinct combinations of moves.  As there are also 2^12 possible ending configurations, if any configuration is obtainable by more than one set of moves, then, by the pigeonhole principle, there must be some unattainable final configurations.  So to prove that no final configuration (including that of all the pieces flipped) has more than one elemental solution (i.e., each move made no more than once), all we have to do is show that all final configurations are possible.

We've already shown that each outer point (A, B, H, L, K and E) is individually selectable for winding up flipped.  We only showed that the inner hexagon's vertices can be pairwised flipped.  Here is a combination of moves that will ultimately flip just one inner hexagon vertex:

ABC flips just vertex C.

Thus any configuration of the possible 2^12 is achievable.  As this matches the 2^12 possible reduced (i.e., elementary) sets of moves, there is a 1-to-1 correspondence, and any configuration has only one elementary way of getting there, thus the solution of making each of the 12 possible moves exactly once is the minimal solution, utilizing a total of 48 flips.

Posted by Charlie on 2005-09-20 14:18:45