6
$\begingroup$

My back yard forms a rectangular grid of squares except some of the squares are missing as they are covered by pipes or a small tree. The layout is as follows. A 'x' indicates a square that is free and '.' a covered square.

. x x .
. x x x
. x x x
x x x x
x x x x
x x x x 
x x x x
x x x x
. x x x

I would like write distinct non-negative numbers in each one of the free squares. However, to make it interesting I would like the sums of all the columns to be the same and the sum of the all the rows to be the same (although the row sum need not equal the column sum). We can assume that the value of a covered square is zero.

Is this possible with this layout? If not, why not?

$\endgroup$
  • $\begingroup$ "the row sum need not equal the column sum" Is the opposite possible at all when you have 9 rows and 4 columns???? $\endgroup$ – klm123 Jul 30 '14 at 19:23
  • $\begingroup$ @klm123, no. Suppose r rows and c columns, r > c, are such that row sums = column sums = t. Then both of rt and ct equal the total of all numbers, but rt > ct, a contradiction $\endgroup$ – James Waldby - jwpat7 Aug 9 '14 at 4:20
7
$\begingroup$

Yes, this is possible:

.   54  58  .
.   38  34  40
.   36  44  32
46   4   2  60
48  27  12  25
50  29  22  11
52  30  14  16
56  26  24   6
.    8  42  62

Each column sums to 252; each row 112. And this is certainly not the only solution, just try tweaking the odd numbers up and down a bit.

To figure this out, I started with a spreadsheet with the grid, with equations for the sums around the border, and a list of numbers 1-31 (# of empty squares). I calculated the minimum total sum (504), and figured out how much each row and column should sum to given that total (56/126). I then placed numbers from the list into the empty spaces, shorter rows/cols first, until there were no more possibilities (for me, this left empty spaces where the 27-12-25/29-22-11 is). Then I doubled the value of each square and the expected totals. That gave me 6 even numbers and all the odds to work with; checking the missing sums showed that both the 3 missing numbers in each of the two rows and the two in each column must sum to even numbers, so the columns must be even-even or odd-odd and the rows must have two odd and one even. Looking over the available evens and the required sums, the 12-22 combination fit where it is, and it was trivial then to find four odd numbers to fit in the remaining spots.

$\endgroup$
  • $\begingroup$ That's great! I would now like to find a solution with minimum overall sum . Do you think there is much room for improvement there? $\endgroup$ – Lembik Jul 31 '14 at 8:44
  • $\begingroup$ I'm pretty sure there is room for improvement, but I'm not sure how to go about proving a minimum. $\endgroup$ – Kevin Aug 1 '14 at 18:06
9
$\begingroup$

I have found a minimal solution.
First of all, the puzzle asks for $31$ distinct non-negative numbers. If we take $0$ as a non-negative as well, the $31$ smallest integers are $0 - 30$ and they sum up to $(30*31)/2 = 465$. Now, it should be possible to divide this grand sum through both $4$ and $9$ and that is not possible with $465$. We need a multiple of $36$ and the first after $465$ is $468$, so this is the smallest possible grand total.

I wrote a simple backtracking algorithm, which took a few hours to come to the following solution:

  . 21 31  .
  .  0 22 30
  .  1 24 27
 14 15 10 13
 23 20  2  7
 25 18  3  6
 26 12  5  9
 29 11  4  8
  . 19 16 17

Now, this solution is still very early in the search tree, and I already found two more solutions that look a lot like this, so I assume there will be plenty more solutions. I cannot tell you how many though, that will take a little rewriting the algorithm and a lot more time.

$\endgroup$
  • $\begingroup$ That is very impressive. $\endgroup$ – Lembik Aug 2 '14 at 17:12
-1
$\begingroup$

Assuming that 0 counts as "non negative" a solution with a much lower sum is possible:

 .  2  2  . 
 .  1  1  . 
 .  1  1  2 
 1  2  1  0 
 2  1  0  1 
 2  0  1  1 
 2  1  0  1 
 2  1  1  0 
 .  0  2  2 

Each row adds up to 4, each column to 9. I started by placing two numbers (2 and 2) in the top row and filling the left most column with 2s too and then filling each row that belongs to the leftmost column with 1 0 1//1 1 0//0 0 1. However, the 3 rows left required 12 in sum to be satisfied, and the columns required 16. By shifting a sum of 1 from the left most column to the right columns, each row required 1 less to be satisfied, while 1 more was already placed in the middle rows. Therefore, colums and rows each needed 12 in sum to be satisfied. Then I just filled up the empty spaces, which was more a random process and quite easy.

$\endgroup$
  • 3
    $\begingroup$ Each non negative number needs to be distinct. $\endgroup$ – kaine Jul 31 '14 at 13:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.