Nie przez 7
Z dziewięciu różnych cyfr większych od zera wybieramy cztery, których suma podzielna jest przez 7. Z tych cyfr próbujemy utworzyć 4-cyfrową liczbę (bez powtarzania cyfr) podzielną przez 7.
Na przykład, po wybraniu cyfr 5, 6, 8, 9 (suma 28|7) sprawa jest prosta, bo z 24 liczb możliwych do utworzenia aż sześć dzieli się przez 7 (5698, 6895, 6958, 8596, 8659, 9856). Celem jest znalezienie takiego kwartetu, z którego nie uda się złożyć żadnej 4-cyfrowej wielokrotności siedmiu.
Czy z tym zadaniem można się uporać „na piechotę” bez żmudnego wybierania odpowiednich czwórek cyfr i sprawdzania podzielności przez 7 składanych z nich liczb, czyli bez stosowania metody siłowej albo przynajmniej jakoś ją sprytnie ograniczając? Oto jest pytanie.
Komentarze
Wikipedia, hasło kakuro, kopiuję do notatnika 4-elementowe sumy liczb 14, 21 i 28. Funkcją „znajdź i zamień” usuwam plusy oraz przecinki. Dostaję 18 liczb. Przekopiowuję je do excela i dzielę na 7. Usuwam 2 liczby, które dzielą się bez reszty, zostaje 16 liczb. Każdą z nich permutuję bez powtórzeń, co daje 16 pul po 24 liczby. Dzielę wszystko na 7 i sprawdzam, w której puli nie ma ilorazów całkowitych. Okazuje się, że są trzy takie pule: 1238, 1389 i 2469. Kwadrans pracy.
Pytanie tylko, czy spełniłam warunki zadania. Taki sposób określa Pan jako żmudny? Trzeba może więcej myśleć przy tym, nie tylko „kopiuj”, „wklej”, „permutuj”, „dziel” klikać?
To oczywiście nie jest żmudne i to jest całkiem sprytne, ale to nie jest „na piechotę”.
Wypisania wszystkich 18 4-cyfrowych kombinacji chyba nie da się „przebiec”, ale dalej – tak mi się wydaje – można, główkując (ale nie korzystając z programu), przynajmniej trochę uprościć zmagania.
mp
Robię drugie podejście – piechotą 🙂
Można przyglądać się zestawowi 4 cyfr i w myślach układać sumy, których składniki są podzielne przez 7. Składniki te warto wybierać spośród liczb: 1001, 2002, 3003, …, 9009; 105, 203, 301, 406, 504, 602, 700, 805, 903 oraz oczywiście 2-cyfrowych, których nie będę wymieniać. Na początku jest może trochę trudno, ale jak się nabierze wprawy, to łamigłówka robi się całkiem przyjemna. Na przykład:
1479
– dopasowuję na próbę 9009 + 406, wykorzystałam 9 i 4, zostało 17 lub 71,
– z końcówek mam 9+6=15,
– sprawdzam, czy 17 lub 71 po odjęciu 15 da liczbę podzielną przez 7,
– okazuje się, że 71 – 15 = 56, bingo,
– cały zestaw to 9009 + 406 + 56 = 9471,
– liczba 9471 jest podzielna przez 7, bo jej składniki są.
1569
– dopasowuję na próbę 6006 + 903, wykorzystałam 6 i 9, zostało 15 lub 51,
– z końcówek mam 6+3=9,
– sprawdzam, czy 15 lub 51 po odjęciu 9 da liczbę podzielną przez 7,
– okazuje się, że 51 – 9 = 42, bingo,
– cały zestaw to 6006 + 903 + 42 = 6951,
– liczba 9651 jest podzielna przez 7, bo jej składniki są.
1247
– dopasowuję na próbę 1001 + 203, to daje razem 1204, i jeszcze 70 – mamy całość,
– liczba 1274 jest podzielna przez 7, bo jej składniki są.
Itd. Itp.
Jak już napisałam wyżej, ćwiczenie jest całkiem fajne. Wcale nie żmudne 😉 Oczywiście, co kto lubi.
Właśnie o czymś podobnym myślałem, ale w prostszej wersji: zrestaw cyfr odpada, jeśli z jego cyfr można utworzyć dwie liczby podzielne przez 7.
Np. z [1569] powstaną liczby 56|7 i 91|7 natomiast z [1578] 7|7 i 518|7. W ten sposób da się łatwo odrzucić 10 kwartetów cyfr. Potem można korzystać z Pani sposobu nieco bardziej zakręconego.
mp
To powinny być cyfry: 2, 4, 6, 9. Ale nie jestem usatysfakcjonowany, bo trochę przypadkiem to wyszło. Badałem w excelu liczby trzycyfrowe (trzy cyfry wyznaczają czwartą n lub dwie możliwe czwarte, jak 1 i 8 czy 2 i 9, no ale to się sprowadza do różnicy podzielnej przez 7) i wszędzie dość szybko okazywało się, że po dodaniu n tysięcy pojawiają się liczby podzielne przez 7. Może to jest patent: sprawdzać po kolei trójki, nie jest ich niezmiernie dużo. Np. 1, 2, 3 mamy 8; 1, 2, 4 dochodzi 7; 1,2,5 uzupełnia 6 i możliwości dla 1 i 2 już się kończą. 1, 3, 4 znów 6, a potem dopiero 1, 3, 8 i 9, itd. W każdym razie natchnęło mnie, by przetestować czwórkę, gdzie nie ma dwóch cyfr sąsiednich: 2, 4, 6 i 9. Nie ułoży się z nich liczby podzielnej przez 7, ale nie potrafię udowodnić, że jak są dwie cyfry sąsiednie, to na pewno się da, tym samym nie wiem, czy to jedyne rozwiązanie. Inny taki zestaw to 1, 4, 7, 9, ale tu np. 1974 jest podzielne przez 7. Podzielność przez 7 jest skomplikowana, cecha podzielności dla liczb czterocyfrowych jest taka, że jak się skreśli pierwszą cyfrę otrzymując liczbę trzycyfrową, a potem odejmie tę skreśloną, to otrzyma się liczbę podzielną przez 7, np. 2100 jest podzielna, bo 100-2 = 98 jest podzielna. Ale jak to wykorzystać w tym zadaniu, czy w ogóle się da – nie wiem.
Tym zadaniem zajmowałem się wcześniej w ramach Umysłu Giętkiego z tym, że doprecyzowałem sobie dyspozycję do postaci:
Znaleźć WSZYSTKIE takie kwartety (tj. złożone z 4 różnych cyfr dodatnich, które sumują się do krotności 7, z których nie da się złożyć żadnej 4-cyfrowej krotności 7).
W tej postaci zadanie jest na tyle żmudne obliczeniowo, że warto pogłówkować by je trochę uprościć. Moje podejście jest niestety dalekie od rozwiązania „na piechotę” ale zawiera jakąś metodę inną niż brute force. Ponieważ odpowiedzi jest niewiele dorzucę swoje 3 grosze.
Kryterium podzielności przez 7 ułatwi rachunki. Niech a,b,c,d będą cyframi:
1000a+100b+10c+d = (1001a+98b+7c)+(-a+2b+3c+d) = 7k+(-a+2b+3c+d)
Jak wiadomo wystarczy więc badać podzielność mniejszej liczby (powstałej z zastąpienia potęg 10 ich resztami modulo 7). Niestety, nie jest to takie przyjemne i symetryczne kryterium jak dla dzielników 3 i 9. Tu dla danego kwartetu jedna liczba 4-cyfrowa może być podzielna przez 7, a po przestawieniu cyfr już nie, lub odwrotnie. Dlatego wątpię żeby to zadanie można było rozwiązać całkiem „na piechotę” bez rachunków, ale oczywiście mogę się mylić.
Istotny jest warunek na sumę cyfr:
-a+2b+3c+d = -2a+b+2c+(a+b+c+d) = b+2(c-a)+7j
Badanie podzielności liczby 4-cyfrowej sprowadza się więc do kryterium zależnego tylko od tercetu cyfr, a takich tercetów jest sporo mniej! Plan był taki, żeby najpierw sprawdzić tercety potencjalnie odpowiednie (tj. nie spełniające kryterium podzielności w dowolnej permutacji), a potem sprawdzić możliwość rozszerzenia tercetu o czwartą cyfrę dopełniającą sumę do krotności 7.
W tabelce w wierszach wypisałem (rosnąco) wszystkie 84 kombinacje 3-cyfrowe a,b,c wybrane z 9 cyfr – niestety, to już jest pewna praca. W 6 kolumnach sprawdziłem podzielność wartości wyrażeń a+2(b-c) dla wszystkich 6 permutacji 3 cyfr a,b,c z każdego wiersza. Zerowość reszty modulo 7 w dowolnej permutacji przekreśla szanse tercetu. Dlatego warunki te można połączyć odp. w pary, a pary przemnożyć przez siebie, żeby sprawdzać wartości tylko 3 kombinacji wyrażeń postaci a^2-(b-c)^2 w 3 kolumnach. W ten sposób znalazłem potencjalnie dobre tercety.
Następnie dodałem 3 kolumny dla sprawdzenia 4-ej cyfry d, w których odjąłem od 3 możliwych w tym zadaniu wartości sumy kwartetu (14,21,28) sumę każdego tercetu. Jeśli różnica jest cyfrą dodatnią, różną od każdej cyfry tercetu, to można dobrać 4-ą cyfrę kwartetu do odpowiedniej sumy.
Kolumna sukcesów obu testów wskazała 5 obiecujących kwartetów, które trzeba jeszcze sprawdzić (ale tylko te 5), gdyż mogą zawierać tercet nieodpowiedni z udziałem czwartej cyfry (dobieranej tylko pod kątem sumy, nie tercetu). Ta korekta eliminuje 2 kwartety spośród 5-ciu. Ostateczne rozwiązanie tworzą 3 kwartety:
1 2 3 8
1 3 8 9
2 4 6 9
Kompletną analizę zadania zapewnia więc tabela formuł wymiaru: 84 wiersze x ~9 kolumn. To nie jest żaden przełom ale chyba jakieś uproszczenie…
PS. Ale jak się tak teraz temu przyglądam z dystansu, to zysk tej całej analizy jest znikomy, a liczony czasem – wręcz ujemny. Skoro i tak wykorzystuję komputer, to da on sobie spokojnie radę z badaniem podzielności większych liczb i większych tabel, które można ułożyć od razu 🙁