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

Home > Just Math
Tile flipping (Posted on 2015-04-08) Difficulty: 3 of 5
A puzzle consists of a number of tiles, T, colored red on one side and blue on the other.

Start with all red side up. The goal is to get them all blue side up in the fewest number of rounds.
A round consists of flipping exactly N of them.

Find a rule for when the puzzle is impossible for given values of (T,N) with N≤T.

Find a rule for the number of rounds it will take when the puzzle is possible.

No Solution Yet Submitted by Jer    
Rating: 4.0000 (2 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
Some Thoughts No Subject Comment 12 of 12 |
If N is odd then flipping N tiles will change the number of blue tiles by an odd number in the interval [-N,N].  Similarly if N is even then flipping N tiles will change the number of blue tiles by an even number in the interval [-N,N].

If T is odd and N is even then the goal is impossible to achieve due to parity.

In any other case, let Q = floor(T/N) and R = T mod N.

For the case R=0, there will be Q rounds of flipping N tiles from red to blue.

If N is even and R is odd: this is the impossible case.

If N and R are both odd and Q>=2:  The goal can be achieved by Q rounds of flipping N tiles red to blue plus 1 round of flipping (N+R)/2 red to blue plus (N-R)/2 blue to red.  The mixed round cannot be the first or last round
For example if T=33 and N=7 then Q=4 and R=5.  4 rounds of flipping 7 red to blue and 1 round of flipping 6 red to blue with 1 blue to red.

If N and R are both even and Q>=2:  The same strategy as the previous case works.
For example if T=50 and N=8 then Q=6 and R=2.  6 rounds of flipping 8 red to blue and 1 round of flipping 5 red to blue with 3 blue to red.

If N is odd and R is even and Q>=3:  A variant of the above strategy works:  Q-1 rounds of flipping N tiles red to blue, plus 1 round of flipping (N+1)/2 red to blue with (N-1)/2 blue to red, plus 1 round of flipping (N+R-1)/2 red to blue with (N-R+1)/2 blue to red.
For example if T=24 and N=5 then Q=4 and R=4.  2 rounds of flipping 5 red to blue, one round of flipping 3 red to blue with 2 blue to red, and one round of 4 red to blue with 1 blue to red.

This takes care of all 'large' values of Q.  In all these cases the theoretical minimum of Q (when R=0) or Q+1 (when R>0) is achieved.  I still need to resolve the cases with Q = 1 or 2.

  Posted by Brian Smith on 2016-11-15 10:49:44
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