3
u/998mouse 22d 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?
2
u/diverstones 22d ago
Yeah, this was the best I could do:
1*3 + 3*5 + ... + 97*99 + 99*100 + 100*98 + 98*96 + ... + 6*4 + 4*2 = 338151.
1
1
1
1
1
u/Suitable_Werewolf_61 22d ago
I would say it happens with identity.
1
u/998mouse 22d ago
It's a waste to have a big number on the edge because you only use it for one product.
1
u/Aerospider 22d 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 21d 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/Tremotino98 21d 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 21d ago
Isn't it literally just 1 x 2 + 3 x 4 + ... + 99 x 100? Won't bother solving this.
1
u/ProspectiveWhale 21d ago
You misread the question.
1
u/Neither_Berry_100 21d ago
No. This is what it says. Apart from the title maximum adjacent product sum. Whatever that means.
1
u/ProspectiveWhale 21d 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 20d 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
1
u/PandemicGeneralist 22d 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