במסדרון בית הספר עומדות מאה ארוניות ממוספרות מ-1 עד 100, וכולן סגורות.

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

התלמיד הראשון נוגע בכל הארוניות: 1, 2, 3 וכן הלאה. התלמיד השני נוגע בכל ארונית שנייה: 2, 4, 6 וכן הלאה. התלמיד השלישי נוגע בכל ארונית שלישית: 3, 6, 9 וכן הלאה - וכך ממשיכים, עד התלמיד המאה שנוגע בארונית 100 בלבד.

אחרי שכל מאת התלמידים סיימו לעבור - אילו ארוניות נשארו פתוחות, וכמה הן?

שימו לב: אין כאן שום צורך לדמות את התהליך. שאלה אחת פשוטה על ארונית בודדת פותרת את כל החידה בבת אחת.

רמז דק

התלמיד מספר d נוגע בארונית מספר k בדיוק כאשר d מחלק את k.

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

רמז עבה

מחלקים באים כמעט תמיד בזוגות: אם d מחלק את k, גם k חלקי d מחלק את k, והשניים הם בני זוג.

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

הזוגיות נשברת במקרה אחד בלבד: כאשר שני בני הזוג הם אותו מספר עצמו, כלומר כאשר d שווה ל-k חלקי d.

נסו לרשום את כל המחלקים של 12 ואת כל המחלקים של 16, ולהשוות בין שתי הרשימות.

פתרון

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

כל הארוניות התחילו סגורות, ולכן ארונית תישאר פתוחה בסוף אם ורק אם מספר המחלקים שלה אי-זוגי.

המחלקים של 12 הם 1, 2, 3, 4, 6 ו-12 - שישה מחלקים, מספר זוגי, ולכן ארונית 12 תיסגר.

המחלקים של 16 הם 1, 2, 4, 8 ו-16 - חמישה מחלקים, מספר אי-זוגי, ולכן ארונית 16 תישאר פתוחה.

ההבדל בין השניים ברור: 16 הוא ריבוע מדויק, 4 כפול 4, ולכן המחלק 4 הוא בן זוג של עצמו ואין לו שותף נפרד שיסגור את הדלת בחזרה.

המסקנה: הארוניות שנשארות פתוחות הן בדיוק אלה שמספרן הוא ריבוע מדויק.

בטווח שבין 1 ל-100 אלה הארוניות 1, 4, 9, 16, 25, 36, 49, 64, 81 ו-100 - עשר ארוניות בסך הכול.

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