Dawno nie było tutaj porządnej łamigłówki. No to teraz już będzie 🙂
Proszę spróbować rozwiązać poniższą zagadkę samodzielnie, bez pomocy Google.
Pewien sklep sprzedaje gwoździe Wilsona w paczkach trzech wielkości: małe, pakowane po sześć sztuk, średnie po dziewięć sztuk oraz duże, po dwadzieścia sztuk gwoździ w paczce.
Pytanie brzmi: jaka jest największa liczba gwoździ Wilsona niemożliwa do kupienia w tym sklepie?
Żeby ułatwić "załapanie" o co chodzi (ludzie często mają problem ze zrozumieniem pytania), podaję przykłady.
Nie da się zamówić 5 gwoździ, bo najmniejsza paczka ma ich 6.
Nie da się zamówić 16 gwoździ. 6 + 6 = 12; 9 + 6 = 15, wszystkie inne kombinacje dają więcej, niż 16.
Da się zamówić 18 gwoździ: 3 x 6 lub 2 x 9.
Nie da się zamówić 37 gwoździ. Jak by człowiek nie kombinował, zawsze wyjdzie 36 albo 38, ale nigdy 37.
Powyżej pewnej liczby da się zamówić każdą ilość, ponieważ liczba kombinacji rośnie tak, że pokrywa szczelnie całą oś liczb naturalnych.
No właśnie. Jaka jest największa liczba, której zamówić się nie da?
Miłego koncypowania 🙂
da się to analitycznie policzyć?
Nie wiem. Mi się to udało wykombinować „na piechotę”, a potem sobie zrobiłem symulację w Excelu, która potwierdziła poprawność wyniku. Jedno i drugie zamierzam wrzucić na bloga za jakiś czas, póki co dam się pomęczyć Czytelnikom 😉
NWD(6,9)=3
Czyli za pomoca paczek po 6 i po 9 gwozdzi jestesmy w stanie uzyskac kazda liczbe postaci 3x, dla x >=2.
Wiec problem mozna zredukowac do uzywania paczek po 3 i po 20 gwozdzi.
A stad juz mozna skorzystac z zaleznosci, ze liczba, ktorej szukamy jest postaci:
A x (B – 1) – B, gdzie NWD(A, B) = 1.
Zatem dla A=20 i B=3, wychodzi:
20 x (3 – 1) – 3 = 37
Zgubiłem się tutaj:
A x (B – 1) – B, gdzie NWD(A, B) = 1
Możesz rozwinąć?
(A przy okazji: Twoja odpowiedź jest nieprawidłowa. Ale i tak chcę spróbować zrozumieć Twój tok rozumowania)
Masz racje, popelnilem blad, bo problemu jednak nie mozna zredukowac do 3 i 20. Wzor wyprowadzilem na podstawie obserwacji w excelu, ale juz nie mialem czasu zeby go udowodnic, ale opieraloby sie to o dzielenie modulo z reszta.