חזור לתיקייה: שיעורי בית

גליון 2

חיפוש בתיקיה
Ctrl K
לחץ כאן או הקש Ctrl K כדי לחפש בכל התיקיה
  • תרגיל 1
  • תרגיל 2
  • תרגיל 3
  • תרגיל 5

גליון 2

02340141

קומבינטוריקה למדעי המחשב

רשימות הרצאה לקריאה בשבת

גליון 2

הופק מתוך תקיית התואר של שקד

uni-folder.vercel.app

תרגיל 1

תרגיל (1 [א])

הוכיחו כי בכל בחירה של שמונה מספרים מתוך קבוצת המספרים {1,2,3,…,15}\left\{ 1,2,3,\dots,15 \right\}{1,2,3,…,15} יש לפחות 333 זוגות של מספרים בעלי הפרש זהה.
דוגמה: עבור הבחירה של 1,2,3,4,5,6,7,81,2,3,4,5,6,7,81,2,3,4,5,6,7,8 הזוגות {1,2},{3,4},{5,6}\left\{ 1,2 \right\},\left\{ 3,4 \right\},\left\{ 5,6 \right\}{1,2},{3,4},{5,6} מקיימים את הנדרש.
הזוגות אינם חייבים להיות זרים.

הוכחה:
יהיו {a,b},{c,d}\left\{ a,b \right\},\left\{ c,d \right\}{a,b},{c,d} זוגות מספרים בעלי סכום זהה. אזי מתקיים:

a+b=c+d  ⟹  a−c=d−ba+b=c+d \implies a-c=d-ba+b=c+d⟹a−c=d−b

לכן, במידה ונבצע החלפת איברים ההפרש שלהם יהיה זהה. לכן, מספר הזוגות בעלי אותו ההפרש זהה למספר הזוגות בעלי אותו הסכום.
הסכום המקסימלי האפשרי בקבוצה הוא 15+1=1615+1=1615+1=16 והסכום המינימלי האפשרי בקבוצה הוא 1+2=31+2=31+2=3.
לכן, יש בדיוק 16−2=1416-2=1416−2=14 סכומים אפשריים (ובכך 141414 הפרשים אפשריים)
נבחר שמונה מספרים ונחלק זוגות שלהם לתאים עבורם הסכומים זהים, כלומר נניח הסכום של זוג מספרים הוא xxx אז הם ילכו לתא הממוספר xxx.
אנו בוחרים 888 מספרים. נסדר אותם בשורה ואז, למספר הראשון יש 888 אפשרויות לסכימה(כי אפשר חזרות), לשני יש 777 אפשרויות(כי האפשרות של המספר הראשון + המספר השני כבר נבחרה ב-8 אפשרויות של הקודם), לשלישי יש 666 וכך הלאה. סה"כ, לאיבר כללי xxx שנמצא במקום ה-iii בסידור שלנו, יש 8−i+18-i+18−i+1 אפשרויות לחלוקה.
לכן, מספר האפשרויות לסכומים של 888 מספרים הינו ∑i=18(8−i+1)=8+7+6+5+4+3+2+1=36\displaystyle \sum_{i=1}^8 (8-i+1)=8+7+6+5+4+3+2+1=36i=1∑8​(8−i+1)=8+7+6+5+4+3+2+1=36.
לפי עקרון שובך היונים המוכלל, כאשר יש לנו 141414 תאים ו-363636 יונים, אזי בהכרח קיים תא עם ⌈3614⌉=⌈2+814⌉=3\left\lceil \frac{36}{14} \right\rceil=\left\lceil 2+\frac{8}{14} \right\rceil=3⌈1436​⌉=⌈2+148​⌉=3 יונים.
לכן, בהכרח קיימים 333 זוגות של מספרים בעלי אותו סכום ולכן, 333 זוגות של מספרים בעלי אותו ההפרש.
∎

תרגיל (1 [ב])

הוכיחו/הפריכו: בכל בחירה של שמונה מספרים מתוך קבוצת המספרים {1,2,3,…,15}\left\{ 1,2,3,\dots,15 \right\}{1,2,3,…,15} יש לפחות 333 זוגות של מספרים בעלי הפרש 111 או הפרש 222 (כלומר, 333 עם הפרש 111 או 333 עם הפרש 222)

הטענה נכונה.
הוכחה:
נבחר 888 מספרים מתוך הספרות {1,…,15}\left\{ 1,\dots,15 \right\}{1,…,15} ונסדר אותם בסדר עולה:

x1<x2<x3<x4<x5<x6<x7<x8x_{1}<x_{2}<x_{3}<x_{4}<x_{5}<x_{6}<x_{7}<x_{8}x1​<x2​<x3​<x4​<x5​<x6​<x7​<x8​

ההפרש המקסימלי של שני מספרים בקבוצה הינו 141414 כפי שראינו בסעיף קודם.
נסתכל על ההפרש בין כל שני מספרים עוקבים, שכן אלו יהיו ההפרשים הכי קטנים. נגדיר Δxi=xi+1−xi\Delta x_{i}=x_{i+1}-x_{i}Δxi​=xi+1​−xi​.
נמצא את סכום כל ההפרשים הללו:

∑i=17Δxi=x8−x7+x7−x6+⋯+x2−x1=x8−x1≤↓מהנ"ל14\sum_{i=1}^7 \Delta x_{i}=x_{8}-x_{7}+x_{7}-x_{6}+\dots+x_{2}-x_{1}=x_{8}-x_{1} \underset{\begin{matrix} \downarrow \\ \R{\text{מהנ"ל}} \end{matrix}}{\leq} 14i=1∑7​Δxi​=x8​−x7​+x7​−x6​+⋯+x2​−x1​=x8​−x1​↓מהנ"ל​≤​14

נניח בשלילה כי לא קיימים 333 הפרשים או של 111 או של 222. לכן קיימים במקסימום 222 הפרשים של 111 ו-222 הפרשים של 222. נסכום את ההפרשים הללו 2+2+1+1=62+2+1+1=62+2+1+1=6.
כעת, נבחר את שאר ההפרשים. המינימום שהם יכולים להיות זה 333 ולכן נניח כי הם כולם 333. יש לנו בדיוק 7−4=37-4=37−4=3 הפרשים לבחור ולכן נקבל את סכום ההפרשים 3⋅3=93\cdot 3=93⋅3=9.
נסכום ונקבל:

∑i=17Δxi≤9+6=15≤14\sum_{i=1}^7 \Delta x_{i}\leq 9+6=15 \leq 14i=1∑7​Δxi​≤9+6=15≤14

זוהי סתירה לכך ש-15>1415>1415>14 ולכן, בהכרח יש לפחות 333 זוגות מספרים בעלי הפרש של 1 או 3 זוגות מספרים בעלי הפרש של 2.
∎

תרגיל 2

תרגיל (2 [א])

הוכיחו: בכל סידור של 101101101 מספרים טבעיים גדולים ממש מ-000 במעגל שסכומם 300300300 ניתן למצוא רצף של מספרים במעגל שסכומם 200200200.

הערה (רעיון ההוכחה)

כנראה גם שובך היונים.
נגדיר 0<xi∈N0< x_{i} \in \mathbb{N}0<xi​∈N לכל 0≤i≤1000\leq i\leq 1000≤i≤100. אזי מתקיים:

x0+x1+⋯+x100=300x_{0}+x_{1}+\dots+x_{100}=300x0​+x1​+⋯+x100​=300

זה נשמע כמו C300100\mathbb{C}_{300}^{100}C300100​ - זה מספר האפשרויות ליצור יצור שכזה עם מספרים גדולים או שווים ל-000. אז אם נגדיר: yi=xi−1y_{i}=x_{i}-1yi​=xi​−1 אזי מתקיים:

y0+y1+⋯+y100=300−101=199y_{0}+y_{1}+\dots+y_{100}=300 -101=199y0​+y1​+⋯+y100​=300−101=199

אז זה בעצם C199100\mathbb{C}_{199}^{100}C199100​. זהו מספר האפשרויות ל-101101101 מספרים מסודרים במעגל(הסדר בינהם חשוב)

כעת נבנה סכומים, הסכום המקסימלי של רצף במעגל הוא 300300300 שכן זה סכום המעגל כולו, והסכום המינימלי הוא xix_{i}xi​ הקטן ביותר. אז כנראה זה לא זה כי זה גם לא עוזר אם נמצא שבטוח קיים תא כלשהו - אנחנו צריכים תא ספציפי.

הוכחה:

∎

תרגיל (2 [ב])

יהי n≥2n\geq 2n≥2. הוכיחו/הפריכו כי לכל בחירה של nnn ממספרים טבעיים שונים מאפס קיימים שני מספרים שהפרש הריבועים שלהם מתחלק ב-n−1n-1n−1.
דוגמה: עבור n=3n=3n=3 עם הבחירה של 17,300,4517,300,4517,300,45 מתקיים כי 452−17245^2-17^2452−172 מתחלק ב-222.

הערה (רעיון לפתרון)

שטויות.

הטענה ????.

תרגיל (2 [ג])

נתונים עשרה ילדים העומדים במעגל ונתונות 494949 סוכריות המחולקות לילדים.
הוכיחו כי בכל חלוקה של סוכריות כך שכל ילד מקבל לכל היותר 888 סוכריות קיים רצף של 333 ילדים שיש להם לפחות סוכריה אחת.

הערה (רעיון ההוכחה)

494949 סוכריות לחלק ל-101010 ילדים זה בממוצע 4.94.94.9 סוכריות לילד.
אם אנחנו מחלקים כך שלכל ילד יש לכל היותר 888 סוכריות אז נוכל לקחת את החלוקה הכי מוגזמת שכן ככל שלכל ילד יש יותר סוכריות כך לפחות ילדים יש סוכריות.
אז נקבל 6 ילדים עם שמונה סוכריות ועוד ילד אחד עם סוכריה אחת.
אנחנו לא יכולים לסדר 777 ילדים במעגל של 101010 בלי שיהיה רצף של 333 ילדים. (נניח שהילדים בלי סוכריה לא נכנסים למעגל ובמקומם יש כיסאות ריקים)
נניח בשלילה כי אין רצף של 3 ילדים, אזי הרצף המקסימלי הוא 222. נחלק את הילדים לזוגות, יש 333 זוגות ועוד אחד בודד. בנוסף, גם את הכיסאות נחלק ל-222 ואז יש 555 מקומות.
נכניס זוג למקום הראשון, ואז עוד זוג למקום השלישי ועוד אחד למקום החמישי.
כעת נפריד בחזרה למעגל ונקבל 101010 כיסאות עם ילדים בזוגות וילד אחד שנותר להכניס.
נראה כי בכל מקום שאנו מכניסים אותו הוא יוצר רצף של 333 או יותר.
זה רק מקרה פרטי אבל. צריך להוכיח למקרה הכללי כנראה גם עם שובך היונים.

הוכחה:

∎

תרגיל 3

תרגיל (3 [א])

בכל קבוצת חברים נגדיר את היחס "חבר/ה של". היחס סימטרי, אם יוסי חבר של דנה אז דנה חברה של יוסי.
הוכיחו כי בכל קבוצת חברים בגודל n≥2n\geq 2n≥2 קיימים לפחות שני אנשים עם אותה כמות חברים.

הוכחה:
לכל אדם בקבוצה של nnn אנשים יכולים להיות מ-000 עד n−1n-1n−1 חברים. זה בדיוק nnn אפשרויות.
נניח בשלילה כי אין שני אנשים עם אותו מספר חברים. אזי קיים אדם עם 000 חברים ואדם עם n−1n-1n−1 חברים, שכן יש בדיוק nnn אפשרויות למספר חברים ולכן כל אדם מ-nnn האנשים מקבל אפשרות אחת. זה עומד בסתירה לכך שהיחס "חבר של" סימטרי. כלומר, לא יכול להיות שיהיה אדם עם 000 חברים אם קיים אדם בעל n−1n-1n−1 חברים שכן האדם בעל n−1n-1n−1 חברים חבר של האדם בעל 000 חברים מכיוון שיש רק n−1n-1n−1 אנשים שהאדם בעל n−1n-1n−1 חברים יכול להיות חבר שלהם ואז לפי סימטריות היחס, האדם בעל 000 חברים חבר של האדם בעל n−1n-1n−1 חברים. כלומר, אין לו 000 חברים אלא 111.
לכן, קיימים לפחות שני אנשים עם אותו מספר חברים.
∎

תרגיל (3 [ב])

נתון שבקבוצת חברים יש בדיוק שני אנשים עם אותו מספר חברים. מהו מספר זה אם ידוע שאין בקבוצה מישהו בלי חברים?

פתרון:
נוכיח באינדוקציה כי עבור קבוצה של nnn חברים בה יש בדיוק שני אנשים עם אותו מספר חברים, מספר זה הוא ⌊n2⌋\left\lfloor \frac{n}{2} \right\rfloor⌊2n​⌋.
בסיס:

  • עבור n=2n=2n=2 מתקיים כי יש שני אנשים, שמכיוון שאף אחד לא בודד, לשניהם יש חבר אחד שהוא האדם השני. לכן יש ⌊22⌋=1\left\lfloor \frac{2}{2} \right\rfloor=1⌊22​⌋=1 חברים לשני אנשים בדיוק.
  • עבור n=3n=3n=3 כמות החברים שיכולה להיות לכל אדם היא 111 או 222. מכיוון שיש רק זוג אחד בעל אותו מספר חברים, בהכרח יש אדם אחד בעל חבר אחד ואדם אחר בעל שני חברים. האדם בעל השני חברים חבר לאדם בעל החבר אחד וחבר של האדם השלישי. האדם בעל החבר האחד חבר רק של האדם בעל שני החברים ולכן האדם השלישי הינו בעל חבר אחד בדיוק. לכן, זוג האנשים שיש להם את אותו מספר חברים הינו בעל חבר אחד בהתאם לנוסחה: ⌊32⌋=1\left\lfloor \frac{3}{2} \right\rfloor=1⌊23​⌋=1.
    צעד: נניח כי עבור nnn אנשים אשר לאף אחד אין 000 חברים יש בדיוק שני אנשים עם ⌊n2⌋\left\lfloor \frac{n}{2} \right\rfloor⌊2n​⌋ חברים ונוכיח כי זה מתקיים עבור n+2n+2n+2 ובכך עבור כל n≥4n\geq 4n≥4 (שכן הבסיס שלנו מתייחס גם למספרים האי-זוגיים)
    עבור קבוצה של n+2n+2n+2 חברים אשר אף אחד בה לא בלי חברים, יש את האפשרויות ל-{1,2,…,n+1}\left\{ 1,2,\dots,n+1 \right\}{1,2,…,n+1} חברים. מכיוון שיש רק זוג אחד של אנשים בעל אותו מספר חברים, בהכרח כל מספר בקבוצה הזו מקבל אדם אשר לו כמות החברים שמייצג המספר. בנוסף, קיים אדם בעל kkk חברים כאשר k∈{1,2,…,n+1}k \in \left\{ 1,2,\dots,n+1 \right\}k∈{1,2,…,n+1} והוא הזוג שלנו.
    נסמן ב-AAA את האדם בעל n+1n+1n+1 חברים. הוא חבר של כולם ולכן מבטיח כי קיים אדם BBB בעל חבר אחד בלבד.
    נוציא את שניהם מהקבוצה ובכך נוריד לכל אדם חבר אחד, שכן מספר החברים שיש לכל אדם כולל את החברות של אותו אדם עם AAA ולא כולל את החברות של אותו אדם עם BBB שכן BBB חבר אך ורק של AAA והיחס סימטרי.
    קיבלנו כעת קבוצה של nnn אנשים שבה האפשרויות לחברים הינם: {2,3,…,n−1}\left\{ 2,3,\dots,n-1 \right\}{2,3,…,n−1} בנוסף עדיין קיים אדם בעל k−1∈{2,3,…,n−1}k-1 \in \left\{ 2,3,\dots,n-1 \right\}k−1∈{2,3,…,n−1} חברים אשר אינו תלוי בקבוצה הזאת(k−1k-1k−1 במקום kkk שכן חבר אחד שלו - AAA - עזב את הקבוצה). לפי הנחת האינדוקציה מתקיים כי:
k−1=⌊n−12⌋=⌊n2−12⌋=⌊n2⌋  ⟹  k=⌊n2⌋+1=⌊n2+1⌋=⌊n+22⌋k-1=\left\lfloor \frac{n-1}{2} \right\rfloor =\left\lfloor \frac{n}{2}-\frac{1}{2} \right\rfloor =\left\lfloor \frac{n}{2} \right\rfloor \implies k=\left\lfloor \frac{n}{2} \right\rfloor +1=\left\lfloor \frac{n}{2}+1 \right\rfloor =\left\lfloor \frac{n+2}{2} \right\rfloor k−1=⌊2n−1​⌋=⌊2n​−21​⌋=⌊2n​⌋⟹k=⌊2n​⌋+1=⌊2n​+1⌋=⌊2n+2​⌋

כנדרש.

לכן, לכל קבוצה של nnn חברים המתאימה לתנאי השאלה, קיים זוג של אנשים בו לכל אחד מהם יש ⌊n2⌋\left\lfloor \frac{n}{2} \right\rfloor⌊2n​⌋ חברים.

תרגיל (3 [ג])

הוכיחו/הפריכו: קיימת קבוצת חברים בגודל n≥2n\geq 2n≥2 זוגי בה לכל האנשים יש מספר זוגי של חברים.

הטענה נכונה.
נביט בקבוצת חברים בגודל n=4n=4n=4.

  • אדם 111 חבר של 222 אנשים(אדם 2 ואדם 3)
  • אדם 2 חבר של 2 אנשים(אדם1 ואדם 4)
  • אדם 3 חבר של 2 אנשים(אדם1 ואדם 4)
  • אדם 4 חבר של 2 אנשים(אדם 2 ואדם 3)

לכל אחד מהאנשים בקבוצה הזו יש 222 חברים ו-222 הוא מספר זוגי.

תרגיל (3 [ד])

הוכיחו/הפריכו: קיימת קבוצת חברים בגודל n≥3n\geq 3n≥3 אי-זוגי בה לכל האנשים יש מספר אי-זוגי של חברים.

הטענה אינה נכונה
הוכחה:
תהי AAA קבוצת חברים בגודל n≥3n\geq 3n≥3 אי-זוגי. נניח בשלילה שלכל אדם יש מספר אי זוגי של חברים.
מכיוון שיש מספר אי זוגי של אנשים ולכולם מספר אי זוגי של חברים, כמות החברים של כל האנשים בקבוצה יחד(סופרים לכל אדם את כמות חבריו ומחברים ביחד) תהיה אי זוגית. נסמנה SSS.
כאשר אנו בונים קבוצה AAA, לאור היותו של היחס סימטרי, SSS בהכרח זוגי.
זוהי סתירה לכך ש-SSS אי זוגי ולכן בהכרח קיים אדם בעל מספר זוגי של אנשים.
∎

תרגיל 5

תרגיל (5 [א])

הוכיחו קומבינטורית וללא פישוטים אלגבריים כי:

∑i=2nk(k−1)kn−i=kn−k\sum_{i=2}^n k(k-1)k^{n-i}=k^n-ki=2∑n​k(k−1)kn−i=kn−k

הוכחה:
בעיה: מספר הוקטורים ה-kkk-ים באורך nnn שבהם לא כל האיברים זהים.
צד ימין: נגדיר את AAA כקבוצת כל הוקטורים ה-kkk-ים באורך nnn. לכל איבר בוקטור יש kkk מספרים שהוא יכול להיות ולכן יש (k1)=k\begin{pmatrix}k\\1\end{pmatrix}=k(k1​)=k אפשרויות לבחירתו. לפי עקרון הכפל, יש knk^nkn איברים בקבוצה AAA. נגדיר את BBB כקבוצת כל הוקטורים ה-kkk-ים באורך nnn שבהם כל האיברים זהים. נבחר את כל האיברים בבחירה אחת, לשם כך יש לנו kkk ספרות ובכך (k1)=k\begin{pmatrix}k\\ 1\end{pmatrix}=k(k1​)=k אפשרויות. לכן, גודל הקבוצה BBB הוא בדיוק kkk. לכן, לפי עקרון ההפרש, מספר הוקטורים ה-kkk-ים באורך nnn שבהם לא כל האיברים זהים הינו kn−kk^n-kkn−k.
צד שמאל: נחלק למקרים זרים על בסיס האיבר הראשון במילה ששונה מהאיבר הפותח. נסמנו iii. מכיוון שהאיבר הראשון קובע ממה האיבר iii צריך להיות שונה, המקרים הזרים שלנו יתחילו מ-i=2i=2i=2 ויסתיימו ב-i=ni=ni=n.
לכל iii נסתכל על שלוש בחירות שנדרש לעשות: נתחיל לבחור את האיברים הזהים במילה ובכך כל האיברים המגיעים לפני iii. לבחירה כזו נוכל לבחור את כל אחת מהספרות, כלומר, יש לנו (k1)=k\begin{pmatrix}k\\ 1\end{pmatrix}=k(k1​)=k אפשרויות לבחירה זו. כעת, נבחר את האיבר ה-iii שכפי שנאמר, הוא הראשון ששונה מהאיבר הפותח ולכן יש לנו k−1k-1k−1 ספרות בהן נוכל להשתמש ובכך (k−11)=k−1\begin{pmatrix}k-1\\1\end{pmatrix}=k-1(k−11​)=k−1 אפשרויות לבחירתו. לבסוף, נבחר את כל שאר האיברים במילה, אלו שמגיעים לאחר iii. הם האיברים i+1i+1i+1 עד nnn ולכן יש n−in-in−i בחירות שנדרש לעשות. כל בחירה היא מתוך kkk ספרות, שכן אין לנו תנאי על איברים אלו ולכן, יש kn−ik^{n-i}kn−i אפשרויות לבחירתם.
לפי עקרון הכפל, לכל iii יש k(k−1)kn−ik(k-1)k^{n-i}k(k−1)kn−i וקטורים שנוכל להרכיב.
לכן, לפי עקרון החיבור, יש ∑i=2nk(k−1)kn−i\displaystyle \sum_{i=2}^n k(k-1)k^{n-i}i=2∑n​k(k−1)kn−i וקטורים kkk-ים באורך nnn שבהם לא כל האיברים זהים.

מכיוון שהפתרונות הינם פתרונות לאותה הבעיה הם שקולים ולכן:

∑i=2nk(k−1)kn−i=kn−k\sum_{i=2}^n k(k-1)k^{n-i}=k^n-ki=2∑n​k(k−1)kn−i=kn−k

∎

תרגיל (5 [ב])

הוכיחו קומבינטורית וללא פישוטים אלגבריים כי:

(n3)=∑i=2n−1(n−i)(i−1)\begin{pmatrix} n \\ 3 \end{pmatrix}=\sum_{i=2}^{n-1}(n-i)(i-1)(n3​)=i=2∑n−1​(n−i)(i−1)

הוכחה:
בעיה: מספר הוקטורים הבינאריים עם בדיוק שלושה 111-ים.
צד ימין: נבחר תחילה את מיקום האחד האמצעי. לא נוכל לבחור את האיבר הראשון למיקום ה-1 האמצעי ולא נוכל לבחור את המיקום האחרון עבור ה-1 האמצעי שכן אנו רוצים להכניס עוד 1 אחד מימינו ומשמאלו. לכן, נוכל לבחור כל 2≤i≤n−12\leq i\leq n-12≤i≤n−1. נחלק כעת את הבעיה למקרים זרים לפי המיקום שבחרנו אשר נסמנו iii. נבצע שתי בחירות: בחירה על המיקום של ה-111 השמאלי, שמיקומו יכול להיות מ-1 ועד i−1i-1i−1 מה שיהיה בדיוק i−1i-1i−1 מקומות אפשריים ולכן (i−11)=i−1\begin{pmatrix}i-1\\ 1\end{pmatrix}=i-1(i−11​)=i−1 אפשרויות ובחירה על המיקום של ה-111 הימני, שמיקומו יכול להיות מ-i+1i+1i+1 עד nnn מה שיהיה בדיוק n−in-in−i מקומות אפשריים ולכן יש (n−i1)=n−i\begin{pmatrix}n-i\\ 1\end{pmatrix}=n-i(n−i1​)=n−i אפשרויות לבחירת מקומו. לכן, מספר האפשרויות הינו לפי עקרון הכפל, לזה יש (n−i)(i−1)(n-i)(i-1)(n−i)(i−1) אפשרויות. לכן, לפי עקרון החיבור, יש סה"כ ∑i=2n−1(n−i)(i−1)\displaystyle \sum_{i=2}^{n-1}(n-i)(i-1)i=2∑n−1​(n−i)(i−1) וקטורים בינאריים עם בדיוק שלושה 111-ים.
צד שמאל: נבצע בחירה של 333 מקומות ללא חשיבות לסדר הבחירה ובלי חזרות מתוך nnn המקומות בוקטור הבינארי. זה בדיוק (n3)\begin{pmatrix}n \\ 3\end{pmatrix}(n3​).

מכיוון שהפתרונות הינם פתרונות לאותה הבעיה הם שקולים ולכן:

(n3)=∑i=2n−1(n−i)(i−1)\begin{pmatrix} n \\ 3 \end{pmatrix}=\sum_{i=2}^{n-1}(n-i)(i-1)(n3​)=i=2∑n−1​(n−i)(i−1)

∎