Przy kasie
W poprzednim wpisie było zadanie diagramowe, trudne i żmudne. Tym razem dla odmiany coś prostszego i tekstowego z życia wyższych sfer.
Nikodem Dyzma wszedł do gabinetu Leona Kunickiego, zapalił światło i rozsunął ciężką aksamitną kotarę. We wnęce muru stała wielka, zielona kasa ogniotrwała. Aby ją otworzyć, należało – jak powiedział Kunicki – nastawić górną rozetę na dziewiątkę, a dolną na siódemkę, tylko że na drzwiach.. nie było rozet. Zamiast nich był zamek szyfrowy z trzema okienkami, w których ustawiało się cyfry, czyli ogólnie 3-cyfrową liczbę. W pierwszej chwili Dyzma pomyślał, że stary lis wystrychnął go na dudka, ale natychmiast zreflektował się, bo przecież otworzenie kasy leżało w interesie Kunickiego. Sięgnął więc po komórkę, zadzwonił do pryncypała i opisał zastaną sytuację. Okazało się, że Kunicki przed kilkoma dniami wymienił starą kasę na nową. Konkretnego szyfru nie mógł sobie przypomnieć, ale korzystając z mnemotechniki zapamiętał jego szczególną własność. Dyzma usłyszał więc, że liczba-szyfr jest czterokrotnie większa od iloczynu jej cyfr. Teraz stoi bezradnie przed kasą i żałuje, że w szkole nie przykładał się do matematyki. Krzepicki, który mógłby mu pomóc, nie odbiera telefonu.
Kto pomoże Dyzmie i rozszyfruje szyfr?
PS Poza konkretną liczbą mile widziane będą zwięzłe opisy eleganckiego sposobu rozwiązania tego zadania.
Komentarze
Czy ten wstęp o rozetach ustawionych na 9 i 7 jest potrzebny do rozwiązania zadania?
Zdaje się, że zadanie sprowadza się do odnalezienia liczby trzycyfrowej, która jest cztery razy większa od iloczynu jej cyfr, tak?
Oczywiście. Wstęp jest tylko fabułką nawiązującą do znanej powieści (i znakomitego serialu).
mp
1. szukana liczba musi być poodzielna przez 4
2. zatem liczba dwucyfrowa będącą końcówką szukanej liczby również musi być podzielna przez 4 (są 24 takie liczby dwucyfrowe i jednocyfrowe: 4, 8, 12, 16…96)
3. nie może występować zero (odrzucamy 4, 8, 20, 40, 60, 80, pozostaje 18 liczb)
4. odrzucamy 16, oraz liczby zawierające 2: 24, 32, 72, 92 gdyż iloczyn ich cyfr wraz z cyfrą setek rośnie wolniej niż sama liczba (z cyfrą setek)
5. odrzucamy liczby, które iloczyn cyfr dają wynik wyrażony w okrągłych dziesiątkach a zatem 52, 56, pozostaje 10 liczb
6. dalej metodą prób i błędów dochodzimy do liczby 384 – jedynej, która spełnia warunki zadania
Odpowiedz to 384.
Mój sposób rozumowania:
1. Liczba musi dzielić się przez 4 (gdyż jest czterokrotnością iloczynu swych cyfr i nie może dzielić się przez 5 (wówczas ostatnia cyfra musiałaby być 0). Oznacza to też że wśród cyfr tej liczby nie ma żadnej piątki ani zera.
2. Jeśli liczba ma postać abc czyli jest równa 100a+10b+c to z warunku:
100a+10b+c=4abc mamy a=(10b+c)/(4bc-100), czyli w szczególności:
a) 4bc>100 => bc>25
b) 4bc-100 bc<50
3. Warunki 1 i 2 spełniają tylko następujące liczby: a48, a68, a76, a84 (gdzie a jest nieznana cyfra setek).
4. Po sprawdzeniu każdej z czterech możliwości okazuje się ze prawidłowa odpowiedzią jest 384.
Rozwiązanie to 384 ale znalazłem je za pomocą arkusza. W ramach „pokuty” proponuję drobną korektę opowieści
„Niestety w Koborowie zawsze były zakłócenia na linii, więc Nikodem nie usłyszał przez jaka liczbę przemnożył Kunik szyfr ale zapamiętał, że żadna z liczb się nie powtarzała i wszystkie były nieparzyste … lub parzyste ( z tym zawsze miał problem).”
Rozwiązujemy równanie 100*a+10*b+c=4*a*b*c względem a
a=((c+10*b)/(4*b*c-100)), ponieważ c jest parzyste i większe od zera to dla
c=2 a=((5*b+1)/(4*b-50)) dla dowolnego b>10 a zawsze będzie ujemne
c=4 a=((5*b+2)/(8*b-50)) b>6 i dla b=8 a=3 czyli mamy rozwiązanie 384
c=6 a=((5*b+3)/(12*b-50)) brak rozwiązań
c=8 a=((5*b+4)/(16*b-50)) brak rozwiązań
Jedynym rozwiązaniem jest liczba 384=4*3*8*4
2b mialo byc naturalnie:
b) 4bc-100 bc<50
Pierwsze, co mi przyszło do głowy, to 000.
Potem wymyśliłam tyle, że ta 3-cyfrowa liczba nie zawiera 0 i jest podzielna przez 4. No tak, ale takich liczb jest mnóstwo. Jak znaleźć w tym stogu siana igłę, nie wiem. Excel znalazł w trymiga:
384 = 4 * 3 * 8 * 4
Rozwiązanie – jest, zwięzły opis skąd – jest, z elegancją – gorzej.
Mamy równanie:
100*A+10*B+C = 4*A*B*C (*)
Mamy rozwiązanie trywialne 0,0,0, czego nie powinniśmy z góry odrzucać
bo kasa jest nowa i może być jeszcze ustawiony standardowy szyfr fabryczny 😉
Jeśli choć jedna cyfra = 0 to wszystkie są równe 0.
Dalej zakładamy więc, że A, B, C nalezą do {1, 2,…,9}.
Liczba 10*B+C musi być podzielna przez 4 i nie kończyć się zerem.
Jest tych liczb 18 i są to:
12, 16, 24, 28, 32, 36, 44, 48, 52, 56, 64, 68, 72, 76, 84, 88, 92, 96.
Z równania (*) wyliczamy A = (10*B+C)/(4*(B*C-25))
Widzimy, że B*C musi być większe od 25, więc zostaje tylko 7 liczb:
48, 56, 68, 76, 84, 88, 96.
Podstawiając do wzoru na A znajdujemy, że tylko jedna z nich daje całkowite
A = (10*8+4)/(4*(8*4-25)) = 84/28 = 3
Więc szyfr ABC = 384.
x liczba setek
y liczba dziesiątek
z liczba jedności
Mamy więc
100x+10y+z= 4xyz (1);
x,y,z różne od zera, całkowite,dodatnie z przedziału 1-9. Dla x=y=z rozwiązanie trywialne.
Szukana liczba jest podzielna przez 4 więc liczba powstała z dwu ostatnich cyfr musi być podzielna
przez 4. Mamy 18 liczb dwucyfrowych :12,16,24,28,32,36,44,48,52,56,64,68,72,76,84,88,
92,96. Podstawiając kolejno do (1) mamy;
100x+10+2=4*1*2*x
100x+12=8x
92x=-12
x nie może być ujemny i musi być całkowity, więc y*z musi być większe od 25.
Eliminuje to 9 liczb dwucyfrowych, sprawdzamy pozostałe, wynik musi być całkowity.
Poprawna odpowiedź jest dla 84.
100x+84 =128x
84= 28x
x=3.
Szyfr ma klucz 384.
000 dla zmyły 😉
Trzycyfrowa liczba podzielona przez jej pierwszą cyfrę (różną od zera) da nam wynik z przedziału 100-199. Podzielone przez 4 da 25-49.
Szyfr dzieli się przez 4, więc ostatnie dwie cyfry (po wykluczeniu zer) wybieramy spośród osiemnastu par. Jeśli ich iloczyn jest z naszego przedziału 25-49, to próbujemy dopasować cyfrę setek. Tutaj też nie trzeba kombinować wiele, bo dostaniemy:
ABC => B*C*4 = 1XY oraz A*1XY = ABC, więc BC musi być wielokrotnością XY.
Pary wpadające do przedziału: 48, 56, 68, 76, 84.
B*C*4 = kolejno: 128, 120, 192, 168, 128 – po obcięciu jedynki, tylko ta ostatnia zwielokrotniona daje wyjściową parę: 3*128 = 384 => szyfr.
384
Znaleźć liczbę to nie problem, gorzej z elegancją 🙂
Oznaczmy szukaną liczbę w zapisie pozycyjnym przez
[abc] = 100a + 10b + c. Warunek zadania to: [abc] = 4abc.
Jeśli pominąć rozwiązanie zerowe, to a,b,c ≥ 1 oraz c parzyste, więc 8|[abc].
Jeśli już to wiemy, wystarczy zbadać wszystkie krotności 8-ki między 112 a 998 na spełnienie warunku zadania. Jest ich tylko 110 (nawet mniej o 22-wie krotności 5-ki z c=0). Mając arkusz kalkulacyjny i odrobinę wprawy zrobimy to w czasie góra 5 min znajdując jedyne rozwiązanie równe 384. To szybki sposób ale średnio elegancki bo zbliżony do metody brute force.
Jeśli spróbujemy trochę pobawić się tym równaniem, możemy znaleźć dodatkowe warunki np. podzielności: 4|2b±c oraz 5|(ab+1). Można sporządzić dwie tabelki wartości tych wyrażeń, zaznaczając pary cyfr spełniające ww. warunki podzielności. Otrzymamy 18 par [bc] i 16 par [ab]. Niestety trzeba jeszcze w kolejnej tabelce sparować pary [ab] z [bc] aby wyłapać wspólną wartość b. Dostaniemy 32 możliwe układy [abc], które i tak trzeba jeszcze sprawdzić pod kątem spełniania warunku (tylko 384 go spełnia).
Dużo pracy, mały postęp a i tak praktycznie potrzeba arkusza.
Chyba jednak nie o to tu chodziło…
Istotnie, to jeszcze nie to…, bo można „eleganciej”.
mp
384
Zadanie sprowadza się do rozwiązania równania diofantycznego:
100*a + 10*b + c = 4*a*b*c
Dla komputera sprawdzenie wszystkich 504 możliwości to ułamek sekundy. Ale z treści zadania nie wynika, by Dyzma komputerem dysponował.
Można zmniejszyć liczbę rozpatrywanych możliwości do 72, przekształcając równanie do postaci:
a = (10*b + c)/(4*b*c – 100)
i sprawdzając, dla jakiej pary (b,c) a będzie liczbą naturalną 25, a zatem c może być równe 4, 6 lub 8
– jeżeli c jest podzielne przez 4, to b musi być parzyste, jeżeli nie, to b jest nieparzyste
W rezultacie udało się zredukować liczbę możliwych par (b,c) do pięciu: (4,8), (6,8), (7,6), (8,4) i (9,6).
Tu kończy się eleganckie rozwiązanie i podstawiamy kolejne pary (b,c) do wzoru na a (na szczęście już tylko 5, a nie 72, więc chyba Dyzma, nawet bez kalkulatora, dałby sobie z tym radę).
Jedyne rozwiązanie to: a = 3, b = 8, c = 4.
Co wiemy lub łatwo wywnioskować? Szukamy liczby 3-cyfrowej [abc] = 100a + 10b + c = 4abc. Pomijając rozwiązanie zerowe, cyfry muszą spełniać: a,b,c ≥ 1 i a,b ≠ 5. Ponieważ 4|[abc] więc cyfra c jest parzysta a zatem 8|[abc]. Łatwo oszacować, że 112 ≤ [abc] ≤ 998. Nikodem Dyzma nie ma kalkulatora ani komputera więc musi wystarczyć ołówek i papier.
Łatwo znaleźć możliwe układy cyfr b i c. Równanie szyfru przekształcę do postaci: 4a(25 – bc) = -10b – c, skąd 25 jest mniejsze od bc. Prosta tabliczka mnożenia wymiaru 8×4 wskaże 12 liczb [bc] (=10b+c) o wartości iloczynu cyfr bc większej niż 25, z czego tylko 6 liczb dzieli się przez 4: 48; 68; 76; 84; 88; 96.
Do każdej z tych 6 par [bc] znajdę możliwe cyfry ‘a’ z warunku 8|[abc], korzystając z kryterium podzielności przez 4 liczby: [ab] + c/2 = 10a + b + c/2. Dla znalezionych 6 par [bc]:
48; 68; 76; 84; 88; 96
wyliczam pomocniczą wielkość h = b + c/2, odpowiednio:
8; 10; 10; 10; 12; 12
Kiedy 4|(10a+h)?
Jeśli h=8 lub h=12, to 4|h, więc musi być 4|10a czyli ‘a’ jest cyfrą parzystą (ponadto a>0).
Jeśli h=10, to 10a+h = 10(a+1), więc ‘a’ jest cyfrą nieparzystą (ponadto a≠5).
Pozostają do rozpatrzenia następujące 6*4=24 możliwe układy cyfr: a – bc
2\4\6\8 – 48; 1\3\7\9 – 68; 1\3\7\9 – 76; 1\3\7\9 – 84; 2\4\6\8 – 88; 2\4\6\8 – 96
Ponieważ 4*(6*6*7) = 1008 > 998 możemy odrzucić przypadki, gdzie wszystkie cyfry są ≥ 6 i przynajmniej jedna ≥ 7. Także 4*(4*8*8) = 1024 (liczymy w pamięci) więc wyrzucamy przypadki z cyfrą 4 jeśli pozostałe są ≥ 8. Przypadki z [bc] równym 48 i 88 oraz a≠6 można względnie łatwo wykluczyć, bo wtedy wszystkie cyfry są potęgami dwójki, a więc także liczba 4abc. Pomiędzy 112 oraz 998 są tylko 3 potęgi dwójki:128, 256, 512. Środkową można przeliczyć ale pozostałe mają tak niskie cyfry, że 4-krotne iloczyny cyfr są mniejsze od samych liczb (liczymy w pamięci).
Bez wielkich rachunków udało się zredukować zadanie do 10 przypadków, które można od biedy sprawdzić bezpośrednio – nastawami sejfu lub rachunkiem.
648; 168; 368; 176; 376; 184; 384; 784; 296; 496
Szukanym szyfrem okaże się 384. Tyle zdołałem wymyślić ale pewnie można prościej..
Dawno nie rozwiązywałem, a teraz jak już rozwiązałem, to nagle się okazało, że rozwiązania opublikowane są. Ponieważ jednak uczciwie rozwiązałem 384, więc dopisuję się. Widzę, że podobnie jak @Spytko proponuję zacząć od 18 liczb xy, stanowiących cyfry dziesiątek i jedności, dalej jest po fryzjersku, czyli sprawdzanie nożyc 1xy, 2xy, versus 4*x*y, 8*x*y, etc., czyli mamy np. dla 48 takie dwie kolumny, po lewej 148, po prawej 4×32=128, dalej po lewej 248, po prawej 256… tak więc mamy już po prawej liczbę większą niż po lewej, a więc od tego momentu nożyce będą się rozwierać i już nie potrzeba dalej sprawdzać. Można nożyce badać raz z lewej, „od jedynki”, raz z prawej, „od dziewiątki”, jeśli np. 912 > 9*1*2*4 = 72, a 112 > 8, to punkt przecięcia nożyc leży w ogóle poza zakresem 100-999. No i jedynym rozwiązaniem okazuje się 384. Właściwie to jest 16 liczb nie 18, @filipo ma rację, że odpadają piątki, czyli 52 i 56.