את החידה שלפנינו חיבר המתמטיקאי האנגלי הנודע, הנרי ארנסט דודיני: הסולטאן מעוניין לשלוח לקרב יחידת חיל רגלים שאת לוחמיה ניתן לסדר בשתי קבוצות ריבועיות בתריסר דרכים שונות. מה המספר המזערי של לוחמים שיש לכלול ביחידה כזו?
דוגמה: יחידה שבה 130 לוחמים ניתנת לסידור בשתי קבוצות ריבועיות בשתי דרכים שונות:
לוקחים 28 גרגרי אורז, ומחלקים אותם לערמות בצורה כלשהי (בכל ערמה יש גרגר אורז אחד או יותר).
נמלה מגיעה לערמות הגרגרים, אוספת גרגר אחד מכל ערמה - ויוצרת מכל אלו ערמה חדשה - ערמות שהיה בהן רק גרגר אחד נעלמות כמובן. הנמלה חוזרת על הפעולה שוב ושוב. למשל - אם היו רק 6 גרגרים, המסודרים בערמות 2, 2, 2 אחרי סיבוב אחד של הנמלה המצב יהיה - 1, 1, 1, 3 אחרי הסיבוב הבא - 2, 4.
במקרה של 28 גרגרים, האם קיים מצב יציב (כלומר מצב שלאחר שמגיעים אליו הוא יישאר אותו דבר אחרי כל סיבוב של הנמלה), ומהו? האם בהכרח מכל מצב שהוא, אחרי מספיק סיבובים נגיע למצב היציב (הוכיחו שכן או מיצאו דוגמת נגד)?
פתרון
מצב יציב הוא מצב שבו הערמות מהוות סדרה חשבונית עם איבר פותח 1 והפרש 1 (כמו 1,2 או 1,2,3,4) במקרה שלנו 1,2,3,4,5,6,7
בסכום הימני, הרכיבים שסימנם שלילי הם אלה שבהם k אי-זוגי. מכאן שבסכום הכולל מתקזזים כל הרכיבים שבהם k אי-זוגי ונותרים רק רכיבים שבהם k הוא זוגי, שהם הרכיבים שבהם החזקה של וגם של היא זוגית. לכן הוא מורכב כולו ממספרים שלמים ובעצמו מספר שלם.
הביטוי המקורי שווה ל
וראינו שסכום שני האיברים הראשונים
הוא מספר שלם, והאיבר השלישי
קרוב מאד לאפס. לכן חיסור האיבר השלישי מסכום שני האיברים הראשונים ייתן מספר שקרוב מאד למספר שלם, שבו לפחות עשר הספרות הראשונות מימין לנקודה העשרונית, ובפרט הספרה השמינית, הן כולן 9.
למלך היו 100 מתמטיקאים בכלא. יום אחד הוא אסף אותם והכריז: "עד הלילה תהיו ביחד ותהיה לכם הזדמנות לגבש אסטרטגיה. לאחר מכן אשים כל אחד מכם בתא מבודד. בכל זמן שארצה אבחר מישהו באקראיות ואשים אותו בחדר שכל מה שיש בו זה נורה ומתג. מי שבפנים יוכל לשנות את מצב הנורה (אם היא הייתה דלוקה לכבות ואם כבויה להדליק) או לא לעשות כלום. בהתחלה הנורה תהיה כבויה. המטרה שלכם שבאחד הימים יבוא אלי מישהו ויגיד שכולם כבר היו בחדר לפחות פעם אחת. אם הוא יצדק, אשחרר את כולכם, אך אם יטעה, אוציא את כולכם להורג." מה צריכה להיות האסטרטגיה של המתמטיקאים?
הערה: לצורך החידה למתמטיקאים יש חיי אלמוות. כל אחד מהם נכנס מספר פעמים לא מוגבל לחדר, כלומר אין דבר כזה מישהו שנכנס בפעם האחרונה. כמו כן, אין המתמטיקאים יודעים את הזמנים בהם מוכנסים אנשים ואין הם יודעים את המספר הסידורי של כניסתם (בפרט הראשון שנכנס אינו יודע שהוא הראשון).
פתרון
על המתמטיקאים למנות ראש קבוצה. כל אחד מה-99 האחרים יפעל לפי האלגוריתם הבא: בפעם הראשונה שהוא רואה את הנורה כבויה, הוא מדליק אותה. בכל מקרה אחר, הוא לא עושה כלום. ראש הקבוצה פועל לפי האלגוריתם הבא: אם הנורה כבויה, הוא לא עושה כלום, ואם היא דלוקה, הוא מכבה אותה וסופר את מספר הפעמים שהוא מכבה. לאחר שכיבה 99 פעמים, בהכרח כולם כבר היו בחדר כי כל אחד הדליק פעם אחת ואף אחד לא כיבה.
חידת המשך: נניח ולא ידוע המצב בתחילתי של הנורה בחדר. כלומר ייתכן שלפני שהוכנסו המתמטיקאים היא הייתה דלוקה, וייתכן שהיא הייתה כבויה. באיזו אסטרטגיה על המתמטיקאים להשתמש כעת?
פתרון
המתמטיקאים יפעלו על פי אותו אלגוריתם כמו קודם, רק שהפעם כל אחד מ-99 המתמטיקאים ידליק את הנורה הן בפעם הראשונה והן בפעם השנייה שהוא רואה אותה כבויה. ראש הקבוצה יספור הפעם עד 198. כך מובטח שאפילו אם הנורה הייתה דלוקה בהתחלה, וראש הקבוצה ספר אותה בטעות כמתמטיקאי, זה רק אומר שאחד המתמטיקאים הספיק להדליק את הנורה רק פעם אחת, ובכל מקרה כולם ביקרו בחדר.
חידת המשך 2: בנוסף לחידה הראשונה (הנורה בהתחלה כבויה), המלך מודיע למתמטיקאים כי הוא עלול לנסות לבלבל אותם ולשנות בעצמו מדי פעם את מצב הנורה - אך לא יותר מ-n פעמים. באיזו אסטרטגיה על המתמטיקאים להשתמש כעת?
פתרון
המצב בו לא ידוע מצב הנורה ההתחלתי שקול לכך שהנורה בהתחלה כבויה, אך למלך מותר לשנות את מצבה פעם אחת. על כן המתמטיקאים יפעלו על פי אותו אלגוריתם כמו קודם, אלא שעל כל מתמטיקאי שאינו ראש הקבוצה להדליק את הנורה 1+n הפעמים שהוא רואה אותה כבויה, וראש הקבוצה יספור הפעם עד 99*(n+1). כך מובטח ש-n הפעמים בהם המלך התערב בתהליך לא גרמו לכלול בספירה מתמטיקאי שכלל לא נכח בחדר.
האם יש n טבעי גדול מ-2, שלגביו קיימים מספרים טבעיים x,y,z המקיימים את המשוואה: ?
במבוא לסדרת ספריו The Art of Computer Programming הציג דונלד קנות' בעיה זו כדוגמה לבעיה מתמטית בדרגת הקושי הגבוהה ביותר, אם כי המתמטיקאי פייר דה פרמה, שעסק בבעיה 330 שנה מוקדם יותר, טען שיש לה פתרון אך אין לו מספיק מקום לכותבו.
נניח בשלילה שקיימים מספרים כאלו. נניח ללא הגבלת הכלליות . המספר האי-זוגי מתחלק ב, מכאן אי-זוגי (ומכיוון שהוא ראשוני זה שקול לכך שהוא לא 2). לכן כי הראשונים הקטנים ביותר ש-q,r יכולים להיות הם 5 ו-7.
ואז נקבל ומכיוון שמספר לא יכול להתחלק במספר שגדול ממנו, לא מתחלק ב- .
ב) תשובה: קיימים: 2, 3, 5. זה גם המקרה היחיד, הרי בסעיף א' ראינו שהאי-קיום נבע מכך שאף-אחד מהראשוניים לא היה 2 ואז אזי קל להבין שזו היא השלשה האפשרית היחידה. חידת בונוס: על איזה תנאים d צריך לענות בשביל שיהיו קיימים מספרים ראשוניים אלה?
פתרון
בינתיים לא נמצא פתרון מלא, אם כי נמצא ש-d>10, ש-d אינו יכול להיות כפולה של אף אחד מ-p,q או r, ושאם d<26 אז הוא אי-זוגי.
מופע קסמים: על הבמה קוסם, שוליה, לוח שחמט ריק (8 על 8 משבצות) ו-64 מטבעות. הקוסם יוצא, והשוליה מזמין שני מתנדבים מהקהל. השוליה אומר למתנדב אחד לומר מספר מאחד עד 64, ולמתנדב השני הוא אומר לשים מטבעות על המשבצות בלוח איך שבא לו. מותר למתנדב לשים כמה מטבעות שהוא רוצה, או לא לשים בכלל, אבל אסור לו לשים מטבע על כמה משבצות, או לשים כמה מטבעות על אותה משבצת.
אחרי זה השוליה רשאי להסיר מטבע אחד בלבד מהלוח, או להוסיף מטבע אחד, או להשאיר את הלוח כפי שהוא. אסור לו להזיז מטבע למשבצת אחרת.
הקוסם חוזר, מסתכל על הלוח, והוא יודע איזה מספר המתנדב הראשון בחר. איך הם עושים את זה?
פתרון
השוליה והקוסם ממספרים מראש את משבצות הלוח מ-0 עד 63 בבסיס בינארי כך שכל מספר יכיל 8 ספרות (אם צריך מוסיפים אפסים בהתחלה) השוליה מבצע XOR על הערכים של המשבצות עליהן הונחו המטבעות (כל ספרה בנפרד) ושוב XOR על התוצאה ועל המספר שבחר המתנדב הראשון (פחות 1). התוצאה היא מספר בין 0 ל-63, והשוליה שם או מסיר מטבע במשבצת שזהו מספרה. כעת הקוסם יבצע XOR על כל ערכי המשבצות שמכוסות במטבעות והתוצאה (ועוד 1) היא המספר שבחר המתנדב.
