1
u/Suitable_Werewolf_61 4d ago
I would say it happens with identity.
1
u/998mouse 4d ago
It's a waste to have a big number on the edge because you only use it for one product.
1
u/Aerospider 4d ago
We need to maximise the multiples of the higher numbers, so best to keep them together.
E.g. (100 * 60) + (40 * 1) > (100 * 1) + (60 * 40)
We can do this by making a(i) = i, but then the 100 only features once, so better to do a(i) = i+1, with a(100) = 1.
This gives
6 + 12 + 20 + 30 + ... + 9,702 + 9,900 + 100
= 333,398
1
u/Fovlsbane 3d ago
What happens if you now swap the 2 and the 1? 6 becomes 3 in the sum, and 100 becomes 200, gains 97 total. Or swap 99 and 100; 100 becomes 99, 9900 stays 9900, 9702 becomes 9800, gains 97 total.
2*3+100*1<1*3+100*2
98*99+99*100+100*1<98*100+100*99+99*1
1
u/PandemicGeneralist 4d ago
Clearly maximized with the identity mapping. Then we need a formula for Σ(2i+1)(2i+2) between i=0 and 49. We know that the sum of terms of a degree n polynomial is degree n+1, so the answer is a cubic. We find the terms of this cubic by solving the linear system by plugging in the first 4 values, and obtain 4/3x^3+5x^2+17/3x+2 and plug in 49 to obtain the answer of 169150
1
1
u/Tremotino98 3d ago
My best guess based on smaller esamples is all odd numbers in increasing order, followed by all even numbers in decreasing order (essentially put a1 in first place, a2 last place, a3 second, a4 second to last, and so on)
Will try to prove it later
1
u/Neither_Berry_100 3d ago
Isn't it literally just 1 x 2 + 3 x 4 + ... + 99 x 100? Won't bother solving this.
1
u/ProspectiveWhale 3d ago
You misread the question.
1
u/Neither_Berry_100 3d ago
No. This is what it says. Apart from the title maximum adjacent product sum. Whatever that means.
1
u/ProspectiveWhale 3d ago
a1a2 + a2a3 + ...
Notice a2 appears twice here?
That's where you misread the question.
Doing it with your sequence (in ascending order) would be
1x2 + 2x3 + 3x4 + ...
1
u/spdazero 3d ago
I'm too lazy to write a rigorous proof, but here is the intuition, which can easily be verified:
- Since a1 and a100 occur only once, it would make sense to assign them 1 and 2 (proof by contradiction, if they are not 1 and 2, just swap them with anything else and compare)
- Now that a1 = 1 and a100 = 2, a2 must be 3 to minimise the effect caused by multipling with a1. (proof by contradiction, if a2 != 3, just swap them with the position where number 3 is and compare)
- Same goes a99 = 4
- Rinse and repeat
- Final answer: maximum at 1*3 + 3*5 + ... + 4*2, with a1, a2 ... being increasing odd numbers, and a100, a99 .. being increasing even numbers
3
u/998mouse 4d ago
How about putting the 100 in the middle with the even numbers down one side of it and the odd numbers down the other side?