perplexus.info :: General : Penny Parity

Penny Parity (Posted on 2013-07-18)

Consider n pennies arranged in a straight line.

A move consists of taking a penny and turning it over (from head to tail or visa versa) and of doing the same to each of its neighbors.

If the penny happens to be at the end of the line, then it will have only one neighbor. For example, if the sequence is HHTH and you choose the 3rd penny, then your move would result in HTHT.

The question is, given any sequence of n pennies, is it possible to find a sequence of moves to bring it to all Heads? Show that the answer is no for n=5 but yes for n=6.

No Solution Yet Submitted by Danish Ahmed Khan

Rating: 3.0000 (1 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)

re: An algorithm

Comment 4 of 4 |

(In reply to An algorithm by Brian Smith)

The algorithm which Brian describes always works if n mod 3 is 0 or 1.

It will not always work if n mod 3 is 2, because in this case the 2nd step causes every penny to be turned twice. In other words, the 2nd step makes no change if n mod 3 is 2.

There is in fact no algorithm which will always work for n mod 3 = 2. This can be proven using an obvious extension of the parity argument I made for n = 5

Posted by Steve Herman on 2017-07-25 13:00:54

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 (0)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:


perplexus dot info