)שירשור החידות הגדול
פתרון הכובעים.
אני מצטט פה את הפתרון הסימטרי היפה של אמיר. לי היה פתרון אחר (דומה) אבל לא סימטרי.
אני מצטט פה את הפתרון הסימטרי היפה של אמיר. לי היה פתרון אחר (דומה) אבל לא סימטרי.
כל אחד יקבל על ראשו כובע אחד מתוך 1000 אפשריים, ולכן ניתו ליצג את הכובע שכל אחד יקבל ע"י מחרוזת באורך 10 ביטים.
נעמיד את כולם במעגל, עם הפנים פנימה, וכאת כל אחד יחלק את האחריות לביטים של הכובע שלו, החל מהביט הראשון עד הביט האחרון לאנשים ע"פ כיוון השעון. כלומר האיש לשמאלו יקבל את האחריות על הביט הראשון, האיש הבא בתור אחראי לביט השני, וכך הלאה, עד האיש לימינו שיהיה אחראי אל הביט האחרון.
בפרט, כל אחד מקבל אחריות על 10 ביטים - הביט הראשון של האיש מימינוו, הביט השני של האיש 2 מימינו, וכך הלאה עד היט האחרון של האיש משמאלו.
עכשיו שמים לכולם את בכובעים על הראש, ומורידים את כיסוןי העיניים.
כל אחד מחשב מהכובעים שהוא רואה את 10 הביטים שבאחריותו, ומרים פתק בהתאם לזוגיות של 10 הביטים שהוא אחראי עליה.
בשלב השלישי, כל אחד צריך לגלות את כל הביטים של הכובע שלו.
כדי לגלות את הביט ה-i, הבחור מסתכל על הפתק שהרים האיש שאחראי על הביט הזה (האיש ה-i עם כיוון השעון). הפתק הזה הוא הזוגיות של 10 ביטים שונים, שכוללים את הביט שחסר לו. נבחין כעת, כי הבחור יכול מהכובעים שהוא רואה (9 הכובעים חוץ מזה של האיש ה-i) להסיק 9 ביטים שנכנסו לחישוב, הביט היחידי שהוא לא רואה (והאיש ה-i כן רואה), זה הביט שחסר לו (ה-i בכובע שלו). ולכן, הבחור יודע 9 ביטים, ואת הזוגיות של כל 10 הביטים (כולל הביט החסר), ויכול להסיק את הביט החסר.
מכיוון שזה נכון לכל i, הבחור יכול לגלות את כל הביטים של הכובע שלו, ולכן גם את הצבע של הכובע.
מכיוון שזה נכון לכל הבחורים , כולם יכולים במקביל לגלות את הצבע של הכובע שלהם....
משה
אבי ואריה משחקים את המשחק הבא -
בכל תור משה מטיל מטבע חוקית (הסתברות חצי/חצי לעץ/פלי) אבל לפני שהוא אומר להם את התוצאה אבי ואריה צריכים להגיד ביחד (בבת אחד, במקביל) את הניחוש שלהם. אם שניהם צודקים הם נצחו, אם לא, הפסידו.
משחק זה חוזר על עצמו הרבה פעמים, ומטרת אבי ואריה למצוא אסטרטגיה שתביא למקסימום את מספר הסיבובים שהם מנצחים.
עד כה, ברור שהם יכולים להגיע ל-50 אחוז (למשל ע"י זה שהם מראש יסכימו בינהם לצעוק "עץ" כל הזמן),. וברור שהם לא יכולים לעשות יותר טוב מזה.
כעת, נודע להם, שאמיר (שיודע מראש את התוצאות של כל הטלות המטבע), יגיד לאריה, שנייה לפני שהמשחק יתחיל, את התוצאות של כל ההטלות. כעת, חמושים בידע הזה (שאמיר ידבר עם אריה), אבי ואריה יכולים לתכנן אסטרטגיה יותר טובה מלצעוק "עץ". כמובן, שאחרי שאמיר אומר לאריה את תוצאות ההטלות, ןהמשחק יתחיל אין כל קומוניקציה בין אריה לאבי (חוץ מזה שהם מכריזים על הניחוש שלהם בכל תור).
האם תוכלו לעזור לאבי אריה לתכנן אסטרטגיה בה ינצחו ביותר מ-70 אחוז מהסיבובים?
credit
את החידה הזאת, כמו רבות לאחרונה, אני לוקח משני ספרי חידות מעולים שקניתי בנסיעה האחרונה שלי לאמריקה (של Peter Winkler) רוב רובן של החידות שם הוא קשה מדי לדעתי (ונלקחו מכל מיני אולימפידות במטמתיקה...), אבל חלקן, אלה שאני מפרסם, "סתם" קשות.
בכל תור משה מטיל מטבע חוקית (הסתברות חצי/חצי לעץ/פלי) אבל לפני שהוא אומר להם את התוצאה אבי ואריה צריכים להגיד ביחד (בבת אחד, במקביל) את הניחוש שלהם. אם שניהם צודקים הם נצחו, אם לא, הפסידו.
משחק זה חוזר על עצמו הרבה פעמים, ומטרת אבי ואריה למצוא אסטרטגיה שתביא למקסימום את מספר הסיבובים שהם מנצחים.
עד כה, ברור שהם יכולים להגיע ל-50 אחוז (למשל ע"י זה שהם מראש יסכימו בינהם לצעוק "עץ" כל הזמן),. וברור שהם לא יכולים לעשות יותר טוב מזה.
כעת, נודע להם, שאמיר (שיודע מראש את התוצאות של כל הטלות המטבע), יגיד לאריה, שנייה לפני שהמשחק יתחיל, את התוצאות של כל ההטלות. כעת, חמושים בידע הזה (שאמיר ידבר עם אריה), אבי ואריה יכולים לתכנן אסטרטגיה יותר טובה מלצעוק "עץ". כמובן, שאחרי שאמיר אומר לאריה את תוצאות ההטלות, ןהמשחק יתחיל אין כל קומוניקציה בין אריה לאבי (חוץ מזה שהם מכריזים על הניחוש שלהם בכל תור).
האם תוכלו לעזור לאבי אריה לתכנן אסטרטגיה בה ינצחו ביותר מ-70 אחוז מהסיבובים?
credit
את החידה הזאת, כמו רבות לאחרונה, אני לוקח משני ספרי חידות מעולים שקניתי בנסיעה האחרונה שלי לאמריקה (של Peter Winkler) רוב רובן של החידות שם הוא קשה מדי לדעתי (ונלקחו מכל מיני אולימפידות במטמתיקה...), אבל חלקן, אלה שאני מפרסם, "סתם" קשות.
אמיר.
ההטלות הם חוקיות (מטבע נורמאלית) - ואכן השאלה היא על תוחלת.moco כתב:אתה מתכוון בתוחלת (כמו ה50% הקודם) או ב worst case (שזה 0% במקרה הקודם) ?
יש לי 75% בתוחלת ו50% worst case ....
תמשיך לעבוד על זה עד שתגיע ל-70%
אמיר.
"חידה" נוספת בזמן שאתם חושבים על הנוכחית - פתרונות לפרטי
בארץ רחוקה (אך מחוברת לאינטרנט), יש בחור שהיה רוצה למצוא סרטי HD, וסדרות למינהן.
האם תוכלו לעזור לו במשימתו ? האם אפשר בצורה חינמית? (לבחור יש bit-torrent client)
ושוב - פתרונות לפרטי בלבד
בארץ רחוקה (אך מחוברת לאינטרנט), יש בחור שהיה רוצה למצוא סרטי HD, וסדרות למינהן.
האם תוכלו לעזור לו במשימתו ? האם אפשר בצורה חינמית? (לבחור יש bit-torrent client)
ושוב - פתרונות לפרטי בלבד
אמיר.
