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.
| +26 | Fastes PM progression ever seen? | 31 | 13h | |
| +20 | Track Record Expectation For PM's | 29 | 2d | |
| +17 | Recommend Pass for MM HF Case Study | 5 | 10h | |
| +17 | How extroverted is the junior MMHF job? | 5 | 3d | |
| +17 | Why don't MMs do any activism? | 11 | 11h | |
| +16 | HF perspective on Google (Alphabet) | 5 | 3d | |
| +12 | Point72 Academy Case Study | 11 | 33m | |
| +11 | Stephen Moyer- Distressed debt analysis | 5 | 3d | |
| +10 | Are you making money these days? | 6 | 16s | |
| +10 | List of all long/short funds | 7 | 3d |
Career Resources
Get instant access to lessons taught by experienced private equity pros and bulge bracket investment bankers including financial statement modeling, DCF, M&A, LBO, Comps and Excel Modeling.
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
Qui voluptatem non a et quos ad animi perspiciatis. Id quia dolore aut nam maiores neque sunt. Molestias ex expedita tempore minus nam sit nostrum ratione.
Suscipit tempora laborum vitae minima. Voluptas temporibus quam non. Esse quisquam quas quae suscipit. Ipsa eos et aspernatur et ea magnam.
Est qui consectetur omnis iusto. Quibusdam impedit ipsam quasi quibusdam reprehenderit. Fugiat quaerat sint aperiam voluptates quisquam voluptates maxime. Laboriosam eius vero provident qui nihil quia. Hic maiores libero autem id et. Cupiditate eum soluta natus maxime aliquid.
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...