wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> hard >> "Slider Puzzle With A Twist"
        
(Message started by: william wu on Jun 23^rd, 2003, 2:44am)

Title: "Slider Puzzle With A Twist"
Post by william wu on Jun 23^rd, 2003, 2:44am

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

Title: Re: "Slider Puzzle With A Twist"
Post by towr on Jun 23^rd, 2003, 3:11am

one side of it is easy,
[hide]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.[/hide]

Title: Re: "Slider Puzzle With A Twist"
Post by James Fingas on Jun 23^rd, 2003, 9:32am

Here's an approach that should convince everybody it's possible, even if it's not a rigorous proof:
[hide]
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?
[/hide]