שאלות ופתרונות שלב ב' 2022
שאלה ראשונה - אבטיחים מרובעים
קנזי אוהב אבטיחים מרובעים.
אבטיחים מרובעים הם בצורת קובייה (הגובה, האורך והרוחב שלהם זהים זה לזה).
קנזי קנה n אבטיחים כאלו שהאורכים שלהם נתונים במערך A (כאשר A[i] הוא האורך של האבטיח ה-i).
כל האורכים של האבטיחים הם מספרים שלמים בין 1 ל-m, ונתון ש-m קטן מ-n.
אבטיחים מרובעים נקטפים תמיד בעודם בוסר, ולא מתאימים לאכילה. הם נמכרים בעיקר לנוי.
לכן קנזי אוהב לסדר את האבטיחים שלו לראווה במגדלים. על אבטיח i הוא יכול לשים ישירות את אבטיח j אם ורק אם אבטיח j קטן ממש מאבטיח i (כלומר מתקיים A[j] < A[i]).
קנזי לא יכול לשים יותר מאבטיח אחד ישירות על אותו האבטיח, אבל הוא יכול לשים במגדל מספר אבטיחים זה על גבי זה, כשעל כל אבטיח יש ישירות לכל היותר אבטיח אחד אחר, הגדלים שלהם מתאימים (למשל הוא יכול לשים את j ישירות על i ואת k ישירות על j אם אבטיח j קטן מאבטיח i וגם אבטיח k קטן מאבטיח j, וכך לבנות מגדל של שלושה אבטיחים).
קנזי רוצה לבנות כמה שפחות מגדלים שיכילו את כל האבטיחים (כלומר כל אבטיח חייב להיות משויך למגדל אחד בדיוק (גם מגדל של אבטיח אחד הוא חוקי), ובנוסף מספר המגדלים הכולל יהיה קטן ככל האפשר).
לדוגמה, אם היו לו 5 אבטיחים באורכים 3, 1, 2, 3, 2, הוא היה צריך לבנות 2 מגדלים (למשל אחד של 1 על 2 על 3, ואחד של 2 על 3).
-
עזרו לקנזי וכתבו עבורו אלגוריתם, שמקבל את n (מספר האבטיחים), את m (האורך המקסימלי האפשרי של אבטיח) ואת A (מערך אורכי האבטיחים), ומדפיס את מספר המגדלים הקטן ביותר שקנזי יכול לבנות כך שהם יכילו את כל האבטיחים.
-
עזרו לקנזי וכתבו עבורו אלגוריתם, שמקבל את n, את m ואת A, ומדפיס את המגדלים עצמם, כשמספר השורות הוא כמספר המגדלים, וכל שורה מתארת את אחד המגדלים - כרשימת אורכי האבטיחים במגדל זה (מהאבטיח התחתון עד לאבטיח העליון במגדל, לפי הסדר).
הצג פתרון
תובנות:
1. אם כל משקלי האבטיחים המרובעים שונים זה מזה, ניתן לשים את כולם במגדל אחד (נמיין את האבטיחים מהגדול לקטן ונשים אחד על השני לפי הסדר).
2. כל אבטיח חייב להיות קטן ממש מכל האבטיחים שמתחתיו במגדל (ולא רק מזה שמתחתיו ישירות), כי אם a < b וגם b < c בהכרח a < c, ולכן בפרט לא יתכן ש-2 אבטיחים באותו הגודל נמצאים באותו המגדל (כי נקבל סתירה לכך שהעליון מבניהם מוכרח להיות קטן ממש מהתחתון מבניהם).
3. נניח שאבטיח באורך x מופיע y פעמים. לא ניתן לשים את כל האבטיחים בפחות מ-y מגדלים, כי אז באחד מהם יהיה חייב להיות יותר מאבטיח אחד באורך x (עקרון שובח היונים), בסתירה לתובנה #2.
מהתובנות ניתן להסיק שאם נספור לכל אחד מאורכי האבטיחים כמה פעמים הוא נמצא אצל קנזי, וניקח את המספר הגבוה ביותר (מספר האבטיחים הרב ביותר מאותו האורך שיש לקנזי), זה יהיה מספר המגדלים הקטן ביותר שקנזי יכול לשים את כל האבטיחים שלו בהם.
מתובנה #3 אי אפשר בפחות מגדלים, ומתובנה #1 אפשר לתכנן אלגוריתם שבונה את מספר המגדלים הזה: ניקח אבטיח אחד מכל אורך שיש לקנזי, נמיין ונבנה את המגדל הראשון. נחזור על הפעולה על כל האבטיחים שנשארו, וכו', עד שיגמרו האבטיחים 😊
אלגוריתם לסעיף א':
סיבוכיות האלגוריתם היא O(n) (כמובן O(n + m), אבל נתון ש-m < n).
אלגוריתם לסעיף ב':
סיבוכיות האלגוריתם גם כאן היא O(n)
שאלה שניה - בננות
סבתא סמית מנהלת חנות למשלוחי בננות.
יש לה n בננות במשקלים שנתונים במערך B (המערך לא בהכרח ממוין), כאשר B[i] הוא המשקל של הבננה ה-i.
לסבתא סמית יש היום הזמנה ל-m משלוחי בננות (ומובטח ש-).
בכל משלוח היא חייבת לשים לפחות בננה אחת, והיא רוצה שבסוף היום לא יישארו לה בננות כלל (הן בתוקף קצר...), כלומר היא חייבת לכל בננה לבחור את המשלוח שהיא שמה אותה בו, כך שיהיו לה בדיוק m משלוחים שכולם מכילים בננה אחת לפחות. שימו לב שהמשלוחים לא חייבים להוות טווחים רציפים במערך.
היא רוצה שהמשלוחים יהיו כמה שיותר אחידים מבחינת טווח משקלי הבננות בתוך המשלוחים.
ליתר דיוק, היא קבעה לעצמה את "ערך השונות" של אוסף המשלוחים, שהוא הסכום של ההפרש בין הבננה הכבדה ביותר לבננה הקלה ביותר בכל משלוח, עבור כל m המשלוחים, והיא רוצה ש"ערך השונות" של אוסף המשלוחים שהיא תוציא היום יהיה קטן ככל האפשר.
למשל, אם יש לה 3 משלוחים, שבראשון משקלי הבננות הם 10, 5 ו-20, בשני בננה אחת במשקל 15, ובשלישי משקלי הבננות הם 1 ו-100, "ערך השונות" יהיה 15 (ההפרש בין 20 ל-5 במשלוח הראשון), ועוד 0 (ההפרש בין 15 ל-15 במשלוח השני) ועוד 99 (ההפרש בין 100 ל-1 במשלוח השלישי), ולכן ערך השונות של אוסף המשלוחים הינו 114.
עזרו לסבתא סמית וכתבו עבורה אלגוריתם, שיקבל את n (מספר הבננות), את m (מספר המשלוחים) ואת B (מערך באורך n המייצג את משקלי הבננות של סבתא סמית), וידפיס את ערך השונות הקטן ביותר שהיא יכולה להשיג על ידי חלוקת n הבננות ל-m משלוחים לא ריקים.
הצג פתרון
תובנות:
- אפשר למיין את המערך B, וקיים פתרון אופטימלי שבו כל המשלוחים הם טווח רציף במערך הזה.
אינטואיציה: ניקח פתרון אופטימלי שזה לא המצב בו, כלומר יש בו 2 משלוחים, משלוח x ומשלוח y, כך שבמשלוח x יש בננות שקלות מהבננה הכבדה ביותר במשלוח y וכבדות מהבננה הקלה ביותר במשלוח y. נוכל להחליף בין הבננה הכבדה ביותר במשלוח x לבין הבננה הקלה ביותר במשלוח y עד שהם כבר לא חופפים, וכך לקבל בסוף משלוחים רציפים, כשערך השונות בהכרח יקטן, בסתירה 😊
בהמחשה, הציר השחור מייצג משקלי בננות עולים, כל צבע משלוח, ואורך הקווים מעל הבננות את התרומה לערך השונות של כל משלוח. ההחלפות יכולות רק להקטין את ערך השונות הכולל משום שהקווים של 2 הקבוצות חופפים תחילה ולכן מכסים בהכרח את כל הטווח מהבננה הקלה ביותר מ-2 המשלוחים לכבדה ביותר בשניהם, ואחרי הפעולה הם כבר לא יכסו את כל הטווח ולא תהיה ביניהם חפיפה.
- אחרי שממיינים את המערך B, לחלק ל-m משלוחים זה בעצם לבחור m – 1 מקומות שבהם מתחילים משלוח חדש:
נסמן את סדרת המקומות האלו ב- i[0], i[1], ... i[m - 2]. אזי ערך השונות יהיה
B[n-1]-B[i[m-2]]+B[i[m-2]-1]-B[i[m-3]]+⋯+B[i[1]-1]-B[i[0]]+B[i[0]-1]-B[0]
כלומרB[n-1]-B[0]+∑〖B[i[j]-1]-B[i[j]]〗, כאשר ∑ זה סכום הביטוי אחריו עבור כל j מ-0 עד m - 2.
כלומר כל בחירה של m-1 מיקומים שונים i[0], i[1], ... i[m - 2] מקבילה לחלוקה למשלוחים, ואנו רוצים למצוא את החלוקה עם ערך השונות הקטן ביותר.
זה יקרה אם נבחר את m – 1 המקומות עם ההפרשים B[i – 1] – B[i] הקטנים ביותר במערך B הממוין.
אלגוריתם:
- מיין את המערך B
- צור מערך C באורך n – 1 כך שלכל i מ-0 עד n-2 מתקיים C[i] = B[i]-B[i + 1]
- מיין את המערך C
- ans → סכום m – 1 האיברים הראשונים במערך C, ועוד B[n – 1] – B[0]
- הדפס את ans כתשובה
סיבוכיות זמן: O(n log n)
שאלה שלישית - ג'קפרוט
דנדי ואלינגטון זכו במדליות באולימפיאדה הבינלאומית במדעי המחשב לתפוחים, וזכו לטיול עם רובן בסינגפור.
הם נתקלו בפרי ענק, גדול משלושת ראשיהם, בשם ג'קפרוט.
בשבוע שאחרי, יורק המאמן טייל באוגנדה, ומצא עץ שעל אחד הענפים שלו גדל ג'קפרוט אחד.
התברר להם שהפרי המטורף הזה גדל על עצים, ולפעמים משקלו מעל 50 ק"ג!
כל שנה על העצים גדלים מאות פירות עצומים.
איך העצים האלו לא קורסים?!
הם החליטו לעשות מחקר רציני ולבדוק מה ההפרשים בעומסים בין הענפים שניתן לראות בטבע. לצורך כך הם רוצים לחקור עצי מודל בלבד - עצים בעלי 2 ענפים שנמצאים בדיוק אחד מול השני. נקרא להם ענף ימין וענף שמאל.
על כל ענף יכולים להיות מספר פירות ג'קפרוט.
העץ מאוזן לחלוטין אם המשקל הכולל של 2 הענפים זהה זה לזה, ואם הוא לא – הוא נוטה תמיד לכיוון הענף שעליו משקל רב יותר.
משום שצפיפות הגזע משתנה מעץ לעץ זווית הנטייה לא מרמזת לנו על ההפרש בין המשקלים שעל הענפים.
ניתן לפי צורת העץ לזהות בוודאות האם 2 הענפים מכילים משקל זהה, או האם אחד הענפים כבד יותר מהשני (ואם כן – איזה מהם), אבל לא ניתן להסיק מידע נוסף.
לצורך המחקר רובן הציע להכין מראש סט משקולות כלשהו שיוכלו לצאת איתו למסע.
הוא יכול לתלות חלק מהמשקולות על הענפים השונים של העץ (לבחירתו על אילו ענפים יתלה את המשקולות), להסתכל על העץ ולהבין האם לאחר תליית המשקולות העץ מאוזן, או האם אחד הענפים כעת כבד יותר מהשני (ואיזה מהם).
הוא יכול לחזור על הפעולה כרצונו ולשנות את תליית המשקולות בהתאם (אבל כמובן לא לגעת בפירות שהיו על הענפים בהתחלה!). בסופו של דבר הוא ירצה לאזן את העץ לחלוטין (אחרי שיוסיף לענפים משקולות לבחירתו).
מובטח שהעץ לא יקרוס כתוצאה מהבדיקות (גם אם שמים הרבה משקל בצד אחד), ואין משמעות למרחק של המשקולת מבסיס הענף, רק למשקל הכולל בכל צד.
משיקולים בוטניים אנו יודעים שתמיד ההפרש בין 2 הענפים בעצי מודל של ג'פרוט יהיה מספר שלם בין 1 ל-N ק"ג.
נרצה שבאמצעות סט המשקולות ניתן יהיה לאזן כל עץ מודל שרובן יכול להיתקל בו.
דוגמה לתהליך: אם במקור על עץ כלשהו היה הפרש של 3 (כשהענף הימני כבד ב-3 מהשמאלי), והיו לו משקולות במשקלים 8, 7 ו-4, הוא היה יכול לאזן את העץ אם על הענף הימני היה שם משקולת של 4 ועל הענף השמאלי משקולת של 7.
עזרו לרובן וכתבו עבורו אלגוריתם, שמקבל כקלט את N, ומדפיס את סט המשקולות בעל מספר המשקולות הקטן ביותר שיספיק לרובן עבור המשימה.
אם יש כמה סטים אפשריים של משקולות עם אותו מספר המשקולות (הקטן ביותר האפשרי), כל אחד מהם יתאים.
הסבירו למה הסט שהאלגוריתם שלכם מוצא הוא באמת בעל מספר המשקולות הקטן ביותר שמתאים למשימה, וכיצד עבור הפרש נתון בין הענפים של עץ מסוים ניתן לאזן אותו (כמובן שרובן עצמו לא יכול לדעת מראש את ההפרש ויאלץ לעשות זאת באמצעות ניסוי וטעיה).
נניח שיש לנו סט עם m משקולות.
יש לנו 3 בחזקת m דרכים שונות לשים את המשקולות האלו על הענפים (כל משקולת יכולה להיות או על ענף ימין, או על ענף שמאל, או בכלל לא על העץ, כלומר 3 אפשרויות לכל משקולת). אחת מהאפשרויות היא לא לשים אף משקולת על העץ (מה שלא מאזן שום משקל), ובטבע יש 2N הפרשים שונים מאפס שצריך לאזן (ענף ימין יכול להיות כבד מענף שמאל ב-1 עד N ק"ג ולהפך), לכן חייב להתקיים:
3^m-1≥2N⇒m≥log_3〖2N〗+1
סט המשקולות שנבחר יהיה בגודל המינימלי שמקיים את זה ויכיל את כל החזקות של 3 (1, 3, 9, ...) עד שהסכום שלהן גדול שווה ל-N:
[הערה: בסוף הפתרון הזה תהיה גם אינטואיציה לדרך שבה אפשר לעלות על זה]
זה אכן יוצר את הסט המינימלי האפשרי:
שימו לב שבבסיס 3 סכום המשקולות שלנו הוא 1111... (כמספר המשקולות בסט – נסמנו m), ואם נכפיל ב-2, 222...., ואם נוסיף 1 נקבל 1 ו-m אפסים, כלומר 3 בחזרת m, כלומר:
כלומר אנחנו עוצרים בפעם הראשונה שבה מספר המשקולות מקיים את התנאי שהראינו שהכרחי, ולכן לא קיים סט משקולות קטן יותר שאיתו ניתן לאזן כל הפרש עד N.
נשאר להראות כיצד ניתן לאזן הפרשים כאלו.
נניח שנתון לנו הפרש של x≤N ונניח בה"כ שענף ימין הוא הכבד יותר (כלומר כבד מענף שמאל ב-x ק"ג).
אלגוריתם לאיזון יכול להיות:
עוד גישה לפתרון (גישה זו יכולה להיות יותר אינטואיטיבית. היא בסוף מובילה לאותו הסט בדיוק, אבל בדרך אחרת ולא מפורשת):
אלגוריתם האיזון של העצים הוא בעצם אלגוריתם לייצוג ההפרש כסכום והפרש של משקולות (לשים בענף הכבד יותר = להגדיר את ההפרש, לשים בענף הקל יותר = להקטין את ההפרש).
נניח שיש לנו סט A שבעזרתו ניתן לייצג את כל ההפרשים עד ל-M באופן יחיד. נסתכל מה יקרה אם נוסיף את המספר 2M+1 לסט.
אם לא נשתמש במספר 2M+1 נוכל ליצור בדיוק את כל ההפרשים בין 1 לM כמו מקודם.
אם נחסר מהמספר 2M+1 הפרש מA נוכל להשיג את כל ההפרשים
M + 1≤ x ≤ 2M+1 באופן יחיד.
אם נחבר את המספר 2M+1 עם הפרש מ-A נוכל להשיג את כל ההפרשים
2M+1 ≤ x ≤ 3M+1 באופן יחיד.
לכן ניתן לקחת סט שמייצג את כל ההפרשים עד M להוסיף לו את האיבר 2M+1 ונקבל סט חדש שמייצג את כל ההפרשים עד ל-3M+1.
מכאן ניתן להגיע לדרך הבאה, נתחיל עם משקולת בגודל 1, שהיא בעצם מצליחה לבטא את כל ההפרשים עד 1. עכשיו כל פעם נרחיב בשיטה שמצאנו, נוסיף את המשקולת החדשה ונעדכן את M,כל פעם נרחיב את הסט עד שנכלול את N.
נגדיר סט משקולות.
נגדיר משתנה שלם M=1.
כל עוד M < N:
- נכניס את 2*M + 1 לסט המשקולות.
- M=3*M + 1
החזר את הסט משקולות.
הסיבוכיות גם כאן (O(log_3(N).
בעצם הסט הזה שמצאנו הוא יכול לאזן את כל המספרים עד N בגלל מה שהראנו בהתחלה (אלגוריתם האיזון יהיה האלגוריתם הרקורסיבי שמצאנו).
בנוסף הסט הזה הוא תמיד אופטימלי. בגלל שהוא מייצג כל מספר באופן יחיד ולא מייצג מספרים שהוא לא צריך בשביל להגדיל את M. הסט מכסה בדיוק את המספרים בין –(3M+1)≤ x ≤ 3M+1, המספרים החיוביים נדרשים כדיי לכסות את ההפרשים, והשליליים חייבים להיות שם כי אם אני יכול לייצג את x אני יכול לייצג את -x.
ולכן הסט הזה הוא תמיד הסט שמכסה הכי הרבה בגודלו, מה שמבטיח שהסט שנחזיר יהיה אופטימלי.
הצג פתרון
שאלה רביעית- דומדמניות
א. האחים רד וגולדן משחקים במשחק הדומדמניות.
במשחק יש ערימה עם n דומדמניות.
שני השחקנים רואים כמה דומדמניות יש בערמה בכל שלב במשחק. רד וגולדן משחקים במשחק לסירוגין, כלומר רד עושה תור, ואז גולדן, ואז רד, ואז גולדן וכו'.
רד מתחיל במשחק, ועליו לקחת בין 1 ל- n-1 דומדמניות מהערמה בתור הראשון.
לאחר מכן, בכל תור, כל שחקן חייב לקחת לפחות דומדמנית אחת מהערמה, אך לא יותר ממספר הדומדמניות שלקח השחקן (השני) בתור האחרון.
מי שאין לו מהלך חוקי בתורו – מפסיד במשחק, וכאמור רד מבצע את המהלך הראשון.
בהנחה שרד וגולדן הם שחקנים שלא עושים טעויות ומשחקים תמיד את האסטרטגיה הטובה ביותר (כלומר אם לאחד מהם יש אסטרטגיה שהוא יכול לנצח בה, הוא ישחק לפיה ולא יעשה טעות שתאפשר לשחקן השני לנצח), כתבו אלגוריתם שמקבל את מספר הדומדמניות במשחק (n) ויקבע האם רד (השחקן שהתחיל ראשון) ינצח במשחק.
ב. רד וגולדן במשחקים במשחק הדומדמניות עם מספר ערמות!
במשחק יש m ערמות, בכל ערימה כמות דומדמניות נתונה במערך D (D[i] זו כמות הדומדמניות בערמה ה-i). שני השחקנים כמובן רואים את כמות הדומדמניות בכל אחת מהערמות בכל שלב במשחק.
כעת, רד מתחיל במשחק, ויכול לבחור את אחת הערמות ולקחת ממנה מספר חיובי גדול מ-1 של דומדמניות. בתורות הבאים, על כל שחקן לבחור ערימה ולקחת ממנה כמות דומדמניות כלשהי בין 1 למספר הדומדמניות שנלקחו בתור האחרון במשחק (לא בהכרח מאותה הערימה). מי שאין לו מהלך חוקי בתורו מפסיד במשחק, וידוע שרד וגולדן לא עושים טעויות.
כתבו אלגוריתם שמקבל את מספר הערמות (m) ואת מספר הדומדמניות בכל ערימה (המערך D), ויקבע האם רד ינצח במשחק.
שאלה זו עוסקת בענף של מתמטיקה ומדעי המחשב שנקרא תורת המשחקים הקומבינטורית, שמהווה מקור להרבה חידות מעניינות.
הסבר מפורט על בעיות מסוג זה ניתן לראות בפתרון של השאלה האחרונה של שלב ב' 2022 (כאן).
א.
האלגוריתם כאן פשוט למדי:
אם n חזקה של 2, קבעו שגולדן מנצח, אחרת רד מנצח.
ניתן להגיע לאינטואיציה הזו אם מתחילים לשחק עם מספרים קטנים ומזהים את החוקיות, או מגיעים לתובנות חלקיות בהדרגה:
-
אם n אי זוגי, רד יכול לקחת דומדמנית אחת ואז כל שחקן בתורו חייב לקחת דומדמנית אחת, תמיד רד מקבל ערימה עם מספר אי זוגי של דומדמניות ויהיה לו מהלך חוקי, וגולדן ערימה עם מספר זוגי של דומדמניות ולכן בסוף הוא יהיה זה שבתורו מקבל ערימה ריקה ואין לו מהלך חוקי, ומפסיד 😊
-
אם n זוגי ולא מתחלק ב-4, רד יכול לקחת 2 דומדמניות. ואז כל עוד גולדן ייקח 2 רד יעשה את אותו הדבר ובדומה לסעיף הקודם תהיה התכונה שרד מקבל ערימה עם מספר דומדמניות שלא מתחלק ב-4 ולכן בפרט לא 0, וגולדן יקבל את ה-0. אם בתור מסוים גולדן יחליט לקחת דומדמנית אחת, רד יקבל ערימה עם מספר אי זוגי של דומדמניות וכל שחקן תמיד יקח דומדמנית אחת, כלומר הגענו למשחק זהה למקרה הקודם.
-
אם n מתחלק ב-4 אבל לא ב-8....
בכל המקרים האלו (כלומר אם n מתחלק ב-2 בחזקת k אבל לא ב-2 בחזקת k+1) רד מנצח, ועליו לקחת 2 בחזקת k דומדמניות במהלך הראשון שלו.
אבל אם n הוא חזקה של 2, לא משנה כמה דומדמניות רד יקח, המספר שישאר לא יהיה חזקה של 2, ונגיע לאחד מהמצבים מהסוגים הקודמים (n מתחלק בחזקה כלשהי של 2 אבל לא בבאה), והמהלך המנצח של רד במקור יהיה כעת מהלך חוקי של גולדן ויעזור לו לנצח.
פתרון פורמלי יהיה:
ב. הפתרון הרשמי:
דרך נוספת לפתור את השאלה (קרדיט: אורי פרנקל ואיתמר ניר) היא להבין שאם יש מספר אי זוגי של דומדמניות בסך הכל, רד מנצח אם יקח דומדמנית אחת, ואז בכל תור גולדן יקבל מספר זוגי (ובסוף אפס וישאר ללא מהלך) ורד מספר אי-זוגי של דומדמניות.
אם יש מספר זוגי של דומדמניות בסך הכל בתחילת המשחק, כמובן שהשחקן הראשון שלוקח מספר אי זוגי מפסיד, כי השחקן הבא יקבל מספר אי זוגי של דומדמניות ויוכל לקחת דומדמניות אחת ולהביא למשחק הקודם. אז אפשר להניח שאף שחקן לא יקח מספר אי זוגי של דומדמניות, ובאופן רקורסיבי פשוט לחלק את מספר הדומדמניות בכל ערימה ב-2 (ולעגל למטה), ולפתור את השאלה עבור המערך שנשאר. המשחק הרי שקול כשכל מהלך במשחק המקורי הוא לקחת פי 2 מאשר המהלך המקביל במשחק אחרי החלוקה ב-2. פתרון רקורסיבי כזה יהיה בסיבוכיות של O(m * n * log d) כאשר d זה מספר הדומדמניות הגדול ביותר שקיים בערימה.
שימו לב שדרך הפתרון הזו מסווגת את המצבים ההתחלתיים בלבד, ולא מצבים באמצע המשחק, וקשה ממנה להבין בהנתן מצב כלשהו באמצע המשחק כיצד על השחקן לשחק על מנת לנצח, בניגוד לדרך הקודמת.
[למי שרוצה להעמיק הרבה מעבר לידע הנדרש בשלב זה - תיאורטית זו סיבוכיות האלגוריתם הרקורסיבי לא שונה מהסיבוכיות של הפתרון הקודם, כי פעולת הקסור גם כן בסיבוכיות של מספר הביטים, שהיא לוג של המספר עצמו, אבל בפועל כשהמספרים נכנסים לרגיסטר במחשב, פעולת הקסור היא O(1) כי זו פעולת מעבד אחת, אז האלגוריתם הראשון יעיל יותר (ובאופן כללי ניתן למקבל את פעולת הקסור כשעושים את הקסור בביטים השונים במקביל, אבל לא את הרקורסיה).]
