You have a 5x5 matrix. The numbers 1,2,3,4 and 5 appear in every row and in every column exactly once....
You are given a 5x5 matrix. The numbers 1,2,3,4 and 5 appear in every row and in every column exactly once. The diagonal from the lower left to the upper right also has the numbers 1,2,3,4, and 5 appear exactly once. Prove that all numbers under the diagonal (10 cells) must have a sum greater than 21.
del
?
WSO > stack overflow / wolfram alpha
True in a way (his question got rejected on stack overflow lmao)
Cuz he already asked for stock pitch ideas on stack overflow
Try to find the arrangement that minimizes the sum. If you can show that this minimum arrangement is above 21, then you're set
A better way to think of it might be to show that you already exceed 21 in a scenario with only two of the constraints:
Consider this picture:
5 5 5 5 5
4 4 4 4 4
3 3 3 3 3
2 2 2 2 2
1 1 1 1 1
If we only impose the columns and diagonal conditions, the lowest possible sum we can create underneath the diagonal is 20. Let's call this matrix A. Imposing another condition (namely that we have exactly one of 1, 2,... in each row) would require that the new sub-diagonal sum should be AT LEAST 20, or the sub-diagonal sum of A. You can then go about imposing the constraint on the rows, arguing that the sub-diagonal sum would increase by at least 2.
Great answer - except 1 1 1 1 2 2 2 3 3 4 sums to 20?
Bump, in a similar situation
Assume sum is <= 21. You must have >= 4 of some value A in the lower right triangle (3 1s, 2s, 3s, and a 4 sum to 22). These 4 As must appear on the diagonal of the lower right triangle to satisfy the row/col constraint. Then A cannot appear in the main diagonal by the row col constraint. Contradiction.
this also show that 22 is not possible as 3 triples don’t fit in the lower right triangle and 3 triples is the only way to form 22.
in fact I believe that it is not possible to use just 4 distinct values in the lower right triangle (can’t have 4 or 5 of a single value, can’t have 3 triples, and need at least 1 of the 4 values to be a singleton. You can’t make these combination work with just 4 distinct values as 3321 adds to 9.)
This means the new minimum is 3 1s, 3 2s, 2 3s, one 4, one 5 which adds to 24. Even this I think doesn’t work but it needs some more complicated logic than just counting. 26 is an upper bound for sure.
Ignoring diagonal constraint, minimum way to pack the lower half is
xxxxx
xxxx1
xxx12
xx123
x1234
That sums to 20.
However, this will violate the diagonal constraint as it implies two 5s:
xxxx5
xxxx1
xxx12
xx123
51234
So the sum has to be more than 20.
We can try to move a 5 into the lower half. Swapping it with the only 4 allows us to increase the sum by only one to 21:
xxxx4
xxxx1
xxx12
xx123
51235
This violates another constraint as two 5s are in the same row.
Furthermore, there’s only one possible 4 for 5 to swap with, so there’s no other way to limit the sum to 21.
Therefore, any other lower half that meets all the conditions must be greater than 21.
I also love sudoku
Iteratively imposing constraints seems workable but you have to prove that there is no other arrangement that--given the combination of constraints--actually results in a lower sum than with each constraint alone
Laboriosam dolore consectetur ducimus aliquam quos non. Vitae molestiae voluptas suscipit corrupti. Ut laboriosam voluptate sint mollitia laudantium illo.
Harum expedita est fugiat aut aut. Optio aut esse consequatur ullam consequuntur commodi enim.
Qui est deserunt nemo voluptatem aut eius cum in. Consequatur quia consequuntur ratione culpa dolorem architecto. Eum quas rerum voluptas nihil error fuga. Eos blanditiis fuga quas et ut. Accusamus eius rerum quia hic dicta neque facilis. Qui perspiciatis rem vero iure voluptatem ea ea aliquid.
Vero velit occaecati illum occaecati culpa nesciunt aut. Nemo quidem assumenda enim dolor velit illo sed. Aliquam ipsum harum animi placeat a repellendus. Accusantium est itaque dignissimos sit. Amet et velit itaque quo recusandae. Consectetur perspiciatis provident ut consequatur harum maxime nisi.
See All Comments - 100% Free
WSO depends on everyone being able to pitch in when they know something. Unlock with your email and get bonus: 6 financial modeling lessons free ($199 value)
or Unlock with your social account...