Modulo
Po krótkiej wycieczce do Turcji powracam do trójkątów liczbowych. To obiekty mało znane, poza trójkątem Pascala, a ciekawe. Przygotowałem artykuł o tych cudakach do Świata nauki; ściślej – o niektórych z nich, pozostałe przemycam do Łamiblogu.
Można powiedzieć, że trójkąty liczbowe są równoboczne, bo na każdym boku znajduje się tyle samo liczb, zaś wszystkie tworzące trójkąt tkwią w nim jak punkty w graficznym przedstawieniu liczb trójkątnych.
Liczba liczb w trójkątach liczbowych jest więc zawsze liczbą trójkątną. Każdy tworzy się albo od wierzchołka, jak trójkąt Pascala, albo od podstawy, jak trójkąt różnicowy lub modularny. O różnicowych już trochę pisałem – tu i tu. O modularnych było przedpoprzednio, a cdn. teraz. Przypomnę, że tworzy się je, wpisując nad parami liczb ich sumy, ale niektóre sumy, np. dwucyfrowe, zapisywane są modulo x, czyli są pomniejszane o x. Przedpoprzednio x równało się 9, więc np. zamiast 15 sumą było 6. Inaczej mówiąc, sumą była suma cyfr sumy:).
Ciekawe zadanie wiąże się z trójkątami modularnymi złożonymi z t liczb, w których modulo t zapisywane są wszystkie sumy większe od t, czyli w tym przypadku są pomniejszane o t (z definicji: „a modulo n” oznacza resztę z dzielenia a przez n). Zatem żadna z tworzących trójkąt t liczb nie będzie większa od t. Oto dwa przykłady dla t = 6; sumy zapisane modulo 6 są niebieskie.
Drugi przykład jest jedynym jednym z dwóch dla t = 6 rozwiązańniem następującego „zakręconego” problemu: czy dla każdego t (3, 6, 10, 15, 21,…) istnieje trójkąt bez powtórek, czyli złożony z wszystkich liczb od 1 do t?
Dla t = 6 szukanie rozwiązania jest proste, bo próbowanie i błądzenie trwa krótko. Wystarczy zauważyć, że w wierzchołku zawsze będzie t (gdyby było niżej, to jakaś liczba pojawiłaby się dwukrotnie), a potem dopasowywać kolejno liczby w drugim i trzecim rzędzie.
A czy istnieje rozwiązanie dla t = 10? Odpowiedzieć na to pytanie, czyli znaleźć (lub nie) trójkąt, to jedno. Drugie i ciekawsze wydaje się znalezienie pomysłu na choć trochę szybsze i sprytniejsze rozwiązywanie niż mozolna metoda prób i błędów lub odpowiadający jej komputerowy backtracking.
Komentarze z prawidłowymi rozwiązaniami uwalniane są wieczorem w przeddzień kolejnego wpisu. Wpisy pojawiają się co 3 dni.
Komentarze
Dla t =10 w podstawie można położyć: 9 4 1 6.
Nie licząc układów symetrycznych, dla t=1 jest jedno rozwiązanie:
_3
1_2
Natomiast, dla t=6, oprócz podanego w zadaniu, istnieje jeszcze jedno:
__6
_1_5
4_3_2
Dla t=10 znalazłem 4 rozwiązania:
__10
__2_8
_7_5_3
1_6_9_4
__10
__2_8
_7_5_3
6_1_4_9
__10
__4_6
_9_5_1
7_2_3_8
__10
__4_6
_9_5_1
2_7_8_3
Czyżby dla kolejnych wartości t liczba rozwiązań była kolejną potęgą dwójki? Było by to dość zaskakujące, ale gdyby tak było, to powinna istnieć jakaś względnie prosta reguła znajdowania rozwiązań dla różnych wartości t.
Spróbuję poszukać rozwiązań dla t=15. Może to pozwoli na znalezienie jakiejś ogólnej metody dochodzenia do rozwiązań.
Pozdrawiam
Hm, a co z rozwiazaniem dla t=6:
6
5 1
2 3 4
Tez spelnia warunki zadania…, czyli to podane NIE jest jedynym.
Konglaide
Natomiast dla t=10 znalazlem 4 rozne rozwiazania:
10
2 8
7 5 3
1 6 9 4
10
2 8
7 5 3
6 1 4 9
10
4 6
9 5 1
2 7 8 3
10
4 6
9 5 1
7 2 8 3
Pozdrawiam
Hm, niestety, już NIE…:)
Ale w parze zawsze raźniej.
mp
10
8 2
3 5 7
9 4 1 6
Dla t=15 nie ma rozwiązań!!!
Nie przeszukiwałem wszystkich możliwych ustawień. Użyłem do tego pewnej metody opartej na rozkładzie liczby t na czynniki pierwsze. Tak znalazłem drugie rozwiązanie dla t=6 i rozwiązania dla t=10.
Pozdrawiam
Dla liczb od 1 do 10 są dwa rozwiązania:
10
2 8
7 5 3
1 6 9 4
10
4 6
9 5 1
2 7 8 3
Bez rozwiązań symetrycznych.
Dość łatwo do nich dojść, zaczynając od góry. Tzn. wpisujemy 10, które jest oczywiście sumą dwóch liczb bez modulo. Par liczb, które spełniają równość a+b=10 jest tylko 3 (2,8),(3,7),(4,6). Łatwo sprawdzić, które liczby muszą być modulo. Następnie powtarzamy to samo z wierszem niższym. Postępowanie jest dość szybkie bo wiersze wyższe mocno ograniczają zasób liczb.
Dla 15 nie ma rozwiązań, to samo dla 21. Choć jest dużo rozwiązań przybliżonych. To jest takich, gdzie jedna z liczb powtarza się dwa razy a jedna z pozostałych nie występuje.
_______13
______9__4
___13__11_ 3
__8__5__6__12
7__1__4__2__10
Powtarza się 13 brak 15 (oj, coś tu nie gra w górnych rzędach – mp)
Dla 21
________21
_______16_5
______7__9_17
____4__3__6__11
__15_10_14_13_19
7__8__2__12__1__18
Powtarza się 7 brak 20
Ciekawie się robi jeżeli zmienimy trochę zasady budowania trójkątów.
Np jeżeli suma pary liczb jest większa od ilośći liczb w trójkącie to zamiast sumy wstawiamy wartość bezwzględną ich różnicy. Istnieją takie trójkąty zbudowane z 15 elementów. Np
_______3
____12__15
___4___8__7
_10_14__6__13
1__9__5__11__2 (Rzeczywiście, oryginalne i ciekawe – mp)
Pozdrowienia
Witam
dla t=10 znalazłem tylko jedno rozwiąznie:
10
4,6
9,5,1
7,2,3,8
pozdrawiam
peha
Jazz, moglbys przyblizyc metode rozkladania liczby na czynniki pierwsze? Chcialbym wiedziec, jak doszedles do Twoich rozwiazan.
Pozdrawiam
Koglaide, zapewne nie chodzi Ci o metodę rozkładania liczby t na czynniki pierwsze, lecz o wykorzystanie tego rozkładu w poszukiwaniu rozwiązań zadania.
Otóż, wyobraziłem sobie, że pewnym uproszczeniem poszukiwania rozwiązań jest wykorzystanie rozkładu liczby t na czynniki pierwsze. Dla ilustracji przyjmijmy t=6. Korzystając z tego, że liczba 6 ma dwa podzielniki pierwsze: 2 i 3, poszukiwałem dwóch zbiorów trójkątów. Jeden zbiór miał zawierać trójkąty podzielności przez 2, drugi zawierać trójkąty podzielności przez 3.
Ponieważ na szczycie rozwiązania musi być wartość t, to w poszukiwanych trójkątach na szczycie musi być 0.
Dla t=6 pierwszy zbiór zawiera dwa dobre trójkąty
__0
_0_0
1_1_1
i
__0
_1_1
0_1_0
Inne trójkąty są niedopuszczalne, gdyż w rozwiązaniu zadania musi być tyle samo liczb parzystych i nieparzystych oraz na szczycie musi być 0.
Dla t=6 mamy, nie licząc symetrii, jeden poprawny trójkąt podzielności przez 3:
__0
_1_2
1_0_2
Inne nie wchodzą w rachubę, gdyż w rozwiązaniu zadania musi być tyle samo liczb dających resztę 0 (czyli podzielnych przez 3), jak i dających resztę 1 oraz resztę 2. No i na szczycie musi być 0
W drugim etapie następuje łączenie trójkątów podzielności przez 2 z trójkątami podzielności przez 3. Tu przychodzi z pomocą pewna ciekawa własność. Otóż nie może być dwóch liczb tworzących rozwiązanie zadania, które mają takie same reszty przy dzieleniu przez 2 i przy dzieleniu przez 3. Inaczej mówiąc jeśli dwie liczby dają przy podzielności przez 2 taką samą resztę, to muszą dać różne reszty przy podziale przez 3. I odwrotnie – dwie liczby mające przy dzieleniu przez 3 taką samą resztę muszą dać różne reszty przy podziale przez 2.
Dla rozważanego przypadku (t=6) trójkąt podzielności przez 3 możemy połączyć z oboma trójkątami podzielności przez 2 (dla innych wartości t tak być nie musi). Dzięki temu mamy dwa rozwiązania (bez symetrii). Jeśli połączymy trójkąt podzielności przez 3 z pierwszym trójkątem podzielności przez 2, to dostajemy rozwiązanie:
__6
_2_4
5_3_1
Dla drugiego przypadku mamy:
__6
_1_5
4_3_2
Na koniec przedstawię krótkie uzasadnienie, że nie ma rozwiązań zadania dla t=15.
Liczba 15 ma dwa podzielniki pierwsze: 3 i 5. Zatem musimy znaleźć wszystkie dopuszczalne trójkąty podzielności przez 3 i podzielności przez 5.
Trójkątów podzielności przez 3 oraz podzielności przez 5 jest po pięć. Jednak nie można z nich utworzyć żadnej pary spełniającej warunek z drugiego etapu, ponieważ dla każdej rozważanej pary trójkątów zawsze znajdują się dwie liczby, które mają taką samą resztę z dzielenia przez 3 i taką samą resztę z dzielenia przez 5.
Czy przedstawiona powyżej metoda jest prosta? Tego nie twierdzę, ale znacznie przyspiesza poszukiwania dla większych wartości t.
Nie spoczywam w staraniach poszukania rozwiązania dla większych wartości t, ale nie obędzie się to bez pomocy komputera.
Pozdrawiam
PS
Proszę o odzew.