Ancestors

Toot

Written by jsiehler on 2024-12-13 at 13:35

A nice problem from "A Mathematical Orchard."

Consider the (n\times n) array whose entry in the (i)-th row, (j)-th column is ((i+j-1)). What is the smallest product of (n) numbers from this array, with one coming from each row and one from each column?

=> More informations about this toot | More toots from jsiehler@mathstodon.xyz

Descendants

Written by Christian Lawson-Perfect on 2024-12-13 at 14:00

@jsiehler I haven't thought about this for long, but am I missing a reason you can do better than the greedy choice of ∏ᵢ₌₁ⁿ(2𝑛−1)?

Or is proving that that is optimal the fun part?

=> More informations about this toot | More toots from christianp@mathstodon.xyz

Written by jsiehler on 2024-12-13 at 14:06

@christianp When you make a "greedy" selection, you're (I presume) selecting the minimum available element in each row -- which makes sense -- subject to a choice of which order you go through the rows. If you went from bottom row to top, you could make a greedy selection which does not achieve the minimum product. Why is "your" greedy choice the right one?

=> More informations about this toot | More toots from jsiehler@mathstodon.xyz

Written by Christian Lawson-Perfect on 2024-12-13 at 14:08

@jsiehler my "greedy" choice is to pick the smallest available number in the array.

In the meantime I've convinced myself that swapping the entries in (a,a) and (b,b) for (a,b) and (b,a) can only increase the product, but is that all there is?

=> More informations about this toot | More toots from christianp@mathstodon.xyz

Written by Andrew on 2024-12-13 at 14:43

@christianp @jsiehler I'm kind of thinking of it as a partitioning puzzle, since the sum of all the numbers we pick has to equal n². So it makes sense to me to say that the solution for n is always just the solution for n-1 with the new bottom right element added into the selection — the most efficient thing you can do with your extra 2n-1 of sum is surely to dump it all in one big number where it can't do too much damage? Still very hand-wavy, but it feels convincing 🤷

=> More informations about this toot | More toots from andrewt@mathstodon.xyz

Written by jsiehler on 2024-12-13 at 14:44

@christianp The swapping argument is convincing. That's "all there is," but it won't be so obvious for everyone, I think.

=> More informations about this toot | More toots from jsiehler@mathstodon.xyz

Written by Christian Lawson-Perfect on 2024-12-13 at 14:45

@jsiehler cool. Was that your argument, or did you come up with another way?

=> More informations about this toot | More toots from christianp@mathstodon.xyz

Written by jsiehler on 2024-12-13 at 16:20

@christianp Yes, I guessed that the product along the main diagonal would be the minimizer, and then used the idea of swapping pairs to compare an arbitrary selection to that one. I think that past experience strongly conditions me to think of "a selection of one from every column and one from every row of a square matrix" as "a permutation" and thinking of permutations as being related by transpositions. There's nothing in the problem that requires advanced knowledge at all (you need to be able to manipulate inequalities at a basic algebra level, I guess) but I would still expect it to have a very low success rate among students here, even limiting to math students, who have not explicitly practiced solving contest-type problems.

=> More informations about this toot | More toots from jsiehler@mathstodon.xyz

Written by Colin Parker on 2024-12-13 at 22:46

@christianp @jsiehler I think you also need to handle cases where a pair is swapped but the result is not two entries on the main diagonal. If any selected entry is above and to the right of any other selected entry a swap will lower the product. Further if the lower right is not selected such a swap is guaranteed to exist. Then you are guaranteed a path to the main diagonal, from which no lowering is possible.

=> More informations about this toot | More toots from Colinvparker@mathstodon.xyz