כניסה

פינת פוגי

פינת פוגי היא פינת חידות מתמטיות של בית הספר למדעי המחשב.
מדי שבוע תתפרסם כאן חידה.
את פתרון החידה, בליווי נימוק קצר כמובן, ניתן לשלוח, במהלך שבוע מיום פרסום החידה,
לכתובת pinat.poogy@gmail.com 

היכל התהילה של פוגי

 

סמסטר א' תשע"ב

1. אלעד שמיטנקה

2. רן כהן

3. חן כהן

 

סמסטר ב' תשע"ב

1. חן כהן

2. אלעד לוז

 

תשע"ב - חידות קודמות, פיתרונן ושמות הפותרים נכונה:

 

חידה 1:פוגי נגד מאה

 

100 אנשים עומדים במעגל ועוצמים את עיניהם. פוגי חובש לראשו של כל אחד מהם כובע שחור או כובע לבן. כאשר כולם פוקחים את עיניהם כל אחד רואה את הכובע של כל האנשים מלבד את של עצמו, ופוגי מבקש מכל אחד מהם לנחש וללחוש באוזנו מהו צבע הכובע שלראשו. כיצד יכולה הקבוצה להבטיח שלפחות 50 מהאנשים ינחשו נכונה? (כמובן, אסור למשתתפים לדבר ביניהם במהלך המשחק, אך הם רשאים לתאם אסטרטגיה לפני שהמשחק מתחיל)

 

פתרון חידה 1 ושמות הפותרים

 

פתרון חידה 1: נשים לב שכל אחד מהאנשים העומדים במעגל היה יכול בקלות לקבוע את צבע הכובע שלראשו לו היה יודע אם מספר האנשים שלראשם כובע שחור הוא זוגי או אי-זוגי. זה נובע מכך שאדם כזה יכול לספור את הכובעים השחורים שהוא רואה, ואם זוגיות המספר היא כזוגיות מספר כל האנשים שלראשם כובע שחור אז הוא מסיק שכובעו לבן ואחרת שכובעו שחור. אם כן, נסתכל על אסטרטגיה שבה 50 מהאנשים (שזהותם נקבעת מראש) מניחים שמספר האנשים שלראשם כובע שחור הוא זוגי ו-50 האחרים מניחים שהוא אי-זוגי, וכל אחד קובע את צבע הכובע שלראשו בהינתן ההנחה שלרשותו. מאחר שמספר האנשים שלראשם כובע שחור הוא בהכרח זוגי או אי-זוגי בדיוק 50 ישיבו נכון.

 

פותרים נכונה: נדב פורז וירדן יעקבסון.

 

חידה 2: מי מגיע למאה?

 

פוגי ופוגית משחקים במשחק הבא: כל אחד בתורו בוחר מספר טבעי בין 1 ל-10 (כולל) ומכריז עליו. פוגי הוא הראשון שבוחר מספר, אחריו פוגית בוחרת, אז שוב פוגי, וכך הלאה. מי שמכריז/ה על מספר שסכום כל המספרים שהוכרזו עד אליו (כולל) הוא בדיוק 100 מנצח/ת במשחק. האם תוכלו להציע לפוגית אסטרטגיית משחק שתבטיח לה ניצחון? ולפוגי?

 

פתרון חידה 2 ושמות הפותרים

 

פתרון חידה 2: לא ניתן להציע לפוגית אסטרטגיית משחק שתבטיח לה ניצחון, משום שהאסטרטגיה שנתאר להלן מבטיחה את ניצחונו של פוגי. פוגי בתחילה בוחר את המספר 1, והחל משלב זה לכל מספר שבוחרת פוגית יבחר פוגי מספר שהסכום שלו עם המספר של פוגית הוא 11 (שימו לב שזה אפשרי לכל בחירה של פוגית). לאחר תשעה סיבובים כאלו המספר שיבחר פוגי ישלים את סכום כל המספרים שנבחרו עד כה ל-100 ופוגי ינצח.

פותרים נכונה (בסדר כרונולוגי): רן כהן, אלעד שמיטנקה, דמיטרי רבינוביץ', מאור רחמים, אור עופר.

 

חידה 3: פוגי והעכביש

 

פוגי מחזיק גומיה אופקית מתוחה באורך מטר אחד שמחוברת לקיר ובקצה שלה (שצמוד לקיר) נמצא עכביש זעיר. התהליך שלהלן חוזר שוב ושוב: העכביש מתקדם 1 ס"מ לכיוונו של פוגי, ופוגי המבוהל מתרחק מטר אחד מהקיר ומושך איתו את הגומיה (כשהגומיה נמתחת מיקומו היחסי של העכביש על הגומיה נותר כשהיה). האם בסופו של דבר יגיע העכביש אל פוגי?

 

פתרון חידה 3 ושמות הפותרים

 

כן. בצעד הראשון העכביש מתקדם 1/100 מהגומיה, בצעד השני 1/200, בשלישי 1/300 וכך הלאה. לכן לאחר שהתהליך חוזר n פעמים החלק היחסי של הגומיה שבין הקיר לעכביש הוא

(1+1/2+1/3+…+1/n)/100.

מאחר שהטור ההרמוני מתבדר, עבור n גדול דיו נקבל מספר שגדול מ-1, כלומר העכביש יגיע לפוגי.

פותרים נכונה (בסדר כרונולוגי): אביעד פינלס, אלעד שמיטנקה, רן כהן.

 

חידה 4: אחד שמכיר

 

לכל שני סטודנטים במכללה יש מספר אי-זוגי של סטודנטים אחרים במכללה ששניהם מכירים. האם יש במכללה סטודנט/ית שמכיר/ה מספר אי-זוגי של סטודנטים? (יש להניח ש"היכרות" היא סימטרית).

 

פתרון חידה 4 ושמות הפותרים

 

פתרון חידה 4: לא. נראה שלכל סטודנט/ית במכללה יש מספר זוגי של מכרים. ניקח את קבוצת המכרים של סטודנט/ית כלשהו/י, ונשים לב שלכל חברי הקבוצה יש מספר אי-זוגי של מכרים בתוכה (הרי אלו הם המכרים המשותפים עם הסטודנט/ית שבחרנו). אם נסכום את מספרי המכרים בקבוצה של כל חברי הקבוצה בהכרח נקבל מספר זוגי, הרי כל היכרות נספרת פעמיים. מאחר שמספר זוגי זה הוא סכום של מספרים אי-זוגיים, מספר המחוברים בהכרח זוגי. לכן מספר הסטודנטים בקבוצה (כלומר מספר המכרים של הסטודנט/ית שבחרנו) הוא זוגי. 

פותר נכונה: אלעד שמיטנקה.

 

חידה 5:פוגי הדוור

 

ברחוב אינסופי יש שורה של בתים ממוספרים במספרים הטבעיים בסדר עולה (3,2,1,...). פוגי מעוניין לחלק עלונים עם "חידת פוגי" השבועית לתיבות הדואר של 2011 בתים רצופים כך שמספרו של אף אחד מהם אינו ראשוני. לתיבות של אילו בתים תציעו לו לחלק את העלונים?

 

פתרון חידה 5 ושמות הפותרים

 

פוגי יכול לבחור, למשל, את הבתים שמספריהם  2012!+2,...,2012!+2012, שכן כל מספר מהצורה 2012!+k עבור k בין 2 ל-2012 אינו ראשוני (הרי הוא מתחלק ב-k).

פותרים נכונה (בסדר כרונולוגי): אלעד שמיטנקה, חן כהן, רן כהן, מאור רחמים.

 

חידה 6: נעים מאוד, פוגי

 

לארוע בביתם של פוגית ופוגי מגיעים ארבעה זוגות אורחים אשר מחליפים לחיצות ידיים (לא כולם לוחצים לכולם את היד, ואף אחד לא לוחץ לעצמו או לבן/בת זוגו). בתום הארוע שואלת פוגית את הנוכחים כמה פעמים הם לחצו ידיים ומקבלת מהם 9 תשובות שונות. כמה ידיים לחץ פוגי?

 

פתרון חידה 6 ושמות הפותרים

 

מתשובותיהם לשאלה של פוגית, עולה כי מספרי הידיים שנלחצו על-ידי כל הנוכחים מלבד פוגית הם  0,1,2,…,8 
נשים לב שהאדם היחיד שלא לחץ יד למי שלחץ 8 ידיים הוא זה שלחץ 0 ידיים ולכן שניהם בני זוג (ולכן אף אחד מהם אינו פוגי). מי שלחץ 7 ידיים לחץ לכל מי שנשאר מלבד זה שלחץ יד אחת ולכן שניהם בני זוג (ושוב אף אחד מהם אינו פוגי). באופן דומה מי שלחצו 2 ו-6 ידיים הם בני זוג וכך גם אלו שלחצו 3 ו-5 ידיים. לכן פוגי לחץ 4 ידיים. שניהם בני זוג (ושוב אף אחד מהם אינו פוגי). באופן דומה מי שלחצו 2 ו-6 ידיים הם בני זוג וכך גם אלו שלחצו.

 פותרים נכונה (בסדר כרונולוגי): אלעד שמיטנקה, יעל ארד, אמיתי אברהם.

 

חידה 7: שובו של פוגי הדוור

 

ברחוב יש 101 בתים ממוספרים 1,2,…,101. פוגי ופוגית משחקים במשחק הבא: כל אחד בתורו בוחר 9 בתים ומחלק לתיבות הדואר שלהם עלונים של "פינת פוגי". פוגי הוא זה שמתחיל במשחק, ולאחר 11 סיבובים נשארים רק שני בתים שלא קיבלו את העלון. אם ההפרש (החיובי) בין מספרי שני הבתים הנותרים גדול מ-54 פוגי מנצח ואחרת פוגית מנצחת. למי תוכלו להציע אסטרטגיית משחק מנצחת?

 

פתרון חידה 7 ושמות הפותרים

 

נציע אסטרטגיית משחק מנצחת לפוגי. פוגי יבחר תחילה את הבתים שמספריהם 47-55. את הבתים הנותרים ניתן לחלק לזוגות: 1 ו-56, 2 ו-57, וכך הלאה עד 46 ו-101. כעת לאחר כל סיבוב בו בוחרת פוגית 9 בתים, יבחר פוגי 9 בתים כך שבשני סיבובים אלו בדיוק 9 מזוגות הבתים שבחלוקה יקבלו את העלון לתיבת הדואר. בסופו של דבר יישאר זוג אחד של בתים שההפרש בין מספריהם הוא 55 ולכן פוגי ינצח.


 פותרים נכונה (בסדר כרונולוגי): אלעד שמיטנקה, חן כהן.


 

חידה 8: פוגי והטבלה

 

נתונה טבלה תלת-מימדית שמימדיה 8x8x8. התוכלו לעזור לפוגי למלא כל תא בטבלה ב-0 או ב-1 כך שלאורך כל קו שעובר דרכה (שורה חד-מימדית או עמודה חד-מימדית) מופיע 1 פעם אחת בדיוק?

 

פיתרון חידה 8 ושמות הפותרים

 

פתרון חידה 8: פוגי יכול למלא ב-1 את כל תאי הטבלה (i,j,k) עבורם הסכום i+j+k מתחלק ב-8, ואת התאים האחרים ב-0.

 

פותרים נכונה (בסדר כרונולוגי): אלעד שמיטנקה, יורי ארונוב, חן כהן, רן כהן.

 

חידה 9: שרשור יעיל

 

תהא A קבוצה (אינסופית) של מחרוזות בינאריות, ונניח שקיימת תוכנית מחשב "יעילה" אשר בהינתן מחרוזת בינארית קובעת האם היא שייכת ל-A או לא. התוכלו לעזור לפוגי לכתוב בעזרתה תוכנית מחשב "יעילה" אשר בהינתן מחרוזת קובעת האם היא שרשור של מספר כלשהו של מחרוזות מהקבוצה A?

 

פיתרון חידה 9

 

נניח שקיימת תוכנית מחשב יעילה עבור A. עבור מחרוזת בינרית x באורך n נגדיר גרף מכוון על קבוצת הצמתים {0,1,…,n} ונחבר צומת i בקשת מכוונת לצומת j אם תת המחרוזת של x שמתחילה בתו ה-i+1 ומסתיימת בתו ה-j שייכת ל-A. נשים לב ש-x היא שרשור של מספר כלשהו של מחרוזות מ-A  אם ורק אם בגרף זה יש מסלול מכוון מ-0 ל-n, ושניתן לבנות את הגרף ולבדוק זאת ביעילות.

 

חידה 10: פוגי והטבלה (2)

 

פוגי ממלא כל משבצת של טבלה ריבועית שמימדיה 8x8 ב-0 או ב-1. לאחר מכן פוגית מחליפה ל-1 כל 0 שסמוך לשתי משבצות בהן מופיע 1 (מימין, משמאל, מלמטה או מלמעלה). פוגית עושה זאת שוב ושוב עד שאין עוד אפסים כאלה. מהו המספר הקטן ביותר של משבצות שצריך פוגי למלא ב-1 כדי שבסופו של דבר כל איברי הטבלה יהיו 1?

 

פיתרון חידה 10

 

התשובה היא 8. אם פוגי ימלא את אלכסון הטבלה (הראשי) ב-1-ים, לאחר סדרת צעדים של פוגית כל איברי הטבלה יהיו 1. נראה גם שעליו למלא לפחות 8 משבצות בטבלה ב-1. נשים לב שכל צעד של פוגית אינו מגדיל את היקף שטח ה-1-ים שבטבלה (אשר יוגדר כסכום היקפי השטחים הרציפים בהם מופיעים 1-ים). לפיכך כדי שבסוף התהליך כל הטבלה תתמלא ב-1-ים ההיקף ההתחלתי חייב להיות לפחות 32 יחידות, ולכן על פוגי בהכרח למלא לפחות 8 תאי טבלה ב-1.

 

חידה 11: פוגי והמכונית

 

פוגי מתכנן טיול מעגלי במכונית דרך 10 נקודות ציון לפי סדר שנקבע מראש. בכל נקודה ממתין לפוגי מיכל דלק בגודל כלשהו. בגלל מחירי הדלק, כמות הדלק הכוללת בכל המיכלים היא בדיוק הכמות הנחוצה לצורך הנסיעה המעגלית. בהנחה שמיכל הדלק של פוגי ריק בתחילה, האם בהכרח קיימת נקודת ציון שאם יתחיל את הטיול ממנה יוכל להשלים את הטיול ולחזור אליה?

 

פיתרון חידה 11 ושמות הפותרים

 

כן, קיימת נקודה כזו. כדי להשתכנע בכך נתחיל מנקודה שרירותית ונסתכל על רשימת מצבי הדלק המתקבלים בהנחה שהתחלנו ממנה (המצב הראשוני הוא 0; לאחר מכן בחלק מהנקודות "כמות" הדלק עשויה להיות שלילית). נותר להיווכח שאם פוגי יתחיל מהנקודה עם מצב הדלק הנמוך ביותר הוא יצליח להשלים את הטיול המעגלי.


פותר נכונה: אלעד שמיטנקה, אלעד לוז.

 

חידה 12: פוגי והלוח

 

על הלוח כתובים המספרים הטבעיים 1,2,...,101. פוגי ופוגית משחקים במשחק הבא: כל אחד בתורו בוחר מספר שכתוב על הלוח ומוחק אותו. פוגי מתחיל במשחק, ולאחר 99 סיבובים נשארים רק שני מספרים על הלוח. אם הסכום ביניהם מתחלק ב-5 פוגי מנצח ואחרת פוגית מנצחת. למי תוכלו להציע אסטרטגיית משחק מנצחת?

 

פתרון חידה 12 ושמות הפותרים

לפוגי יש אסטרטגיה מנצחת - פוגי מתחיל בבחירת המספר 1 ולאחר כל תור שבו פוגית בוחרת מספר שהוא j מודולו 5 פוגי יבחר מספר שהוא –j מודולו 5.


פותרים נכונה: חן כהן, אלעד שמיטנקה, אלעד לוז

 

חידה 13: פוגי, פוגית ומחרוזות בינאריות

 

פוגי כתב על דף את כל המחרוזות הבינאריות באורך 100 שאפשר למחוק מהן מחצית מהתווים ולקבל מחרוזת שכולה אפסים. פוגית כתבה על דף את כל המחרוזות הבינאריות באורך 100 שאפשר למחוק מהן מחצית מהתווים ולקבל מחרוזת של אפסים ואחדים לסירוגין (כלומר 0101…01). מי מהשניים כתב יותר מחרוזות?

 

פתרון חידה 13 ושמות הפותרים

 

פתרון חידה 13: פוגית ופוגי כתבו אותו מספר של מחרוזות.

 

חידה 14: פוגי מתכנת

 

פוגי כתב את קטע הקוד הבא:

while (x>0)   x:=2012-2x;

עבור אילו ערכים שלמים של x התוכנית של פוגי עוצרת?

 

פתרון חידה 14 ושמות הפותרים

 

פתרון חידה 14: התוכנית של פוגי תעצור לכל ערך שלם של x. כדי להשתכנע בכך אפשר להראות שלכל ערך שלם של a1 בסדרה an המוגדרת על-ידי כלל הנסיגה an = 2012-2∙an-1 יש איברים שליליים.

  פותרים נכונה: ערן טיקטין, אלעד לוז, חן כהן

 

חידה 15: פוגי וסטראסן

 

פוגי התבקש על-ידי ידידו סטראסן לחשב את המכפלה של שתי מטריצות מסדר 2012. האם תוכלו לעזור לו לעשות זאת בעזרת 7 הכפלות של מטריצות מסדר 1006 (ומספר כלשהו של פעולות חיבור/חיסור מטריצות מסדר1006 )?

 

פתרון חידה 15 ושמות הפותרים:

 

  פתרון חידה 15: המטריצהA  (וכך גם B,C) מורכבת מארבע מטריצות מסדר 1006 שנסמן ב- A1,1 , A1,2 , A2,1 , A2,2 (משמאל לימין ומלמעלה למטה). פוגי יכול לחשב את 7 המטריצות הבאות בעזרת 7 פעולות כפל:

M1 = (A1,1 + A2,2)(B1,1 + B2,2)
M2 = (A2,1 + A2,2)B1,1
M3 = A1,1(B1,2 – B2,2)
M4 = A2,2(B2,1 – B1,1)
M5 = (A1,1 + A1,2)B2,2
M6 = (A2,1 – A1,1)(B1,1 + B1,2)
M7 = (A1,2 – A2,2)(B2,1 + B2,2)

בעזרתן ניתן לחשב, ללא פעולות כפל נוספות, גם את מרכיבי המטריצה C:
C1,1 = M1 + M4 – M5 + M7
C1,2 = M3 + M5
C2,1 = M2 + M4
C2,2 = M1 – M2 + M3 + M6

 

פותרת נכונה: חן כהן

 

חידה 16: השק של פוגי

 

פוגי מחליט לאסוף לתוך שק את כל המספרים הראשוניים. לשם כך הוא עובר על הטבעיים  2,3,4,5,… משמאל לימין ובכל פעם שהוא נתקל במספר שאינו מתחלק באף מספר שבשק הוא מכניס אותו לשק. לאחר כמה שעות עבודה חוטף פוגי תנומה ובמהלכה פוגית מוציאה כמה מספרים מהשק. האם ייתכן שכתוצאה מכך יכניס פוגי לשק אינסוף מספרים שאינם ראשוניים?

 

פתרון חידה 16 ושמות הפותרים:

 

לא, משום שאם המספר הגדול ביותר שפוגית הוציאה מהשק הוא x אז לכל מספר גדול מ-x2 יש מחלק (לאו דווקא ראשוני) אשר גדול מ-x, ומחלק זה או מחלק שלו בהכרח יהיו בשק.

 

פותרים נכונה (בסדר כרונולוגי): צחי מן, אלעד לוז, חן כהן, ערן טיקטין

 

חידה 17: המספר של פוגי

 

פוגית נכנסת לחדר עם 100 קופסאות מסודרות בשורה שבתוכן פתקים עם המספרים 1,2,…,100 בסדר אקראי, קוראת את כל הפתקים ואם מתחשק לה מחליפה בין שניים מהם. לאחר מכן פוגי נכנס לחדר, מקבל מספר בין 1 ל-100, ועליו למצוא את הפתק עליו מספר זה רשום מבלי לפתוח יותר מ-50 קופסאות. האם תוכלו להציע לפוגי ולפוגית אסטרטגיית משחק שתאפשר לפוגי למצוא את המספר?

 

פתרון חידה 17 ושמות הפותרים:

 

פתרון חידה 17: פוגי יפתח תחילה את הקופסה שמספרה הוא המספר שקיבל, ולאחר מכן בכל פעם יפתח את הקופסה שמספרה הוא המספר שעל הפתק האחרון שמצא עד שיגיע לפתק המבוקש. בצורה כזו ייתכן שפוגי ייאלץ לפתוח יותר מ-50 קופסאות, אולם לא קשה להיווכח שפוגית יכולה למנוע זאת (אם יש צורך) על-ידי החלפת שני פתקים מראש.

 

 פותרים נכונה (בסדר כרונולוגי): אולג קולסניצ'נקו, צחי מן.

 

חידה 18: הציון של פוגי

 

פוגי נבחן בבחינה שבה 100 שאלות בקורס שבו 100 סטודנטים. המרצה כתב במטריצה ריבועית A מסדר 100 את כל הציונים של הסטודנטים בשאלות הבחינה, כך שציוני השאלות של פוגי מופיעים באלכסון הראשי (וסכומם הוא הציון שלו). כדי לגלות את ציונו, פוגי רשאי לבחור תת-מטריצות ריבועיות ("רציפות") של A ולשאול את המרצה מהו סכום האיברים בכל אחת מהן. האם יכול פוגי לגלות את ציונו על-ידי פחות מ-100 שאלות כאלה?

 

פתרון חידה 18 ושמות הפותרים:

 

פתרון חידה 18: לא. נסמן ב-J את אוסף הקטעים שמקיפים את 100 תתי-המטריצות מסדר 1 שעל האלכסון הראשי, שסכום אורכיהם הוא 400, ונסמן ב-P את אוסף הקטעים שמקיפים את תתי-המטריצות שבחר פוגי. נשים לב כי כל קטע שמופיע ב-J מופיע בהכרח גם ב-P, כי אחרת ישנם שני איברים סמוכים במטריצה שאחד מהם על האלכסון הראשי כך שכל תת-מטריצה שבחר פוגי מכילה את שניהם או את אף אחד מהם. מכאן שאם נשנה את שני איברים אלו כך שסכומם יישאר כשהיה, פוגי יקבל את אותם סכומים ולכן בהכרח צורת חישוב הציון שלו שגויה. לכן סכום אורכי הקטעים ב-P הוא לפחות 400 ומכאן שפוגי אינו יכול להסתפק בפחות מ-100 שאלות.

 

 

 

מתעניינים באקדמית?

הזינו פרטים ונחזור אליכם בהקדם
  • מאשר/ת קבלת דיוורים לדואר אלקטרוני

לשיחה עם נציג