\n
![\"kropki](\"https:\/\/www.beta-iks.pl\/wp-content\/uploads\/2024\/04\/kropki01.png\")
<\/p>\n\nNa ile sposob\u00f3w mo\u017cna umie\u015bci\u0107 10 nierozr\u00f3\u017cnialnych kul w 5 rozr\u00f3\u017cnialnych urnach? Okazuje si\u0119, \u017ce ten, i podobne problemy mo\u017cna rozwi\u0105za\u0107 u\u017cywaj\u0105c prostego triku.
\n<\/p>\n
\nRozmieszczanie nierozr\u00f3\u017cnialnych kul w rozr\u00f3\u017cnialnych urnach mo\u017ce wydawa\u0107 si\u0119 niekt\u00f3rym problemem rzucaj\u0105cym pewne wyzwanie. Jak zobaczymy mo\u017cna sobie z nim poradzi\u0107 bardzo prosto. Wystarczy tylko odpowiednio na niego spojrze\u0107. My spojrzymy na te zagadnienie z perspektywy kropek i s\u0142upk\u00f3w. Na pocz\u0105tek rozwa\u017cmy sytuacj\u0119, gdy mog\u0105 zdarzy\u0107 si\u0119 urny puste. Wymagamy jedynie aby ka\u017cda kula znalaz\u0142a si\u0119, w kt\u00f3rej\u015b urnie. W skrajnym przypadku wszystkie mog\u0105 wyl\u0105dowa\u0107 w jednej urnie.<\/p>\n
\nZrobimy prosty rysunek, kt\u00f3ry natychmiast pozwoli nam rozwi\u0105za\u0107 nie tylko ten problem.
\n<\/p>\n
\nMamy 10 du\u017cych kropek, z kt\u00f3rych ka\u017cda oznacza naturalnie jedn\u0105 kul\u0119. Za\u015b s\u0142upki dziel\u0105 owe kule na poszczeg\u00f3lne urny. Ka\u017cdy kolejny s\u0142upek jest zarazem ko\u0144cem jednej jak i pocz\u0105tkiem kolejnej urny. Jedynie pierwsza urna nie ma pocz\u0105tkowego s\u0142upka, a ostatnia nie ma ko\u0144cowego. W naszym przyk\u0142adzie pierwszy s\u0142upek znajduje si\u0119 za pierwsz\u0105 kul\u0105. Zatem w pierwszej urnie znajduje si\u0119 jedna kula. Drugi s\u0142upek jest zaraz za pierwszym. Oznacza to, \u017ce druga urna jest pusta. Mi\u0119dzy drugim a trzecim s\u0142upkiem mamy 4 kule, czyli w trzeciej urnie znajduj\u0105 si\u0119 w\u0142a\u015bnie 4 kule itd. Mo\u017cna ju\u017c w zasadzie zrozumie\u0107 ide\u0119. Ka\u017cde rozmieszczenie s\u0142upk\u00f3w to jeden podzia\u0142 kulek na poszczeg\u00f3lne urny. Teraz przejd\u017amy do og\u00f3lnego rozwi\u0105zania.<\/p>\n
\nMamy 10 kropek\/kul oraz 5 urn. Poniewa\u017c ka\u017cdy s\u0142upek oddziela dwie urny, to potrzebujemy czterech s\u0142upk\u00f3w aby podzieli\u0107 kule mi\u0119dzy 5 urn. W og\u00f3lno\u015bci, potrzeba \\(k-1\\) s\u0142upk\u00f3w aby dokona\u0107 podzia\u0142u kul na \\(k\\) urn. W naszym przypadku, mamy 10 kropek i 4 s\u0142upki, czyli \u0142\u0105cznie 14 obiekt\u00f3w. Ka\u017cde rozmieszczenie s\u0142upk\u00f3w daje nam podzia\u0142 kul na urny. Co oczywiste, inne rozmieszczenia s\u0142upk\u00f3w prowadz\u0105 do innych podzia\u0142\u00f3w kul mi\u0119dzy rozr\u00f3\u017cnialne urny. Wystarczy teraz zauwa\u017cy\u0107 tylko, \u017ce ka\u017cde rozmieszczenie naszych 4 s\u0142upk\u00f3w jest niczym innym jak czteroelementowym podzbiorem zbioru wszystkich naszych obiekt\u00f3w, kt\u00f3rych jest 14. Czyli jest \\[{14 \\choose 4} = 1001\\] sposob\u00f3w na umieszczenie 10 kul w 5 rozr\u00f3\u017cnialnych urnach. W og\u00f3lno\u015bci, gdy mamy \\(n\\) kul oraz \\(k\\) urn, to takich sposob\u00f3w jest \\[{n+k-1 \\choose k-1}.\\]<\/p>\n
\nTeraz rozwa\u017cmy problem, w kt\u00f3rym w ka\u017cdej urnie musi si\u0119 znale\u017a\u0107 przynajmniej jedna kula, tzn. nie mo\u017ce by\u0107 pustych urn. Wymusza to od razu za\u0142o\u017cenie, \u017ce \\(n\\geqslant k\\), gdzie podobnie jak poprzednio, \\(n\\) to liczba kul, a \\(k\\) to liczba urn. Skoro nie mo\u017ce by\u0107 pustych urn, to \u017cadne dwa s\u0142upki nie mog\u0105 si\u0119 znale\u017a\u0107 obok siebie. Do tego, nie mo\u017ce by\u0107 s\u0142upka na samym pocz\u0105tku ani na samym ko\u0144cu bo wtedy pierwsza lub ostatnia urna by\u0142aby pusta. Innymi s\u0142owy mamy \\(n-1\\) miejsc, w kt\u00f3re mo\u017cemy wetkn\u0105\u0107 s\u0142upki.
\n![\"na](\"https:\/\/www.beta-iks.pl\/wp-content\/uploads\/2024\/04\/kropki02.png\")
Od razu wida\u0107, \u017ce tym razem problem sprowadza si\u0119 do umieszczenia \\(k-1\\) s\u0142upk\u00f3w w \\(n-1\\) miejsc. Przy czym w jednym miejscu mo\u017ce si\u0119 znajdowa\u0107 co najwy\u017cej jeden s\u0142upek. Ka\u017cde takie rozmieszczenie s\u0142upk\u00f3w mo\u017cemy uto\u017csamia\u0107 po prostu z podzbiorem \\((n-1)\\)-elementowego zbioru. Reasumuj\u0105c, tym razem mamy \\[{n-1 \\choose k-1}\\] sposob\u00f3w.<\/p>\n
\nOd razu przychodzi do g\u0142owy og\u00f3lniejsze ograniczenie. Mo\u017cemy rozwa\u017cy\u0107 sytuacj\u0119, w kt\u00f3rej chcemy aby w \\(i\\)-tej urnie znalaz\u0142o si\u0119 co najmniej \\(a_i\\) kulek. Sprawia to, \u017ce musi zachodzi\u0107 \\[n\\geqslant a_1+a_2+\\cdots + a_k.\\] Bezpo\u015brednie zastosowanie naszej metody kropek i s\u0142upk\u00f3w jest raczej trudne. Mo\u017cemy jednak pos\u0142u\u017cy\u0107 si\u0119 prostym trikiem. Mianowicie, je\u017celi przyjmiemy \\[m=n-a_1-a_2-\\cdots-a_k,\\] to nasz problem jest r\u00f3wnowa\u017cny rozmieszczeniu \\(m\\) kul w \\(k\\) urnach. Czyli sposob\u00f3w rozmieszczenia kul przy za\u0142o\u017ceniu, \u017ce w \\(i\\)-tej urnie musi ich by\u0107 co najmniej \\(a_i\\) jest \\[{m+k-1 \\choose k-1}.\\]<\/p>\n
\nRozwa\u017cmy teraz inne zadanie, kt\u00f3re z pozoru wydaje si\u0119 zupe\u0142nie inne lecz, jak zobaczymy, jest zupe\u0142nie takie samo. Mianowicie, ile rozwi\u0105za\u0144 w\u015br\u00f3d nieujemnych liczb ca\u0142kowitych ma r\u00f3wnanie \\[x_1+x_2+\\cdots+x_k = n,\\] gdzie \\(n\\) jest r\u00f3wnie\u017c nieujemn\u0105 liczb\u0105 ca\u0142kowit\u0105? Mo\u017ce nie dla ka\u017cdego jest to takie oczywiste na pierwszy rzut oka, ale mo\u017cemy zauwa\u017cy\u0107, \u017ce ka\u017cde \\(x_i\\) mo\u017cemy uto\u017csamia\u0107 z urn\u0105, w kt\u00f3rej znajduje si\u0119 pewna ilo\u015b\u0107 kul (by\u0107 mo\u017ce nawet 0), a samych kul jest \u0142\u0105cznie \\(n\\). Odpowied\u017a jest wi\u0119c oczywista! Takich rozwi\u0105za\u0144 jest \\[{n+k-1\\choose k-1}.\\]<\/p>\n
\nTutaj te\u017c, jak w przypadku kul i urn, mo\u017cemy doda\u0107 ograniczenia, \u017ce \\(x_i\\geqslant a_i\\) dla pewnych \\(a_i\\in\\mathbb N\\). Tak postawiony problem, rozwi\u0105\u017cemy tak samo jak analogiczny z kulami i urnami. <\/p>\n","protected":false},"excerpt":{"rendered":"
Na ile sposob\u00f3w mo\u017cna umie\u015bci\u0107 10 nierozr\u00f3\u017cnialnych kul w 5 rozr\u00f3\u017cnialnych urnach? Okazuje si\u0119, \u017ce ten, i podobne problemy mo\u017cna rozwi\u0105za\u0107 u\u017cywaj\u0105c prostego triku.<\/p>\n","protected":false},"author":1,"featured_media":2456,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[56,57],"tags":[65],"yoast_head":"\n