במעבדה עומדים 1000 בקבוקים ממוספרים מ-1 עד 1000. בכולם נוזל שקוף וחסר ריח, וכולם נראים זהים לחלוטין.

באחד מהם, ורק באחד, מומס חומר סימון מיוחד.

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

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

איך מאתרים בוודאות מוחלטת את הבקבוק המסומן, בסבב בדיקה יחיד?

שימו לב: אין כאן ניחוש ואין כאן מזל. השיטה הנכונה מזהה את הבקבוק בכל אחד מ-1000 המקרים האפשריים.

רמז דק

בסוף התהליך כל אחת מעשר הפיסות תהיה שחורה או לבנה. כמה תוצאות שונות אפשר לקבל בסך הכול?

2 בחזקת 10 שווה 1024 - קצת יותר מ-1000. זה לא צירוף מקרים אלא בדיוק לב הפתרון.

רמז עבה

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

כתבו את מספר הבקבוק בבסיס 2, כלומר כסדרה של עשר ספרות שכל אחת מהן 0 או 1.

עכשיו החליטו כך: פיסה מספר i תיטבל בתערובת של כל הבקבוקים שאצלם הספרה במקום ה-i היא 1.

פתרון

ממספרים את הבקבוקים מ-0 עד 999 וכותבים כל מספר בבסיס 2 בעזרת עשר ספרות בינאריות. עשר ספרות מספיקות, מפני ש-2 בחזקת 10 שווה 1024 והוא גדול מ-1000.

מסמנים את עשר הפיסות במספרים 0 עד 9, כאשר פיסה מספר i אחראית על הספרה הבינארית שמשקלה 2 בחזקת i.

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

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

דוגמה: נניח שהבקבוק המסומן הוא מספר 733. בבסיס 2 הוא נכתב 1011011101, כלומר 512 ועוד 128 ועוד 64 ועוד 16 ועוד 8 ועוד 4 ועוד 1, שהם יחד 733.

לכן הבקבוק הזה תרם טיפה לתערובות של הפיסות 0, 2, 3, 4, 6, 7 ו-9 בלבד, ובדיוק הפיסות האלה ישחירו. הפיסות 1, 5 ו-8 יישארו לבנות, והצירוף מצביע על 733 ורק עליו.

מספיקות עשר פיסות נייר וסבב בדיקה יחיד כדי לאתר בוודאות אחד מתוך 1000 בקבוקים.

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