منتديات الرياضيات العربية - عرض مشاركة واحدة

26-02-2009, 08:54 AM

سؤال جميل ، ولدي محاولة بمعلوماتي البسيطة :

لنعتبر $B$ من Bull تعبر عن الثيران ، و $C$ من Cow يعبر عن البقر

الآن لاحظ أن لدينا المجموعة

$S = \lbrace \infty \cdot B, \; \infty \cdot C \rbrace$

الآن لو كان لدينا $i$ من الـ $B$ ، ولنسمهم $B_1,B_2,...,B_i$

لاحظ أنه يمكننا ترتيب هذه الثيران بالصورة :

...B_1...B_2.......B_i...

حيث كل من الفراغات تملأ بالـ $C$ ، وليكن عدد الـ $C's$ في الفراغ بين $B_{j-1}$ و $B_j$ عبارة عن العدد الصحيح غير السالب $x_j$

لاحظ أن عدد طرق ترتيب هذه الـ $B's$ بحيث بين كل $B$ والآخر على الأقل $k$ من الـ $C$ يمكن استنتاجه بعد عدد حلول المعادلة :

$x_1 + x_2 + ... + x_{i+1} = n-i$

بحيث

$x_1 \ge 0 , \; \; x_2,x_3,...,x_i \ge k , \; \; x_{i+1} \ge 0$

الآن لنعرف الأعداد الصحيحة غير السالبة $y's$ كالتالي

$y_1 = x_1 , \; \; y_r = x_r - k \; \; \forall \; 2 \le r \le i ,\; \;y_{i+1} = x_{i+1}$

الآن يصبح هدفنا إيجاد عدد حلول المعادلة

$y_1 + y_2 + ... + y_{i+1} = (n-i) - (i-1)\cdot k = n - i - k \cdot i + k$

بحيث

$y_1 , y_2 , ... , y_{i+1} \ge 0$

ونعرف بسهولة أن عدد حلول هذه المعادلة يعطى بالعلاقة :

$\begin{pmatrix} n - k\cdot i + k \\ i \end{pmatrix}$

الآن ، هذا الحل عندما يكون عدد الـ $B's$ معلوم ، وهو $i$

ولكن لاحظ أن عدد الـ $B's$ في $n$ مكان سوف يكون محدودًا بين

$0$ و $\lfloor \frac{n}{k+1} \rfloor + 1$

ولإيجاد جميع الحلول لجميع أعداد $B$ الممكنة ، فقط نجمع المقدار

$\begin{pmatrix} n - k\cdot i + k \\ i \end{pmatrix}$

لقيم $i$ من $0$ إلى $\lfloor \frac{n}{k+1} \rfloor + 1$

وهو يعطى بالشكل :

$\sum_{i=o}^{\lfloor \frac{n}{k+1} \rfloor + 1} \; \; \begin{pmatrix} n - k\cdot i + k \\ i \end{pmatrix}$
وانتهينا

لتطبيق المثال المعروض ، خذ $k=2$ و $n=4$ وبالتالي عدد الطرق المختلفة هو :

$\sum_{i=o}^{ 2} \begin{pmatrix} 6 - 2\cdot i\\ i \end{pmatrix}= \begin{pmatrix} 6 \\ 0 \end{pmatrix} + \begin{pmatrix} 4 \\ 1 \end{pmatrix} + \begin{pmatrix} 2 \\ 2 \end{pmatrix} = 1 +4+ 1 = 6$

تحياتي ،،، وائل الغامدي