Jedzie piątka
Zbiór, a właściwie zbiorek trzech liczb – {1, 2, 6} – ma szczególną własność. Korzystając z niego można dojechać do 8, zaliczając po drodze wszystkie mniejsze liczby naturalne. Zaliczenie oznacza skorzystanie z „gotowej” liczby, albo z sumy lub różnicy dwu liczb ze zbiorku, czyli:
1, 2, 1+2, 6-2, 6-1, 6, 1+6, 2+6.
Łatwo zauważyć, że jedynkę można zastąpić dwójką i jazda zbiorkiem {2, 5, 6} będzie równie dalekosiężna:
6-5, 2, 5-2, 6-2, 5, 6, 2+5, 2+6.
Żadnym innym 3-liczbowym zaprzęgiem, czyli trojką, zajechać równie daleko, ani tym bardziej dalej – się nie da.
Z kolei najbardziej sprawna 4-liczbowa kwadryga ({3, 5, 6, 7}) jest chyba tylko jedna i pozwala dotrzeć do 13:
6-5, 5-3 lub 7-5, 3 lub 6-3, 7-3, 5, 6, 7, 3+5, 3+6, 3+7, 5+6, 5+7, 6+7.
Kolej na najwytrwalszą piątkę. Jak wygląda i jak daleko zajeżdża? A może równie ekstremalnie sprawnych piątek jest kilka?
Komentarze z prawidłowym rozwiązaniem ujawniane są wieczorem w przeddzień kolejnego wpisu (z błędnym zwykle od razu). Wpisy pojawiają się co 7 dni.
Komentarze
Używamy tylko różnych liczb 1-cyfrowych, zatem 17 = 8+9 jest tu ograniczeniem górnym.
Liczbę 17 da się zrealizować za pomocą czterech zbiorów:
{2, 5, 7, 8, 9}, {3, 5, 7, 8, 9}, {3, 6, 7, 8, 9}, {4, 6, 7, 8, 9}
Ograniczenie do liczb 1-cyfrowych nie obowiązuje (co nie wyklucza, że przy 1-cyfrowych da się zajechać najdalej).
mp
Zestaw pięciu liczb, który pozwala „zaliczyć” wszystkie liczby naturalne aż do 20, to:
{1, 2, 7, 13, 17}
Nie wiem czy jest inny o takiej samej albo większej „wydajności”.
Poprawiłem trochę program i wyniki:
{1, 2, 7, 13, 17}
{1, 2, 8, 12, 17}
{1, 3, 7, 12, 17}
To wszystkie zestawy do 20
Zestawy sześciu liczb osiągające maksymalny zasięg 28:
{1, 2, 3, 10, 18, 24}
{1, 2, 3, 11, 17, 24}
{1, 2, 4, 10, 17, 24}
Zestaw 7 liczbowy
{1, 5, 7, 16, 19, 29, 32}
Ten zestaw osiąga maksymalny zasięg: 37.
Dalej program nie wydolił.
Gdyby wydolił znalazłby jeszcze jeden zbiór z zasięgiem 37: {3,4,6,15,20,28,33}.
mp
{1, 2, 3, 4, 6, 16, 26, 37} zasięg do 43
Liczba | Sposób uzyskania
——-|——————–
1 | 1 (z zestawu)
2 | 2 (z zestawu)
3 | 3 (z zestawu)
4 | 4 (z zestawu)
5 | |6 – 1|
6 | 6 (z zestawu)
7 | 3 + 4
8 | 2 + 6
9 | 16 – 7
10 | 4 + 6
11 | 16 – 5
12 | 6 + 6
13 | 16 – 3
14 | 16 – 2
15 | 16 – 1
16 | 16 (z zestawu)
17 | 1 + 16
18 | 2 + 16
19 | 3 + 16
20 | 4 + 16
21 | 26 – 5
22 | 6 + 16
23 | 26 – 3
24 | 26 – 2
25 | 26 – 1
26 | 26 (z zestawu)
27 | 1 + 26
28 | 2 + 26
29 | 3 + 26
30 | 4 + 26
31 | 37 – 6
32 | 6 + 26
33 | 37 – 4
34 | 37 – 3
35 | 37 – 2
36 | 37 – 1
37 | 37 (z zestawu)
38 | 1 + 37
39 | 2 + 37
40 | 3 + 37
41 | 4 + 37
42 | 6 + 36
43 | 6 + 37
Dla czterech cyfr jest więcej niż jedna kwadryga
{1, 2, 6, 11}
{1, 2, 7, 11}
{1, 3, 7, 12}
{3, 5, 6, 7}
Aha, to zmienia postać rzeczy. Myślałem że określenia „3-cyfrowy” i „4-cyfrowy” używane wcześniej oznaczają, że używamy właśnie tylko pojedynczych cyfr.
Udało się dojechać do 20, przy pomocy następujących zbiorów:
{1, 2, 7, 13, 17}, {1, 2, 8, 12, 17}, {1, 3, 7, 12, 17}.
Są też trzy dodatkowe czwórki realizujące 13:
{1, 2, 6, 11}, {1, 2, 7, 11}, {1, 3, 7, 12}.
Słuszna uwaga. Mój błąd. Poprawiłem -cyfrowe na -liczbowe.
mp
20
(1, 2, 7, 13, 17)
(1, 2, 8, 12, 17)
(1, 3, 7, 12, 17)
Pytanie, co wtedy, gdy luka następuje dopiero po 13 (dla czwórki), czyli np. 1, 2, 6, 11. Czy to jest równoprawne rozwiązanie z 3, 5, 6, 7?
Tak, to jest OK.
mp
Jeżeli dopuścimy sumę dwóch jednakowych wartości z wyjściowego zbiorku,
czyli tak jak w algebrze konstruujemy grupy, pierścienie, e.t.c,
to mamy jedyne rozwiązanie: [4, 8, 10, 11, 13] generujące wszystkie liczby od 1 do 26.
Jeśli jednak odrzucimy tą możliwość to mamy dwa rozwiązania:
[3, 6, 8, 9, 10] i [4, 7, 8, 9, 10] dowożące nas od 1 do 19.
Te 3 zestawy piątek:
[1, 2, 7, 13, 17]
[1, 2, 8, 12, 17]
[1, 3, 7, 12, 17]
pozwalają utworzyć liczby od 1 do 20
Najbardziej sprawne (tj. docierające do 13) 4-liczbowe kwadrygi są co najmniej 4.
Poza wymienioną w treści wpisu {3, 5, 6, 7}, mamy jeszcze:
[1, 2, 6, 11]
[1, 2, 7, 11]
[1, 3, 7, 12]
Nie widzę błędu w moich rozwiązaniach. Czy da się lepiej ???
Da się.
mp
13 => {3, 5, 6, 7}
13 => {1, 2, 6, 11}
13 => {1, 2, 7, 11}
13 => {1, 3, 7, 12}
20 => {1, 3, 7, 12, 17}
20 => {1, 2, 8, 12, 17}
20 => {1, 2, 7, 13, 17}
Komputer znalazł mi trzy rozwiązania: {1,2,7,13,17}, {1,2,8,12,17}, {1,3,7,12,17}. Dalej niż do 20 dojechać się w podanych warunkach zadania nie da (jeśli nie popełniłem gdzieś błędu?).
A tak to wygląda czytelnie rozpisane:
Tego typu zadania są bardzo żmudne w rozwiązywaniu ręcznym. Jesteśmy omylni. Jeden moment dekoncentracji i można popełnić błąd gubiący rozwiązanie. No i gdy wariantów jest bardzo dużo, to wtedy nie wiadomo, czy nie ma innych rozwiązań, też spełniających założone warunki lub lepszych.
Rozwiązywanie z pomocą poprawnie zaplanowanego algorytmu też nie jest proste. Nie zawsze daje się go łatwo ułożyć, a co dopiero rozpisać na działający kod. Praktycznie zawsze trzeba taki kod nieraz przeglądać i analizować w poszukiwaniu błędów, tak w konstrukcji algorytmu, jak i w późniejszym jego pisaniu. Jednak zaletą tej drogi jest przegląd wszystkich możliwych wariantów. Nawet jeśli jest ich bardzo dużo, to moc obecnych komputerów pozwala rozprawić się z problemem bez narzekania na długie oczekiwanie na zakończenie przeliczania.
I podczas rozwiązywania ręcznego, i z pomocą programu komputerowego – zaliczam do tego także „łagodne” wspomaganie się arkuszem kalkulacyjnym – najprzyjemniejszym momentem jest wymyślanie algorytmów. Odkrywanie, że coś wynika z czegoś. Obie drogi mają więc wspólny element, nieraz dość dokładnie pokrywający się.
Matematyka i rozwiązywanie zadań matematyczno-logicznych, a potem programowanie, choć raczej głównie „na potrzeby własne”, poczynając od ośmiobitowego Atari, było zawsze moim wielkim hobby. Za starych czasów były to między innymi „Rozkosze Łamania Głowy”, prowadzone na początku przez Lecha Pijanowskiego. Dziś zadania w Łamiblogu, głównie dzięki żywemu kontaktowi w jego formule są wspaniałym dodatkiem do… emeryckiego sensu życia. Dołączę się do niedawno tu opublikowanego wpisu @apartado – dziękuję, Gospodarzu.
Rozszerzyłem działanie programu wyszukującego rozwiązania i podaję, co on wyliczył dla 6 i 7 liczb.
Dla 6 liczb można dojechać do 28 na trzy sposoby: { 1, 2, 3,10,18,24 } { 1, 2, 3,11,17,24 } { 1, 2, 4,10,17,24 } Dla 7 liczb można dojechać do 37 na dwa sposoby: { 1, 5, 7,16,19,29,32 } { 3, 4, 6,15,20,28,33 }Rozwiązując to zadanie można wpaść w pułapkę, podjąć pewien mylny trop, spróbuję wyjaśnić. Dla dowolnej liczby n, wszystkich elementów zbioru złożonego z n elementów zbioru wyjściowego, ich sum i dodatnich różnic, jest n^2. Dla n = 4 mamy 4+6+6 = 16, dla n = 5 – 5+10+10 = 25, itd. Gdyby udało się metodą opisaną w zadaniu „dojechać” dla n = 5 do 25, to dwie największe liczby musiałyby być 12 i 13, no ale okazuje się, że 25 osiągnąć się nie da, podobnie jak 16 dla n = 4. I tu wchodzi błędne myślenie: jeśli dla 25 sprawdzamy największe liczby 12 i 13, to dla 23 sprawdźmy 11 i 12, dla 21 – 10 i 11, dla 19 – 9 i 10, itd, jakoś bardziej ufałem nieparzystym sumom. No i doszedłem w ten sposób do jednego z rozwiązań, które podał Spytko z Melsztyna, czyli do 3, 6, 8, 9, 10; da się z pomocą sum i różnic zrobić wszystko od 1 do 19. Pod poprzednim wpisem wspominałem o znajomych młodych programistach, teraz też poprosiłem jednego z nich, imieniem Eryk, by sprawdził wszystkie możliwości – najpierw dla n = 4. Ku mojemu wielkiemu zaskoczeniu, otrzymał oprócz rozwiązania, które miało być „chyba tylko jedno”, 3, 5, 6, 7, jeszcze trzy – 1, 2, 6, 11; 1, 2, 7, 11; 1, 3, 7, 12. Wszystkie zmierzają do liczby 13, a ja zrozumiałem, że jak chcemy osiągnąć 13, to nie jest tak, że dwie największe liczby to muszą być 6 i 7, suma ich może wynosić nawet 19, jak w przykładzie (1, 3, 7, 12), luki jednak powstaną dopiero po osiągnięciu 13, bo nie da się zrobić 14; 15 akurat tak, ale 16, 17 i 18 znów nie. Dla n = 5 Eryk znalazł rozwiązania zaskakujące, wszystkie 3 zmierzają do liczby 20: 1, 2, 7, 13, 17; 1, 2, 8, 12, 17; 1, 3, 7, 12, 17. Ciekawe, że w każdym przypadku nieodzowna przy dochodzeniu do 20 jest liczba 17.
Możliwe do osiągnięcia wartości:
ilość liczb / maksimum
errata:
oczywiście wiersz ze znakiem zapytania powinien wyglądać:
8 / 47? = 37+10
No tak – wygląda na to, że w pośpiechu nadrabiającym zaległości nie doczytałem komentarza @Antyp1958 z maksimum 43 dla 8 liczb.
Tym samym piękna sekwencja się skończyła.
🙂
A jednak zadziałała sekwencja, którą zaproponowałem powyżej.
{1,2,3,13,19,28,36,43} => 47{3,6,9,12,14,16,40,41,42} => 58q.e.d
@apartado
Wspomniany Eryk doszedł do 59 dla n = 9, na 3 sposoby:
2, 4, 6, 8, 11, 27, 30, 47, 48
1, 2, 3, 4, 16, 24, 35, 45, 54
1, 2, 3, 6, 14, 24, 34, 43, 53
Stąd wynika, że jednak prosty schemat jest zbyt prosty.
@aps1968
No wreszcie !
(bo moja wiara w człowieka już zaczęła podupadać)
n=10
59+12=71
{1,2,3,4,7,17,29,41,52,64} => 71
Jestem ciekaw co Eryk na to ?
A tak w ogóle to:
Miałem cichą nadzieję, że ktoś dociekliwy, bystry i spostrzegawczy poszuka jakiejś zależności / wzorca w rozmieszczeniu tych liczb na osi.
TO byłoby prawdziwym odkryciem pozwalającym generować takie zestawy bez uruchamiania zaawansowanych algorytmów.
Ja tego wszystkiego sam przecież nie pociągnę 🙂