Permutuj
132 to jedna z trzech różnych permutacji cyfr {1,2,3} – przy założeniu, że permutacje, z których jedna jest odwróceniem drugiej, uznamy za jednakowe. W odróżnieniu od dwóch pozostałych (123 i 213) permutacja 132 ma pewną szczególną własność: biorąc jedną cyfrę lub sumując dwie lub trzy kolejne, można utworzyć każdą liczbę od 1 do 6. W przypadku permutacji 123 nie utworzymy sumy równej 4, a permutacja 213 uniemożliwia uzyskanie 5.
Czy można utworzyć taką permutację trzech cyfr, w przypadku której w podobny sposób będzie można dotrzeć od 1 bez przerw do większej sumy? Podejrzana jest trójka {1,2,4}, ale łatwo sprawdzić, że żadna permutacja nie pozwoli na współistnienie sum 3, 5 i 6.
Permutacja 132 jest więc rozwiązaniem następującego zadania (dla n=3):
Znajdź taką permutację n cyfr (niekoniecznie różnych) o sumie s, by sumując jakieś k kolejnych, tworzących ją cyfr (k = 1, 2, 3,….., n), można było utworzyć każdą sumę od 1 do s. Ponadto suma s powinna być jak największa.
Proszę rozwiązać to zadanie dla n=4 i ewentualnie dla n=5.
Komentarze
Tak na szybko, to 1412 przychodzi mi do głowy. Ale pewnie bijemy się o dużo większą sumę?…
1332
13411
1352
lub
2513
oraz
13625
13652
17324
17423
dalsze przykłady (dla wiekszej liczby ‚n’)pod adresem
http://en.wikipedia.org/wiki/Golomb_ruler
w tabelce ‚Known optimal Golomb rulers’ przerobic podzialke na dlugość 🙂
To nie jest to samo co linijka Golomba, choć jakby spokrewnione.
mp
…chyba się pospieszyłem…
n=4: s=9, 1143
n=5: s=13, 11443
n=6: s=17, 111554
n=7: s=22, 1115554
n=8: s=29, 12377441
4) 1332, 1143 – 9
5) 11443, 13162, 15322 – 13
6) 111554, 114443, 116423, 116432, 136232, 173222 – 17
7) 1194332, 1366232 -23
1143 i dla n=4 już więcej być nie powinno.
Układ złożony z (n-2) jedynek oraz cyfr n i (n-1) zawsze spełnia warunki.
Np. 11154.
Dla n=4 największe s=9
1,1,4,3
dla n=4: 1332
dla n=5: 13332
dla n=6: 133332 😉
itd.
Dla n=4 OK, ale dalej nie.
mp
n=4, suma 9
1143
1332
oraz dla n=5, suma 13
11443
13162
15322
zaczerpnąłem z: http://en.wikipedia.org/wiki/Sparse_ruler
Podobnie jak w poprzednim wpisie, przeliczyłem podziałki na odległości.
🙂
Trafiona linijka?
Tak, trafienie w dziesiątkę. Permutacje cyfr odpowiadają tzw. linijkom optymalnym.
mp
1, 2, 3, 4 nie wychodzi, więc 1, 2, 3, 3, w kolejności 2, 3, 3, 1.
1, 3, 3, 3, 2 – to właściwie równoważne pod względem sumy z rozwiązaniem y-b, ale nic lepszego mi na razie nie wychodzi.
Dla n=4 mamy 8 (4 bez odwróconych) rozwiązań przy s=9
1,1,4,3
1,3,3,2
2,3,3,1
2,5,1,3
3,1,5,2
3,4,1,1
4,1,2,6
6,2,1,4
Dla n=5 mamy 14 (7 bez odwróconych) rozwiązań przy s=13
1,1,4,4,3
1,3,1,6,2
1,3,6,2,5
1,5,3,2,2
1,7,3,2,4
2,2,3,5,1
2,6,1,3,1
3,4,4,1,1
3,7,1,1,4
4,1,1,7,3
4,2,3,7,1
5,2,6,3,1
6,1,2,2,8
8,2,2,1,6
🙂
Dla n=6, mamy 4 (2 bez odwróconych) rozwiązań, przy s=18:
2,5,6,3,1,8
2,5,7,1,3,6
6,3,1,7,5,2
8,1,3,6,5,2
s powinno być sumą wszystkich cyfr.
mp
11443, suma s=13
15322?
Dla 4 cyfr jest 10 różnych sum, więc s wynosi maksymalnie 10. Nietrudno zauważyć, że 1 i 2 muszą stać na końcach ciągu (żeby dało się zrobić sumy 8 i 9). Wtedy oba ustawienia 3 i 4 pomiędzy nimi nie dają dobrego ciągu. Zatem s=9. Wtedy 1332 spełnia warunki zadania.
Poprawione !!!
Dla n=4 mamy 4 (2 bez odwróconych) rozwiązania, przy s=9:
1,1,4,3
1,3,3,2
2,3,3,1
3,4,1,1
Dla n=5 mamy 6 (3 bez odwróconych) rozwiązań, przy s=13:
1,1,4,4,3
1,3,1,6,2
1,5,3,2,2
2,2,3,5,1
2,6,1,3,1
3,4,4,1,1
Dla n=6, mamy 12 (6 bez odwróconych) rozwiązań, przy s=17:
1,1,1,5,5,4
1,1,4,4,4,3
1,1,6,4,2,3
1,1,6,4,3,2
1,3,6,2,3,2
1,7,3,2,2,2
2,2,2,3,7,1
2,3,2,6,3,1
2,3,4,6,1,1
3,2,4,6,1,1
3,4,4,4,1,1
4,5,5,1,1,1
Zmyliło mnie zdanie że s ma być jak największe 🙂
Dla n=6 ………
Dla n=7, mamy 4 (2 bez odwróconych) rozwiązania, przy s=23:
1,1,9,4,3,3,2
1,3,6,6,2,3,2
2,3,2,6,6,3,1
2,3,3,4,9,1,1
n=4, s=9
1143
1332
n=5, s=13
11443
13162
15322
Te i więcej rozwiązań dla n>5 można znaleźć tu: http://en.wikipedia.org/wiki/Sparse_ruler
No i nieco musztarda po obiedzie ale niech już będzie,
dla n=8, mamy 4 (2 bez odwróconych) rozwiązania, przy s=29:
1,2,3,7,7,4,4,1
1,3,6,6,6,2,3,2
1,4,4,7,7,3,2,1
2,3,2,6,6,6,3,1