S\u0105dzi\u0142em, \u017ce kto\u015b z Szanownych Komentator\u00f3w ujawni kulisy zadania zamieszczonego w poprzednim wpisie. Poniewa\u017c tak si\u0119 nie sta\u0142o, postanowi\u0142em samemu poda\u0107 \u017ar\u00f3d\u0142o. Og\u00f3lny problem jest zapewne ma\u0142o znany, skoro nikt o nim nie wspomnia\u0142.<\/p>\n
Zadanie o pu\u0107kach sprowadzone do abstrakcji brzmia\u0142oby np. tak:<\/p>\n
Zbi\u00f3r sk\u0142ada si\u0119 z niesko\u0144czenie wielu liczb 6, 9 i 20. Jaka jest najwi\u0119ksza liczba naturalna, nie b\u0119d\u0105ca sum\u0105 liczb z tego zbioru?<\/em><\/p>\n Aby sprowadzi\u0107 to zadanie do postaci og\u00f3lnej, nale\u017ca\u0142oby zamiast „6, 9 i 20<\/em>” wstawi\u0107 „x<\/em>1<\/sub><\/span><\/span>, x<\/em>2<\/sub><\/span>, x<\/em>3<\/sub><\/span>,…, x<\/em>n<\/sub><\/span>„. Ponadto wypada\u0142oby doda\u0107, \u017ce wszystkie n<\/em> r\u00f3\u017cnych liczb nale\u017c\u0105cych do zbioru nie mo\u017ce mie\u0107 wsp\u00f3lnego dzielnika. W przeciwnym wypadku zadanie traci sens (na przyk\u0142ad, korzystaj\u0105c ze zbioru liczb parzystych nie spos\u00f3b utworzy\u0107 \u017cadnej sumy nieparzystej).<\/p>\n Rozwi\u0105zywanie jest\u00a0– w konkretnym przypadku\u00a0– szukaniem tzw. liczby Frobeniusa<\/strong> (od nazwiska matematyka niemieckiego z prze\u0142omu XIX i XX w.). Wracaj\u0105c do pu\u0107k\u00f3w, zadanie z poprzedniego wpisu pojawi\u0142o si\u0119 po raz pierwszy przed 20 laty w wersji z McNuggetsami, kt\u00f3re sprzedawane s\u0105 w\u0142a\u015bnie w porcjach po 6, 9 i 20 sztuk; podobno tak\u017ce po 4, ale g\u0142owy nie dam, bo w McDonald’sie nie bywam. Z pobudek patriotycznych zaproponowa\u0142em bli\u017csz\u0105 nam (fonetycznie) potraw\u0119, czyli pu\u0107ki, do kt\u00f3rych\u00a0teraz jeszcze wr\u00f3c\u0119, ale w nieco innym matematycznym uj\u0119ciu.<\/p>\n Klient kupi\u0142 dwie ma\u0142e (po 6 sztuk) i dwie du\u017ce (po 20 sztuk) puszki pu\u0107k\u00f3w. W domu wyj\u0105\u0142 wszystkie, pomiesza\u0142 i u\u0142o\u017cy\u0142 na dw\u00f3ch p\u00f3\u0142miskach\u00a0– ma\u0142ym (dla dzieci) i du\u017cym (dla doros\u0142ych). Nie wiedzia\u0142 jednak, \u017ce jedna ma\u0142a i jedna du\u017ca puszka by\u0142y nieszczelne, a w zwi\u0105zku tym znajduj\u0105ce si\u0119 w nich pu\u0107ki, kt\u00f3re normalnie s\u0105 s\u0142odkie, zgorzknia\u0142y. W trakcie konsumpcji okaza\u0142o si\u0119, \u017ce na jeden p\u00f3\u0142misek trafi\u0142o dwukrotnie wi\u0119cej pu\u0107k\u00f3w gorzkich ni\u017c s\u0142odkich, a na drugim liczba s\u0142odkich by\u0142a ca\u0142kowit\u0105 wielokrotno\u015bci\u0105 gorzkich. Komentarze z prawid\u0142owymi<\/strong> rozwi\u0105zaniami uwalniane s\u0105 wieczorem w przeddzie\u0144 kolejnego wpisu. Wpisy pojawiaj\u0105 si\u0119 co 3-4 dni.<\/span><\/p>\n","protected":false},"excerpt":{"rendered":" S\u0105dzi\u0142em, \u017ce kto\u015b z Szanownych Komentator\u00f3w ujawni kulisy zadania zamieszczonego w poprzednim wpisie. Poniewa\u017c tak si\u0119 nie sta\u0142o, postanowi\u0142em samemu poda\u0107 \u017ar\u00f3d\u0142o. Og\u00f3lny problem jest zapewne ma\u0142o znany, skoro nikt o nim nie wspomnia\u0142. Zadanie o pu\u0107kach sprowadzone do abstrakcji brzmia\u0142oby np. tak: Zbi\u00f3r sk\u0142ada si\u0119 z niesko\u0144czenie wielu liczb 6, 9 i 20. Jaka […]<\/p>\n","protected":false},"author":3,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[],"_links":{"self":[{"href":"https:\/\/blog.polityka.pl\/penszko\/wp-json\/wp\/v2\/posts\/1028"}],"collection":[{"href":"https:\/\/blog.polityka.pl\/penszko\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blog.polityka.pl\/penszko\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blog.polityka.pl\/penszko\/wp-json\/wp\/v2\/users\/3"}],"replies":[{"embeddable":true,"href":"https:\/\/blog.polityka.pl\/penszko\/wp-json\/wp\/v2\/comments?post=1028"}],"version-history":[{"count":0,"href":"https:\/\/blog.polityka.pl\/penszko\/wp-json\/wp\/v2\/posts\/1028\/revisions"}],"wp:attachment":[{"href":"https:\/\/blog.polityka.pl\/penszko\/wp-json\/wp\/v2\/media?parent=1028"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blog.polityka.pl\/penszko\/wp-json\/wp\/v2\/categories?post=1028"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blog.polityka.pl\/penszko\/wp-json\/wp\/v2\/tags?post=1028"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}
\nZe zbiorem, w kt\u00f3rym wyst\u0119puj\u0105 tylko dwie r\u00f3\u017cne wzgl\u0119dnie pierwsze liczby\u00a0– x<\/em>1<\/sub><\/span> i x<\/em>2<\/sub><\/span> (np. 9 i 20), od dawna (1884 r.) wiadomo jak sobie radzi\u0107 w prosty spos\u00f3b. Wystarczy skorzysta\u0107 ze wzoru:
\nF = x<\/em>1<\/sub><\/span>x<\/em>2<\/sub><\/span>\u00a0– x<\/em>1<\/sub><\/span>\u00a0– x<\/em>2<\/sub><\/span>
\nA zatem je\u017celi x<\/em>1<\/sub><\/span> = 9 i x<\/em>2<\/sub><\/span> = 20, to F = 151, czyli dysponuj\u0105c dziewi\u0105tkami i dwudziestkami nie spos\u00f3b utworzy\u0107 sumy r\u00f3wnej 151, a na ka\u017cd\u0105 wi\u0119ksz\u0105 spos\u00f3b si\u0119 znajdzie.
\nJe\u015bli w zbiorze s\u0105 trzy r\u00f3\u017cne liczby\u00a0– x1<\/sub><\/span>, x2<\/sub><\/span>, x3<\/sub><\/span> (np. 6, 9 i 20), to poradzi\u0107 sobie z zadaniem w og\u00f3lnym przypadku ju\u017c nie jest tak \u0142atwo. Prostego wzoru nie znamy, cho\u0107 w niekt\u00f3rych konkretnych sytuacjach mo\u017cna stosowa\u0107 proste sposoby i znane s\u0105 skuteczne og\u00f3lne algorytmy.
\nWobec czterech i wi\u0119cej r\u00f3\u017cnych liczb matematyka jest jak dot\u0105d bezsilna, ale zmagania trwaj\u0105.<\/p>\n
\nIle i jakich pu\u0107k\u00f3w by\u0142o na ka\u017cdym p\u00f3\u0142misku?<\/em><\/p>\n