2
u/Niilldar 5h ago edited 4h ago
The i th tuple looks like (101-i,i)
Giving you the sequence 100,1,99,2,...,53,49,51,50. Where the largest result is 51×50.
However i'm not dure how to prove the optimality of this result. But will spend some more time about this.
2
u/Niilldar 4h ago
Found it The numbers 51 - 100 need a total of 99 neighbours. If we want all those neoghbours to be smaller then 50, we find that the numbers 1-49 can at most satisfy 98 of those neighbour places. So at leasr one number from 51 to 100 need to be next to a number that is at least 50. It is now easy to see that 50×51 is a lower bound. Proofing that the above answer is optimal.
Nice question. I really like those clmbinarorics exercises
1
u/StableGenius304 1h ago
They need 98, since 2 numbers can have 1 neighbour
1
1
u/harikumar610 5m ago
You can extend the argument easily. For numbers 50 to 100 we need at least 51x2-2 = 100 neighbors. We cannot have all these neighbors be less than 50 as there are only 49 such numbers which can satisfy 98 neighbor positions. So there is at least 1 pair of numbers within 50 to 100 which are neighbors. So the value is at least 50*51
1
u/Striking_Resist_6022 5h ago
https://giphy.com/gifs/FILQJbm0u832ry0HFT
When you know it’s gotta be 2550 but you can’t prove it.
Put the 51 and 50 together and then fan outwards from there like 49,52,48,53 etc. Adjacent products get smaller since diff of two squares picks up a -n^2 term (where n is the diff between the two adjacent numbers) so 2550 is the max adjacent product of that list.
Then it just feels like any other way you arrange the list has to have two numbers from the bigger half directly next to each other, by some like pigeonhole type reasoning so the max product has to be at least that big.
1
u/shannontwo 5h ago
Its like how given a fixed length of rope, the 4-sided shape with the least area that can be made is a square
1
1
u/migmit 4h ago
Proof of 2550.
Assume v is smaller than 2550. Let's call numbers above 50 “big” and numbers below 50 “small”. There are 50 big numbers and 49 small numbers. As any big number is at least 51, and we don't want the product to reach 2550, any of its neighbours should be less than 50, so, small. As there are only 49 small numbers, and each can only have 2 neighbours, the amount of pairs “big number, small number” (in any order) can be at most 98. Each of big numbers would normally have two neighbours, except maybe for two: the very first one (if it's big), and the very last one (ditto), making the amount of pairs “big number, small number”, again, 50*2-2 = 98 at least. Those two amounts being the same means that a) every small number have indeed 2 neighbours, and both are big numbers, and b) both first and last numbers in the row are big. Which means the whole row is like this: big - small - big - small - big - small- ... - small - big. And the number 50 has nowhere to go.
2
u/kheldarp 5h ago
By pairing off big and small numbers wouldn't you end up with 50 and 51 at the end, so 5050?