393. Happy Passover

הנה טיפ באווירת פסח.

חידה: מה סכום המספרים בשיר “אחד מי יודע”? (כולל חזרות)

תשובה: ובכן, אם מנתחים את השיר, הוא נראה ככה:

אחד מי יודע? אחד - אני יודע! אחד אלוהינו
שניים מי יודע? שניים - אני יודע! שני לוחות הברית, אחד אלוהינו
שלושה מי יודע? שלושה - אני יודע! שלושה אבות, שני לוחות הברית, אחד אלוהינו
…

קיצר אנחנו רואים שבשורה ה$ n $ בשיר סכום המספרים הוא:

$ n + n + n + (n - 1) + (n - 2) + \dots + 1 $

שהסכום של זה שווה לפי הנוסחה לסדרה חשבונית של גאוס: $ \displaystyle{ 2n + \frac{n (n+1)}{2} } $.
עכשיו צריך לסכום את כל השורות מ1 עד $ n $: כלומר צריך לסכום את $ \displaystyle{ 2k + \frac{k (k+1)}{2} } $ מ$ k = 1 $ עד $ n $.

איך עושים את זה?

---

טוב, כאן מגיע החלק האומנותי של והיצירתי של הטיפ -
נעבור לבעיה אחרת שלכאורה לא קשורה:

בכמה דרכים אפשר לחלק $ n $ תפוזים ל$ k $ ילדים? (כלומר, לא משנה מי מקבל איזה תפוז, אלא משנה כמה תפוזים הוא מקבל)

נסמן מספר זה ב$ F(n,k)$, אז מתקיימת נוסחת הנסיגה:

$ F(n, k) = F(n, k - 1) + F(n - 1, k - 1) + F(n - 2, k - 1) + \dots + F(0, k - 1) $

אכן: נבחר את אחד הילדים: אם הוא קיבל $ 0 $ תפוזים, אנחנו צריכים לחלק $ n $ תפוזים ל $ k - 1$ ילדים, אם הוא קיבל תפוז אחד, אנחנו צריכים לחלק $ n -1 $ תפוזים ל$ k-1 $ ילדים וכו’. כל אפשרות כזאת מתאימה למחובר מתחילת הסכום ( $ F(n,k-1) $ מתאים לאפשרות שהילד שבחרנו קיבל 0 תפוזים, $ F(n-1,k-1) $ מתאים לאפשרות שהילד שבחרנו קיבל תפוז אחד וכו’)

מסתבר שאפשר לחשב את $ F(n,k)$ בצורה מפורשת:

ניקח את כל ה$ n $ תפוזים ונשים ביניהם $ k -1 $ מקלות של ארטיק. כעת בין כל שני מקלות נוצרת מחיצה, ובסה”כ נוצרות $ k $ מחיצות. הילד ה$ i $ יקבל את התפוזים שנמצאים במחיצה ה$ i $.

מספר הדרכים לשים $ k - 1 $ מקלות של ארטיק בין $ n $ תפוזים הוא $ F(n,k) = \binom{n + k - 1}{k-1}$ כאשר $ \binom{n}{k} $ הוא המקדם הבינומי.

נזכור שמתקיים

$ F(n, k) = F(n, k - 1) + F(n - 1, k - 1) + F(n - 2, k - 1) + \dots + F(0, k - 1) $

נבחר $ k =4 $, $ n = N - 1$ ונקבל

$ F(N-1, 4) = F(N - 1, 3) + F(N - 2, 3) + F(N - 3, 3) + \dots + F(0, 3) $

אבל $ F(N - 1, 3) = \binom{N-1+3-1}{3-1} = \binom{N + 1}{2} = \frac{N (N+1)}{2} $

הדבר הזה נותן בעצם סכום לסכום של סדרה חשבונית:

$$ 1 + (1+2) + (1+2+3) + \dots + (1+2+3+\dots+N) = \\ F(N-1,4) = \binom{N-1+4-1}{4-1} = \binom{N+2}{3} = \frac{(N+2)(N+1)N}{6} $$

לכן סכום השורות עד השורה ה$ N $ בשיר אחד מי יודע היא $ \frac{(N+2)(N+1)N}{6} + N(N+1) $

בשיר אחד מי יודע יש 13 שורות ולכן התשובה היא: $ \frac{15\cdot 14 \cdot 13}{6} + 13 \cdot 14 = 637$.

---

להלן קוד מאת אלירן מויאל שכותב את השיר אחד מי יודע (האחריות על שימוש בסדר על המשתמש בלבד…)

var whoKnows = new string[]
               {
                   "ehad elohinu",
                   "shti luhot a brit",
                   "shlosha avot",
                   "arbaa imaot",
                   "hamisha humshi tora",
                   "shisha sidri mishna",
                   "shiva yemi shbta",
                   "shmona yemi mila",
                   "tishaa yerhi lida",
                   "asara dibria",
                   "ahad asar kohvaia",
                   "shnim asar shivtaia",
                   "shlosh asar midaia"
               };

var numbersToHebrew = new Dictionary<int, string>
                      {
                          {1, "ehad" },
                          {2, "shnaim" },
                          {3, "shlosha" },
                          {4, "arbaa" },
                          {5, "hamisha" },
                          {6, "shisa" },
                          {7, "shiva" },
                          {8, "shmona" },
                          {9, "tishaa" },
                          {10, "asara" },
                          {11, "ahad asar" },
                          {12, "shnim asar" },
                          {13, "shlosh asar" }
                      };

const string ending = "elohinu , elohinu , elohinu , elohinu shbashamim ve baaretez ";

for (int i = 0; i < whoKnows.Length; i++)
{
    Console.WriteLine("{0} mi yodea? {0} ani yodea!", numbersToHebrew[i + 1]);

    for (int j = i; j >= 0; j--)
    {
        Console.WriteLine(whoKnows[j]);
    }

    Console.WriteLine(ending);
    Console.WriteLine();
}

חג שמח!