Pućki bis

21 stycznia 2011
Marek Penszko

Sądziłem, że ktoś z Szanownych Komentatorów ujawni kulisy zadania zamieszczonego w poprzednim wpisie. Ponieważ tak się nie stało, postanowiłem samemu podać źródło. Ogólny problem jest zapewne mało znany, skoro nikt o nim nie wspomniał.

Zadanie o pućkach sprowadzone do abstrakcji brzmiałoby np. tak:

Zbiór składa się z nieskończenie wielu liczb 6, 9 i 20. Jaka jest największa liczba naturalna, nie będąca sumą liczb z tego zbioru?

Aby sprowadzić to zadanie do postaci ogólnej, należałoby zamiast „6, 9 i 20” wstawić „x1, x2, x3,…, xn„. Ponadto wypadałoby dodać, że wszystkie n różnych liczb należących do zbioru nie może mieć wspólnego dzielnika. W przeciwnym wypadku zadanie traci sens (na przykład, korzystając ze zbioru liczb parzystych nie sposób utworzyć żadnej sumy nieparzystej).

Rozwiązywanie jest – w konkretnym przypadku – szukaniem tzw. liczby Frobeniusa (od nazwiska matematyka niemieckiego z przełomu XIX i XX w.).
Ze zbiorem, w którym występują tylko dwie różne względnie pierwsze liczby – x1 i x2 (np. 9 i 20), od dawna (1884 r.) wiadomo jak sobie radzić w prosty sposób. Wystarczy skorzystać ze wzoru:
F = x1x2 – x1 – x2
A zatem jeżeli x1 = 9 i x2 = 20, to F = 151, czyli dysponując dziewiątkami i dwudziestkami nie sposób utworzyć sumy równej 151, a na każdą większą sposób się znajdzie.
Jeśli w zbiorze są trzy różne liczby – x1, x2, x3 (np. 6, 9 i 20), to poradzić sobie z zadaniem w ogólnym przypadku już nie jest tak łatwo. Prostego wzoru nie znamy, choć w niektórych konkretnych sytuacjach można stosować proste sposoby i znane są skuteczne ogólne algorytmy.
Wobec czterech i więcej różnych liczb matematyka jest jak dotąd bezsilna, ale zmagania trwają.

Wracając do pućków, zadanie z poprzedniego wpisu pojawiło się po raz pierwszy przed 20 laty w wersji z McNuggetsami, które sprzedawane są właśnie w porcjach po 6, 9 i 20 sztuk; podobno także po 4, ale głowy nie dam, bo w McDonald’sie nie bywam. Z pobudek patriotycznych zaproponowałem bliższą nam (fonetycznie) potrawę, czyli pućki, do których teraz jeszcze wrócę, ale w nieco innym matematycznym ujęciu.

Klient kupił dwie małe (po 6 sztuk) i dwie duże (po 20 sztuk) puszki pućków. W domu wyjął wszystkie, pomieszał i ułożył na dwóch półmiskach – małym (dla dzieci) i dużym (dla dorosłych). Nie wiedział jednak, że jedna mała i jedna duża puszka były nieszczelne, a w związku tym znajdujące się w nich pućki, które normalnie są słodkie, zgorzkniały. W trakcie konsumpcji okazało się, że na jeden półmisek trafiło dwukrotnie więcej pućków gorzkich niż słodkich, a na drugim liczba słodkich była całkowitą wielokrotnością gorzkich.
Ile i jakich pućków było na każdym półmisku?

Komentarze z prawidłowymi rozwiązaniami uwalniane są wieczorem w przeddzień kolejnego wpisu. Wpisy pojawiają się co 3-4 dni.