Ideały
Zacznę, jak w przedpoprzednim wpisie, od największej liczby różnocyfrowej, czyli 9876543210, która jest pod paroma względami bliska ideału. Na przykład, jeśli będziemy ją stopniowo „odsłaniać”, cyfra po cyfrze, zauważymy, że:
98 dzieli się przez 2,
987 – przez 3,
9876 – przez 4,
98765 – przez 5
itd., ale do ideału brakuje jednego:
9876543 nie dzieli się przez 7.
Szukanie ideału, czyli liczby złożonej z 10 różnych cyfr, z których każde n kolejnych cyfr, zaczynając od pierwszej, tworzy liczbę podzielną przez n – jest dość żmudne, choć w dużym stopniu logiczne. Zagadka jest zresztą znana od co najmniej półwiecza i przypominałem ją już w Łamiblogu niemal dokładnie 7 lat temu. Pozostaniemy jednak przy niej, tylko porzucimy układ dziesiętny.
W układzie dwójkowym sprawa jest trywialna – 10 to jedyne rozwiązanie. W układzie trójkowym ideałów brak.
Proszę znaleźć ideał dla układu czwórkowego, czyli przynajmniej jedną liczbę 4-cyfrową złożoną z wszystkich cyfr od 0 do 3 (nie zaczynającą się zerem) – o własności podanej wyżej tłustym drukiem.
A może ktoś się pokusi o znalezienie ideałów dla układu szóstkowego (w piątkowym ich nie ma).
Komentarze
Układ czwórkowy (…)
Układ szóstkowy 1236540, 3216540
Układ dziewiątkowy 381654720
Układ dziesiątkowy (…)
(…) są OK, więc cenzurki tymczasowe.
mp
Albo czegoś nie rozumiem albo jest bardzo proste.
Dla czwórkowego tylko 2 liczby wchodzą w rachubę
3210 i 1230 – i obie są „idealne”
Dla szóstkowego sprawdziłem tylko 543210 i również jest idealne.
Wiadomo, że niezależnie od systemu taka liczba kończy się zerem. Również wydaje mi się łatwe do udowodnienia, że w systemach o parzystej podstawie wszystkie cyfry na parzystych miejscach muszą być parzyste.
P.
Istotnie, dla czwórkowego jest proste, ale dla szóstkowego już chyba nie – 543210 to nie jedyny ideał.
Dwa końcowe zdania są oczywiście słuszne.
mp
W układzie czwórkowym: 1230 oraz 3210.
W układzie szóstkowym: 143250 oraz 543210.
Rzeczywiście zadanie nie wymaga użycia komputera. Kilka obserwacji:
1) Na n-tym miejscu zawsze musi stać 0 (cecha podzielności przez n w układzie n-tkowym to 0 na ostatnim miejscu).
2) Dla parzystych n, na miejscu n/2 musi stać n/2 (mogłoby jeszcze 0, ale jest na końcu).
3) Dla parzystych n, cecha podzielności przez 2 to ostatnia cyfra parzysta.
4) Dla parzystych n, cecha podzielności przez 4 to dwie ostatnie cyfry podzielne przez 4.
Uzwględniając powyższe obserwacje zostają do sprawdzenia po dwa przypadki w układzie czwórkowym i szóstkowym, wszystkie są OK.
1230 lub 3210
0 musi być ostatnie, bo cała liczba musi być podzielna przez 4 (cecha podzielności jak dla 10 w systemie dziesiątkowym)
Druga cyfra musi być parzysta, więc 2 (0 już zajęte). Cecha podzielności przez 2, taka jak w systemie dziesiętnym.
Suma pierwszych trzech cyfr musi być podzielna przez 3 (inaczej nawet zrobić się nie da). Cecha podzielności taka jak dla 9 (zresztą dla trójki też) w systemie dziesiętnym.
w układzie czwórkowym to będzie 1230
a w układzie szóstkowym będzie to 543210
a w układzie dziesiętnym 3816547290
Hmm, treść artykułu sugerowałaby, że w układzie dziesiątkowym jest rozwiązanie, ale mi wyszło, że jednak nie ma.
czwórkowy: 1230, 3210
piątkowy: brak
szóstkowy: 143250, 543210
siódemkowy: brak
ósemkowy: 32541670, 52347610, 56743210
dziewiątkowy,…,dwunastkowy: brak
Ciekawe, czy dla nieskończenie wielu podstaw istnieją rozwiązania…
Dla układu dziesiętnego rozwiązanie jest np. tu
Jeśli chodzi o ostatnie zdanie, to sam jestem ciekaw.
mp
Wydaje mi się, że 3210 w czwórkowym.
Jak się nie pomyliłem przy sprawdzaniu, to 543210. Ciężko w tym okresie znaleźć czas na szukanie dalszych rozwiązań. Poza tym kupiłem sobie i bliskim Omnibus pod choinkę. Wszystkiego dobrego!
Pogodnych Świąt i przyjemnego rozwiązywania (krytyczne uwagi mile widziane :))
mp
2: 10
3: nie ma rozwiązań
4: 3210
5: nie ma rozwiązań
6: 543210
7: nie ma rozwiązań
8: 56743210
9: nie ma rozwiązań
10: 3816547290
11: nie ma rozwiązań
12: nie ma rozwiązań
13: nie ma rozwiązań
14: 9C3A5476B812D0
Rozumiem, że podanie jednego rozwiązania nie oznacza, że jest tylko jedno.
Nie znałem rozwiązań dla podstaw większych niż 10, ale brak dla 12 jest zaskakujący.
mp
Najgorsze są układy, w których podstawa jest liczbą pierwszą. O ile istnieją…
Wszystkie rozwiązania dla wybranych podstaw:
2: 10
3: nie ma rozwiązań
4: 1230 3210
5: nie ma rozwiązań
6: 143250 543210
7: nie ma rozwiązań
8: 32541670 52347610 56743210
9: nie ma rozwiązań
10: 3816547290
11: nie ma rozwiązań
12: nie ma rozwiązań
13: nie ma rozwiązań
14: 9C3A5476B812D0
15: nie ma rozwiązań (dowód z głowy)
16: nie ma rozwiązań
17: ???
18: nie ma rozwiązań
19: nie ma rozwiązań (dowód z głowy)
dość duże podstawy parzyste można „ugryźć” zauważając, że
co druga cyfra jest parzysta; oczywiście na końcu jest zero, a w środku
połowa podstawy.
Zagadnienie dla liczb rzędu 17 i większych to niezły orzech algorytmiczny (ja posługuję się brutalną siłą, generuję wszystkie permutacje, co jest bez sensu, ale rozwiązanie tego problemu z sensem nie jest łatwe)
W każdym bądź razie mamy ciekawy problem: czy w ogóle istnieją rozwiązania inne niż przedstawione powyżej? A może one istnieją dla podstaw postaci 2*p, gdzie p jest liczbą pierwszą – następny kandydat to 22. Na pewno wszelkie podzielności podstawy wprowadzają dodatkowe więzy na poszukiwane rozwiązania.
Można łatwo wykazać brak rozwiązań dla podstaw postaci 4k – 1 (stąd teza o braku rozwiązań dla 15 i 19)
No, no, nie przypuszczałem, że z tego może być taki zawiły i ciekawy problem (przed)świąteczny :).
Z 2*p kłóci się system ósemkowy.
mp
Nie ma dalszych rozwiązań do 32 włącznie.