Author |
Topic: "Slider Puzzle With A Twist" (Read 732 times) |
|
william wu
wu::riddles Administrator
Gender: 
Posts: 1291
|
 |
"Slider Puzzle With A Twist"
« on: Jun 23rd, 2003, 2:44am » |
 Quote  Modify
|
You are given an n x n array of integers. The goal is to end up with an array in which all entries are equal.
Four kinds of moves are allowed:
1. rotate a row
2. rotate a column
3. add 1 to all entries in a row
4. add 1 to all entries in a column
Show that the goal is achievable if and only if the sum of the numbers in the initial configuration is congruent to 0 mod n.
Credits: Amir Michael and Ashraf Michail, via e-mail
|
| « Last Edit: Jun 23rd, 2003, 2:45am by william wu » |
 IP Logged |
[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: "Slider Puzzle With A Twist"
« Reply #1 on: Jun 23rd, 2003, 3:11am » |
Quote Modify
|
one side of it is easy,
If all entries have to be equal you can make them all zero as well.
Since you can only add or subtract n to/from the total sum, the sum you start with has to be 0 modula n.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
James Fingas
Uberpuzzler
Gender:
Posts: 949
|
|
Re: "Slider Puzzle With A Twist"
« Reply #2 on: Jun 23rd, 2003, 9:32am » |
Quote Modify
|
Here's an approach that should convince everybody it's possible, even if it's not a rigorous proof:
I will show that it is possible to effect a series of transformations which decrease one number by 1 and increase one of its neighbours by 1, with no other effects. Using this one move, it should be easy to come up with a thousand ways of solving the problem.
Since the board is symmetric with respect to position, we show that we can add one to the top left position while subtracting one from either a) the top next-to-left position or the b) left next-to-top position, with no other effects.
For a):
1) Add one to the first column
2) Rotate the first row left by one position
3) Subtract one from the first column
4) Rotate the first row right by one position
For b), replace "column" with "row" and vice versa.
This may take a lot of operations, though. Any ideas on using a near-optimal number of operations?
|
|
IP Logged |
Doc, I'm addicted to advice! What should I do?
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print