Zadania tekstowe, zadanie nr 170
ostatnie wiadomo艣ci | regulamin | latex
| Autor | Zadanie / Rozwi膮zanie |
enikon post贸w: 2 |  2014-08-31 17:20:33Kombinatoryka Witam mam problem z zadaniem. Maciek ma n kredek w p kolorach. Kredek z ka偶dego koloru jest ip. Pewnego dnia postanowi艂 zabra膰 do szko艂y dok艂adnie k z nich. Na ile sposob贸w jest w stanie wykona膰 to zadanie je艣li: a) n=6 p=3 i1=3 i2=2 i3=1 k=3? b) n=10 p=5 i1=1 i2=1 i3=2 i4=3 i5=3 k=4? Kredki o jednym kolorze s膮 nieodr贸偶nialne, Maciek mo偶e zabra膰 maksymalnie i1 kredek pierwszego koloru, i2 drugiego itd. Bardzo zale偶y mi na wzorze i szczeg贸艂owym rozwi膮zaniu. Niestety nie potrafi臋 znale藕膰 tego w internecie. Obstawiam 偶e trzeba wymy艣li膰 sprytny spos贸b na po艂膮czenie wzor贸w na permutacj臋 z powt贸rzeniami i kombinacj臋 bez powt贸rze艅 |
tumor post贸w: 8070 | 2014-08-31 18:27:28 Dla tak niewielkich liczb da si臋 w miar臋 szybko wypisa膰 rozwi膮zanie. Nie wiem, czy s膮 na to wzory proste, ale zawsze te偶 mo偶na machn膮膰 metod臋 rekurencyjn膮, kt贸ra b臋dzie wcale nie najgorsza do stosowania r臋cznego. Je艣li wybieramy $k$ kredek spo艣r贸d n kredek, gdy w kolejnych kolorach jest $i_1,i_2,...$ kredek, to oznaczmy to $S^n_k(i_1,i_2,...)$, liczby p pami臋ta膰 w zasadzie nie trzeba, jest ilo艣ci膮 argument贸w) Z pierwszego koloru bierzemy $x$ kredek, mo偶emy wzi膮膰 najwi臋cej $min(k,i_1)$ element贸w (bo bierzemy najwy偶ej tyle ile Maciek chce wzi膮膰 i najwy偶ej tyle, ile jest w danym kolorze), natomiast najmniej mo偶emy wzi膮膰 $max(0, k+i_1-n)$ (poniewa偶 nie mo偶emy wzi膮膰 oczywi艣cie mniej ni偶 $0$, natomiast pozosta艂ych kredek, czyli $n-i_1$, musi by膰 nie mniej ni偶 planowanych do wzi臋cia k-x, czyli $n-i_1\ge k-x$). Gdy we藕miemy x kredek, to trzeba b臋dzie wybiera膰 w sytuacji, gdy kolor贸w jest o 1 mniej, liczba kredek jest o i_1 mniejsza, liczba kredek do wzi臋cia jest o x mniejsza. Czyli $S_k^n(i_1,i_2,i_3,...,i_t)=\sum_{x=max(0,k+i_1-n)}^{min(k,i_1)}S_{k-x}^{n-i_1}(i_2,i_3,...,i_t)$ Dla przyk艂adu $S_3^6(3,2,1)= S_3^3(2,1)+S_2^3(2,1)+S_1^3(2,1)+S_0^3(2,1)$ Przy tym $S_z^z=1$, $S_0^z=1$, czyli mamy $S_3^6(3,2,1)= S_3^3(2,1)+S_2^3(2,1)+S_1^3(2,1)+S_0^3(2,1)= 1+S_2^3(2,1)+S_1^3(2,1)+1= 1+S_1^1(1)+S_0^1(1)+S_1^1(1)+S_0^1(1)+1=6$ Odpowiada to oczywi艣cie sytuacji, gdy mamy kredki w kolorach 111,22,3, mo偶emy wzi膮膰 111 112 113 122 123 223 (sze艣膰 mo偶liwo艣ci) Dodatkowo mamy $S_1^z(i_1,...,i_t)=t$, to te偶 upro艣ci liczenie mo偶liwo艣ci, no i je艣li zosta艂 1 kolor, to ju偶 mamy zawsze tylko jedn膮 mo偶liwo艣膰. Analogicznie liczymy dla $S_4^{10}(1,1,2,3,3)= S_4^9(1,2,3,3)+ S_3^9(1,2,3,3)=$ $S_4^8(2,3,3)+ S_3^8(2,3,3)+ S_3^8(2,3,3)+ S_2^8(2,3,3)=$ $S_4^6(3,3)+ S_3^6(3,3)+ S_2^6(3,3)+ ...$ Wi臋cej tu pisania ni偶 liczenia. Ponadto gdy zostan膮 dwa kolory, 艂atwo liczy膰 w pami臋ci ilo艣膰 mo偶liwo艣ci. Wiadomo艣膰 by艂a modyfikowana 2014-08-31 18:31:50 przez tumor |
enikon post贸w: 2 | 2014-08-31 20:29:03 Dzi臋ki tumor za b艂yskawiczn膮 odpowied藕.  Tak sobie patrz膮c na rekurencj臋 pomy艣la艂em 偶e jednak jaki艣 wz贸r m贸g艂by istnie膰 (sporo ze wzor贸w rekurencyjnych da si臋 zapisa膰 wzorem prostym). Oczywi艣cie po modyfikacji ilo艣ci kredek jak napisano post wy偶ej 偶eby ka偶de ip wynosi艂o min(k,ip). Oczywi艣cie znalezienie wzoru by艂oby 艣wietnym wyzwaniem. My艣la艂em o czym艣 o wygl膮dzie mniej wi臋cej w tym stylu ( to NIE jest 偶aden wz贸r ):$ \frac{n!}{\frac{k\cdot(n-i1)}{k-i1}+\frac{k\cdot(n-i2)}{k-i1}+\cdots}$ |
| strony: 1 | |
Prawo do pisania przys艂uguje tylko zalogowanym u偶ytkownikom. Zaloguj si臋 lub zarejestruj