slider puzzle with a twist
Amir Michail
Here is a slider puzzle that I thought of a while ago.
You are given an array of n x n 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 the goal is achievable if and only if the sum of the numbers
in the initial configuration is congruent to 0 mod n.
Amir
Patrick Hamlyn
Not exactly puzzling... operations 1 & 2 don't affect the sum, ops 3 & 4 each
add n to the sum... kinda obvious innit?
Amol V. Deshpande
=>am...@cs.washington.edu (Amir Michail) wrote:
=>>Here is a slider puzzle that I thought of a while ago.
=>>You are given an array of n x n 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 the goal is achievable if and only if the sum of the numbers
=>>in the initial configuration is congruent to 0 mod n.
=>Not exactly puzzling... operations 1 & 2 don't affect the sum, ops 3 & 4 each
=>add n to the sum... kinda obvious innit?
'Only if' is quite obvious, but I think 'if' part is not exactly obvious.
SPOILER AHEAD (maybe)
Rotate all the columns so that the highest entries are at the bottom.
Add sufficient 1's to all the columns so that all the elements
in the bottom row (which are highest in each column) are equal.
Lets call it K.
Do the same with rows now so that the highest entries are to the right.
Add sufficient 1's to make them K as well.
Repeat :
Find the highest entry in the matrix not equal to K, lets say N.
Add K - N to the corresponding column and K - N to the corresponding
row to make this entry equal to the largest entry in that column and
that row (the highest entry now will be 2K - N).
Add sufficient 1's to the remaining rows and columns to make all
the bottom row elements and rightmost column elts all 2K - N.
At the end, we will have a matrix with all elements equal except for
the element in the rightmost column and bottom row (that will remain
at K).
If all other entries are K', let m = (K' - K)/n.
Add m to the bottom row. Rotate the bottom row by 1 and add
m to the column and continue.
In the end, all the elements will be K + (m+1) * n = K' + m.
Note that m is defined because K' - K is 0 mod n.
Amol.
Nick Wedd
Deshpande <am...@barstow.CS.Berkeley.EDU> writes
>'Only if' is quite obvious, but I think 'if' part is not exactly obvious.
>
>SPOILER AHEAD (maybe)
>
< Amol's spoiler snipped >
Add 1 to each column in turn, while rotating the top row so that the
same top-row cell is always the one added to.
Then subtract 1 from each row except the top one.
The net effect is to add n to a single cell.
Nick
--
Nick Wedd ni...@maproom.co.uk
Patrick Hamlyn
>Add 1 to each column in turn, while rotating the top row so that the
>same top-row cell is always the one added to.
>
>Then subtract 1 from each row except the top one.
>
>The net effect is to add n to a single cell.
'subtract 1' is not an allowed operation. You can work around that, but how does
adding n to a single cell help us?
Nick Wedd
<pa...@multipro.NOcomSPAM.au> writes
>Nick Wedd <Ni...@maproom.co.uk> wrote:
>
>
>>Add 1 to each column in turn, while rotating the top row so that the
>>same top-row cell is always the one added to.
>>
>>Then subtract 1 from each row except the top one.
>>
>>The net effect is to add n to a single cell.
>
>'subtract 1' is not an allowed operation. You can work around that
>, but how does
>adding n to a single cell help us?
It doesn't. My mistake.
matthew g hudelson
On Mon, 15 Nov 1999, Amir Michail wrote:
> Hi,
>
> Here is a slider puzzle that I thought of a while ago.
>
> You are given an array of n x n 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 the goal is achievable if and only if the sum of the numbers
> in the initial configuration is congruent to 0 mod n.
>
> Amir
>
I don't claim this is the most elegant way to do this, but it gets the job
done.
The forward direction is easy. Let L(M) be the sum of the entries in M.
Modulo n, the quantity L(M) is unaffected by any of the above operations.
Since the desired configuration M', where the entries of M' are all equal,
satisfies L(M') = 0 mod n, any starting configuration M that can reach M'
must also satisfy the requirement L(M) = 0 mod n.
For the backward direction, we need a lemma.
Lemma. If 1<=p<=n, then any p entries can be maneuvered into
the same row by a sequence of operations taken from (1) and (2).
Proof of Lemma. The result is obviously true for p=1. Suppose the result
is true for p<n. We want to show that p+1 entries can be maneuvered into
the same row. Maneuver any p of the p+1 entries into the same row. If
the (p+1)st entry is in that row, we're done. Otherwise, rotate the row
it is in until it is in a column not containing the other p entries.
Finally, rotate the column the (p+1)st entry is in until it is in the row
with the other p entries, completing the induction.
Proof of the backward direction.
Suppose the backward direction of the theorem is false and let X be the
set of counterexample matrices. For any such counterexample M, define
F(M) to be the maximum entry of M, f(M) to be the minimum, and
G(M) = F(M) - f(M). Let Y be the subset of X where G(M) is minimized.
Let H(M) be the number of minimal entries of M. Choose a matrix K in Y
such that H(K) is minimized. If H(K)>n, then we can maneuver n of these
entries into the same row, add one to this row and obtain a matrix K' such
that G(K')=G(K) and H(K')<H(K) which contradicts the choice of K. So,
H(K)<=n.
Suppose the number of non-maximal entries of K is greater than or equal to
n. Maneuver the minimal entries and enough non-maximal entries into a
single row containing no maximal entries. Adding one to this row, we
obtain a new matrix K' such that G(K')<G(K).
If the number of non-maximal entries of K is less than n, we note that
G(K)>1, since otherwise the sum could not be zero modulo n. We maneuver
these into a single row, add one to every column containing these entries,
as well as adding one to the row containing these entries. The result is
also a new matrix K' such that G(K')<G(K), as the new maximum entries are
one larger than that of K, while the new minimum entries are two larger
than those of K. Notice that entries not added to are now one less than
the new maximal entries. (This is why we needed G(K)>1.)
The upshot is that K' satisfies G(K')<G(K) and so K' is not in X.
Therefore, K' can be reduced to a matrix whose entries are all the same.
Thus, so can K, via reduction to K', which is a contradiction since K was
chosen from X.
>
>
>
Glenn
:>>>Here is a slider puzzle that I thought of a while ago.
:>>>You are given an array of n x n 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 the goal is achievable if and only if the sum of the numbers
:>>>in the initial configuration is congruent to 0 mod n.
:
:>'Only if' is quite obvious, but I think 'if' part is not exactly obvious.
:
:>SPOILER AHEAD (maybe)
NOT!
:>Rotate all the columns so that the highest entries are at the bottom.
:
:>Add sufficient 1's to all the columns so that all the elements
:>in the bottom row (which are highest in each column) are equal.
:>Lets call it K.
:
:>Do the same with rows now so that the highest entries are to the right.
:>Add sufficient 1's to make them K as well.
:
:>Repeat :
:> Find the highest entry in the matrix not equal to K, lets say N.
:
:> Add K - N to the corresponding column and K - N to the corresponding
:> row to make this entry equal to the largest entry in that column and
:> that row (the highest entry now will be 2K - N).
:
:> Add sufficient 1's to the remaining rows and columns to make all
:> the bottom row elements and rightmost column elts all 2K - N.
:
:>At the end, we will have a matrix with all elements equal except for
:>the element in the rightmost column and bottom row (that will remain
:>at K).
Not unless you are very lucky!
Suppose in the second iteration of your loop, that the highest entry is
in a different row and column, call this entry location B, than the entry
chosen in the first iteration, call this entry location A. Then in the
step where you add sufficient ones to make the bottom row and right column
all equal, you will be adding 1s to row containing A and to the column
containing A which will make the value in location A greater than every
other matrix entry!
Mark J. Tilford
>Hi,
>
>Here is a slider puzzle that I thought of a while ago.
>
>You are given an array of n x n 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 the goal is achievable if and only if the sum of the numbers
>in the initial configuration is congruent to 0 mod n.
>
>
>
[SPOILERS BELOW]
Assuming sum of entries congruent to 0:
Outline:
Step 1:
Get all entries in the matrix congruent to 0 (mod n)
Step 1a:
Get all entries except those in the bottom row congruent to 0 (mod n)
Step 1b:
Get the entries in the bottom row congruent to 0, while maintaining the
status of the other entries (except for the rightmost column, which will
briefly change)
Step 2:
Get all entries equal
1a) Given an element X not originally in the bottom row, which is not congruent
to 0 mod n:
Rotate that column so that X is at the bottom.
Add 1 to the bottom row until X is congruent to 0 mod n.
Rotate the column so that X is in its original position.
This will get X congruent to 0 (mod n), and will not disturb any element not
originally in the bottom row. Repeat until all elements not in the bottom row
are 0 (mod n).
1b)
Repeat the following steps n times:
Add 1 to the rightmost column until the bottom element is congruent to 0 (mod
n), then rotate the bottom row 1 square to the right.
After doing that, all elements originally in neither the rightmost column nor the
bottom row will be 0 mod n (they were that way at the end of 1a and were not
disturbed in this step). All elements in the bottom row will be 0 mod n (they
were set to that during this step, and were not disturbed after being set.
Finally, consider all the elements in the rightmost column, and not the bottom
row. They were all congruent to each other at the end of step 1a. Every time
one was incremented, all were incremented. Therefore they are all congruent to
each other now (let k be this value). Since the sum of all elements of the
matrix was congruent to 0 at the beginning, and none of the operations disturbs
that fact, the sum of all elements of the matrix is still congruent to 0 mod n.
Thus 0 + 0 + 0 ...... + 0 (n^2 - n + 1 times) + k + k + k ... + k (n - 1 times)
is congruent to 0 mod n. So k * (n - 1) == 0 (mod n)
kn - k == 0 ( mod n) ==> k == 0 (mod n)
Therefore all elements in the matrix are congruent to 0.
2)
Suppose that not all elements of the matrix are equal.
Define D := sum over all elements ( That Element - Smallest Element )
Obviously, D > 0, and D == 0 only if all element are equal.
Do the following:
Find an element X which is greater than the smallest element.
Repeat the next line n times:
Add 1 to all rows except the one which contains X, then rotate the column which
contains X 1 square down.
Add 1 to all columns except the one which contains X.
This has the effect of adding n to every square, except the one which contains X.
Thus:
It does not disturb the fact that all elements are congruent to 0 mod n.
It reduces D by n.
It can be done as long as D > 0.
Thus, repeat until D == 0, and you will have a matrix with all elements equal.
Note that element are returned to their original position at the end of each
substep, and that each element is in its original row or column at all times.
Side comment: I think that if you are not allowed to perform operation 3, the
necc. and suff. condition is unchanged, and the same holds for removing
operation 4. If you are not allowed to perform operation 1, I believe the N&S
condition becomes (the sum of all elements in each column is the same for each
column (mod n)).
--
-----------------------
Mark Jeffrey Tilford
til...@cco.caltech.edu
Glenn
>You are given an array of n x n 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 the goal is achievable if and only if the sum of the numbers
>in the initial configuration is congruent to 0 mod n.
I've got an algorithm!
SPOILER WARNING
Break up the solution into two stages.
Stage 1 Goal: Make all of the elements equal to the highest element
except for a single column.
I'll work on the rows from top to bottom. For each row I'll work
left to right. The key to this stage is to leave the rightmost
column available for the necessary shifting of elements.
First row:
Repeat until you've done all the row except the last column.
Find the highest remaining entry and rotate it into the next column.
Add 1s to every element in that column until you bring up the just
placed element up to the maximum.
The remaining rows are solved the same way except that before adding
the 1s to the appropriate column, you rotate all of the previous rows
so that the rightmost column lines up with the desired column. Then
you can safely add the 1s without ruining the previous values. Then you
can rotate the previous rows back and proceed. (you can use a similar
trick to rotate the next element into its correct location).
After adding the 1s to a column, it is possible that there will be more
than one element with the same highest remaining value. There are a
couple of ways to handle this. You could place more than one element
before adding the 1s, you could line up the highest remaining elements
in the free column, add the 1s and then rotate them, or you could simply
do them as before while making sure that you rotate any identical values
out of the way before adding the 1s to a column.
Stage 2 Goal: Finish the puzzle.
First add 1s to the last column until some element becomes as large
as the maximum. If you are extremely lucky, the puzzle is now solved.
If not, then bring all the elements in the last column up the current
maximum, M, as follows. Find some element x in the rightmost column
not equal to M. Repeat until we bring the value up to M.
Add 1 to every element in x's row.
Rotate the rightmost column down one position.
Do the same for each remaining element y in the rightmost column
making sure we initially rotate the column so that y's initial row is
the one just after the last row we added 1s to.
After this step, everything in the rightmost column is M.
Because of modularity, the number of times we added a 1 was a
multiple of n. Therefore, every element in the left n x n-1 block
is equal. So we simply add 1s in the rightmost column to bring all
the elements up to the same value. :-)