From Newsgroup: rec.puzzles
On 19/02/2026 19:28, Richard Tobin wrote:
In article <10n40hv$2gkcq$1@dont-email.me>,
David Entwistle <qnivq.ragjvfgyr@ogvagrearg.pbz> wrote:
Each cell of a 30 |u 30 grid contains one of the numbers reA1, 0 or 1 with >> each of these three numbers appearing exactly 300 times.
Is it possible that the 60 row and column sums are all different?
Here's my solution. I'm not confident I haven't got an equality the
wrong way round somewhere.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
Let's consider the general case with side N (divisible by 3) - is it
possible that the 2N sums are all different?
There are 2N+1 possible row and column sums, -N .. +N. Since we want
2N different sums, exactly one possible sum must not occur. The sum
of all the row and column sums must be zero - there are equal numbers
of -1s and 1s - so the missing sum must be zero. The sums are
therefore -N .. -1 and 1 .. N.
Consider the positive sums, without regard for the grid. A sum of k
could be made with k 1s and (N-k) 0s, or it might include some -1s, in
which case it will need that many more 1s to cancel them out. The
total number of 1s needed will be N(N+1)/2 plus the number of -1s that
occur in positive sums.
When we consider the grid, we will need fewer 1s because a given 1 may
occur in both a positive row sum and a positive column sum.
The rows can be arbitrarily permuted without changing the sums, and
likewise the columns, so let's arrange them with the positive row sums
at the top and the positive column sums at the left. This divides the
grid into four parts which we'll call A, B, C, and D, shown here for
N=6:
x x x x | x x +ve
A | B
x x x x | x x +ve
-----------------------
x x x x | x x -ve
|
x x x x | x x -ve
C | D
x x x x | x x -ve
|
x x x x | x x -ve
+ve +ve +ve +ve -ve -ve
Suppose there are t positive row sums, then there must be N-t negative
row sums, and similarly N-t positive column sums and t negative column
sums.
How many 1s do we need in the grid? The 1s in A appear in two sums,
so we need:
Your logic below is clear, and very well presented!
My (final) reasoning gets the result a bit quicker, but it's a bit harder to explain /how/ I arrived
at the solution!
Anyhow, my reasoning matches yours so far. For convenience, I'll let N = 3M, just to simplify
formulas. I aim to show a solution would require more 1s than are available. We examine the 2M
rows/columns that have totals M+1, M+2, M+3, ... 3M-1, 3M. Each of these requires at least that
many 1s, although some of those may be double counted if they're counted in both a row and a column.
Since there are 2M rows/columns being considered, the maximum number of double-countings is M^2,
when we have a balanced row/column split (M rows, M columns) and all M^2 intersection points were
counted +1s. So the grid must contain at least
(M+1, M+2, M+3, ... 3M-1, 3M) - M^2 = M(4M+1) - M^2
= 3M^2 + M
+1s. But there are only 3M^2 +1s available, so the solution is not possible. Er, that's it!
Short and sweet, and as a proof we can just agree it works, but that leaves the question of how I
settled on those particular totals to focus on! The answer (for anyone curious!) is that in
practice I started with smaller numbers and just played around. :)
E.g. with a 30x30 grid I started looking at the two totals 29 and 30. 29+30 = 59, and just 1 cell
of double counting is possible, so we need at least 58 +1s. If we add in 27 and 28, the "sum of
totals" increases by 55 [good!] but the "double counting" possibility goes from 1^2=1 to 2^2=4. So
those 4 rows/cols need 58+55-3 = 110 +1s - we're heading in the right direction!
But if we continue this too far, the gain from the (with-double-counting) sum increase is
overwhelmed by the loss from the increase in possible double counting. E.g. if we examine /all/ the
+1,+2,...+30 rows/cols, the sum 1+2...+30 = 15x31 = 465, but we have to subtract a possible overlap
of 15^2 = 225. If we had missed out the +1,+2 totals, the sum would only have gone down by 1+2=3,
but the possible double counting figure would have gone down from 15^2 to 14^2, i.e. gone down by 29
so our +1s required figure would have been higher by 26. Much better!
So as we examine more of the rows/cols (starting from highest total and working down) the figure we
get for "+1s required" goes up initially, but at some point starts falling when we've gone too far.
At this point I rather unscientifically looked at smaller grids, and saw that the sweet spot seemed
to be around 1/3 of the grid side length. So I looked at the general case of only examining totals
M+1 to 3M and it worked with simple arithmetic. More scientifically, I suppose I might have looked
at the general formula for including the top 2k totals (that's easy to write), and looked at
maximising that value as a function of k, (hopefully) finding the maximum somewhere near k=M. But I
didn't actually do that! :)
Mike.
N(N+1)/2
+ (the number of -1s in B and C) + (twice the number of -1s in A)
- (the number of 1s in A)
which is at least
N(N+1)/2
+ (the number of -1s not in D)
- (the number of 1s in A)
which is at least
N(N+1)/2
+ N^2/3 - (N-t)t [since there are N^2/3 -1s and no more than (N-t)t are in D]
- (N-t)t
(N-t)t <= N^2/4 so it is at least
N^2/2+N/2 + N^2/3 - N^2/2
= N^2/3 + N/2
We need at least N^2/3 + N/2 1s but we only have N^2/3, so it can't be
done.
-- Richard
--- Synchronet 3.21b-Linux NewsLink 1.2