חשיבה מתמטית

[inbarsery]

חשיבה מתמטית

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

 

[איגור קרסיק]

פתרון ל-1

התשובה היא כן. יהי n מספר שלא מתחלק ב-2 וב-5 [ולכן גם לא ב-10]. נסתכל בסדרה בת n+1האברים:

1,11,111,...,1...1 [there are n+1 ´1´]​

נחלק כל אחד מהם ב-n ונמצא את השארית. כך יתקבלו n+1 שאריות. משום שקיימות n שאריות שונות בחלוקה ב-n אזי ישנם 2 מספרים שונים בסדרה הנ"ל שיש להם שארית שווה. נסמנם ב-a ו-b כאשר b הוא הגדול מבינהם. b-a הוא מספר שמתחלק ב-10 וכן ב-n ומשום ש-n לא מתחלק ב-10 אז נקבל ש:

[a-b]/10​

גם כן צתחלק ב-n [זה נובע בקלות מהמשפט היסודי של האריתמטיקה]. את המספר החדש נמשיך לחלק ב-10 עד שלא נוכל לעשות זאת ללא שארית. נשים לב שכל אחד מאותם מספרים שנחלק ב-10 יתחלק גם ב-n. המספר האחרון בשרשרת זו יתחלק ב-n וכל סיפרותיו יהיו 1. אם כן מצאנו מספר שכל סיפרותיו הן 1 והוא כפולה של n. נראה לי שהשאלה השנייה מצריכה ידע בתורת הגרפים [תורה שאינני יודע כלל].

 

[inbarsery]

תודה

 

[איגור קרסיק]

טלמון [או משהו אחר]

יש לכם מושג איך פותרים את 2?

 

[טלמון סילבר]

בינתיים אין לי רעיון. אולי זה משהו

מתחום הגראפים? תחום זה מעולם לא למדתי ואינני מכיר. אז מה אומרים המומחים שלנו בתחום הזה?

 

[Fingertip]

זו שאלה קלאסית באולימפיאדות

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