Lasketaan lukujen 1, 2, ..., n permutaatiolle sen vierekkäisten alkioiden summat ja näin saadulle (n-1 -pituiselle) lukujonolle taas sen vierekkäiset summat ja jatketaan näin kunnes lopulta tulee vain yksi luku. Kutsutaan näin saatujen summalukujen joukkoa H. Kuinka pieni voi |H| olla minimissään?
Esimerkki (n=5)
Olkoon permutaatio 3,4,1,2,5
Summat ovat
7, 5, 3, 7
12, 8, 10
20, 18
38
H = {3, 5, 7, 8, 10, 12, 18, 20, 38}
ja |H| = 9.
Esimerkki (n=5)
Olkoon permutaatio 3,4,1,2,5
Summat ovat
7, 5, 3, 7
12, 8, 10
20, 18
38
H = {3, 5, 7, 8, 10, 12, 18, 20, 38}
ja |H| = 9.
Vastaukset 1
Vanhimmat
Äkkiseltään sanoisin, että paras strategia on laittaa ensimmäiselle riville luvut järjestyksessä n, 1, (n-1), 2, (n-3), 3, ... jolloin eri lukuja tulee mahdollisimman vähän.