All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars    
perplexus dot info

Home > General
Star of David (Posted on 2005-09-20) Difficulty: 2 of 5
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.

See The Solution Submitted by pcbouhid    
Rating: 4.0000 (4 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
Solution re: Accomplishing the goal | Comment 2 of 10 |
(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
Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (2)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2017 by Animus Pactum Consulting. All rights reserved. Privacy Information