Opgave 30

Geplaatst op door

Plaats de eerste 20 getallen op een cirkel. S is de som van ( de positief getelde ) verschillen van twee aanliggende getallen. Wat zijn de minimum en maximum waarden voor S?

 

 

Antwoord

 

 

  • Proberen we eens uit met 4 getallen en noteer een schikking op de cirkel door bijvoorbeeld ( 1,3,2,4). De waarde van S is dan (3-1)+(3-2)+(4-2)+(4-1)=8. 
  • Als we de schikking (1,2,3,…,20) gebruiken, dan is het positief getelde verschil va twee buren altijd 1 behalve bij de buren 1 en 20. Dus s=19.1+19=38. Dit is duidelijk de minimumwaarde.
  • Noteer de getallen door a_1,a_2,...,a_{20}. Dan is elk verschil van de vorm \pm (a_{i+1}-a_i).
  • Bijgevolg is S=k_1a_1+k_2a_2+....+k_{20}a_{20} met k_i\in \{2,-2,0\} en waarvan de som van alle k_i gelijk is aan 0.
  • Dan wordt S gemaximaliseerd door h_1=h_2=...=h_{10}=-2 en h_{11}=h_{12}=...=h_{20}=2 en dan is S=-2(1+2+...+10)+2(11+12+...+20)=100. 
  • Dit kan je effectief verkrijgen door volgende schikking: (1,20,2,19,3,18,…,10,11).