מסית ומדיח
New member
שאלות
ידוע מה אורך הרכבת? מהירות? כל כמה זמן אפשר לעשות דגימה? במקום אחד כל פעם?
ידוע מה אורך הרכבת? מהירות? כל כמה זמן אפשר לעשות דגימה? במקום אחד כל פעם?
שרשור חידות
- פותח הנושא vinney
- פורסם בתאריך
אני משער...
חייבים להיות כמה הנחות מוקדמות. כי אם מדובר ברכבת נעה, אז אנחנו מוכרחים לפעול במסגרת זמן מסויימת, כלומר עלינו לדעת כמה זמן לוקחת בדיקה ובאיזה מהירות הרכבת. אחרת מה הטעם בבדיקה בכלל. נניח לרגע שאנחנו יודעים באיזה מהירות פחות או יותר הרכבת נוסעת. נניח שזמן הבדיקה הוא קבוע וזניח. אם נדגום נקודות במרווחים קבועים שהם פונקציה של מהירות הרכבת. מתישהו אנחנו עלולים להיתקל בה. לא? טוב אם כי זו הדרך שבטוח תביא לתוצאות היא הדרך הפחות יעילה כי אנחנו נצטרך לבדוק אין סוף נקודות. אבל אולי עם מעט זכרון, (אני לא יודע כרגע להעריך כמה) אם נאחסן את תוצאות של כמה בדיקות אולי זה אפשרי איכשהו. יכול להיות שאפשר לפסול מראש הרבה בדיקות משום שאם למשל התקבלו שתי תוצאות סמוכות שליליות בפרק הזמן שלוקח לרכבת לעבור מנקודה לנקודה. אז אנחנו יכולים להניח אחת מן השתיים או שהיא עוד לא הגיעה לנקודה הנמוכה יותר או שהיא כבר עברה את הנקודות הללו, לא?. כנ"ל לגבי קבוצות גדולות יותר של נקודות סמוכות. טוב אני רק חושב בקול... צריך לחשוב על זה...
חייבים להיות כמה הנחות מוקדמות. כי אם מדובר ברכבת נעה, אז אנחנו מוכרחים לפעול במסגרת זמן מסויימת, כלומר עלינו לדעת כמה זמן לוקחת בדיקה ובאיזה מהירות הרכבת. אחרת מה הטעם בבדיקה בכלל. נניח לרגע שאנחנו יודעים באיזה מהירות פחות או יותר הרכבת נוסעת. נניח שזמן הבדיקה הוא קבוע וזניח. אם נדגום נקודות במרווחים קבועים שהם פונקציה של מהירות הרכבת. מתישהו אנחנו עלולים להיתקל בה. לא? טוב אם כי זו הדרך שבטוח תביא לתוצאות היא הדרך הפחות יעילה כי אנחנו נצטרך לבדוק אין סוף נקודות. אבל אולי עם מעט זכרון, (אני לא יודע כרגע להעריך כמה) אם נאחסן את תוצאות של כמה בדיקות אולי זה אפשרי איכשהו. יכול להיות שאפשר לפסול מראש הרבה בדיקות משום שאם למשל התקבלו שתי תוצאות סמוכות שליליות בפרק הזמן שלוקח לרכבת לעבור מנקודה לנקודה. אז אנחנו יכולים להניח אחת מן השתיים או שהיא עוד לא הגיעה לנקודה הנמוכה יותר או שהיא כבר עברה את הנקודות הללו, לא?. כנ"ל לגבי קבוצות גדולות יותר של נקודות סמוכות. טוב אני רק חושב בקול... צריך לחשוב על זה...
לפי דעתי
תחת ההנחות הבאות: - אורך הרכבת 2 יחידות לפחות (אחרת למה לקרוא לזה "רכבת") - הרכבת נעה צעד אחד בכל תור הפתרון הוא: להתחיל מ-0 (או כל נקודה שרירותית אחרת), ולבדוק כך: ...,0,3,0,6,0,9,0,12,0,15 הוכחה: אם ברגע ההתחלה הרכבת כבר בצד החיובי, אז אנחנו רודפים אחריה. כיוון שאנו מתקדמים ימינה מהר יותר מהרכבת (3 יחידות ב-2 תורות) אנו בהכרח נשיג אותה בסוף. אם ברגע ההתחלה היא בשליליים, אז כשהיא תגיע ל-0 אנחנו נתפוס אותה. הניואנס היחיד הוא לבדוק שאין מצב שהרכבת לימיננו ואנחנו מדלגים מעליה ומפספסים אותה, וזה אכן לא יכול לקרות וקל לבדוק את זה.
תחת ההנחות הבאות: - אורך הרכבת 2 יחידות לפחות (אחרת למה לקרוא לזה "רכבת") - הרכבת נעה צעד אחד בכל תור הפתרון הוא: להתחיל מ-0 (או כל נקודה שרירותית אחרת), ולבדוק כך: ...,0,3,0,6,0,9,0,12,0,15 הוכחה: אם ברגע ההתחלה הרכבת כבר בצד החיובי, אז אנחנו רודפים אחריה. כיוון שאנו מתקדמים ימינה מהר יותר מהרכבת (3 יחידות ב-2 תורות) אנו בהכרח נשיג אותה בסוף. אם ברגע ההתחלה היא בשליליים, אז כשהיא תגיע ל-0 אנחנו נתפוס אותה. הניואנס היחיד הוא לבדוק שאין מצב שהרכבת לימיננו ואנחנו מדלגים מעליה ומפספסים אותה, וזה אכן לא יכול לקרות וקל לבדוק את זה.
אם נדע את המהירות של הרכבת,
נוכל לדגום את ה"מרחב" בצורה כזו, למשל: x, 1+x, -1+x, 2+x, ...ZZZ כאשר בכל נקודה x=vt. כלומר x הוא ה"היסט" של הרכבת מנקודת ה"התחלה" (שהיא נקודה כלשהי על הציר), או המרחק שלה, או משהו כזה. בקיצור, בעצם יצרנו "רדוקציה" לבעיה של מציאת משבצת (פחות או יותר) במכונת טיורינג שבה יש ערך מסויים, ואת זה אנחנו כבר יודעים לפתור, בקלות. אם לא נדע את המהירות של הרכבת, אני מניח שנוכל לאלתר משהו. (1 בתשובה מציין את אורך הרכבת, שגם אותו הנחתי שאנחנו יודעים. ואחרת, אני מניח שגם כאן אפשר לעשות את אותו הדבר) דוגמא לאלתור יכולה להיות, לנסות פשוט את כל האורכים האפשריים, ואת כל המהירויות האפשריות, על כל הסרט האפשרי, בו"ז (כלומר, בסידור כלשהו שלהם בדרך הקודמת). ועכשיו, בחזרה לממ"ן
נוכל לדגום את ה"מרחב" בצורה כזו, למשל: x, 1+x, -1+x, 2+x, ...ZZZ כאשר בכל נקודה x=vt. כלומר x הוא ה"היסט" של הרכבת מנקודת ה"התחלה" (שהיא נקודה כלשהי על הציר), או המרחק שלה, או משהו כזה. בקיצור, בעצם יצרנו "רדוקציה" לבעיה של מציאת משבצת (פחות או יותר) במכונת טיורינג שבה יש ערך מסויים, ואת זה אנחנו כבר יודעים לפתור, בקלות. אם לא נדע את המהירות של הרכבת, אני מניח שנוכל לאלתר משהו. (1 בתשובה מציין את אורך הרכבת, שגם אותו הנחתי שאנחנו יודעים. ואחרת, אני מניח שגם כאן אפשר לעשות את אותו הדבר) דוגמא לאלתור יכולה להיות, לנסות פשוט את כל האורכים האפשריים, ואת כל המהירויות האפשריות, על כל הסרט האפשרי, בו"ז (כלומר, בסידור כלשהו שלהם בדרך הקודמת). ועכשיו, בחזרה לממ"ן
חידה
נתונות 999 כוסות יין וכוס אחת עם רעל שנראה זהה ליין שבשאר הכוסות. מולקולה אחת מהרעל מספיקה כדי להרוג מיד בן אדם (כך שאם מעבירים כמות מזערית של רעל לכוס עם יין, מי שילגום ממנה ימות מיד). נתונים עשרה עבדים שישתו מהכוסות. כל אחת ילגום רק פעם אחת וכולם ילגמו בו זמנית. צריך להציע דרך שבה עשרת העבדים ילגמו מהכוסות בו זמנית וכל אחד רק מכוס אחת, חלקם או כולם ימותו מיד ולפי מי שמת ומי שנותר בחיים נדע באיזה כוס היה הרעל בהתחלה. מותר להעביר טיפות מכל כוס לכל כוס כמה שרוצים. אם מישהו לא בטוח למה הכוונה מההסבר שלי, אז אני אשמח להסביר. אמנם נתקלתי במעט מאוד חידות, אבל החידה הזו (או יותר נכון הפתרון שראיתי) היא היפה ביותר שראיתי עד כה. למי שיש רעיון שיזכור לשים
בכותרת. בהצלחה.
נתונות 999 כוסות יין וכוס אחת עם רעל שנראה זהה ליין שבשאר הכוסות. מולקולה אחת מהרעל מספיקה כדי להרוג מיד בן אדם (כך שאם מעבירים כמות מזערית של רעל לכוס עם יין, מי שילגום ממנה ימות מיד). נתונים עשרה עבדים שישתו מהכוסות. כל אחת ילגום רק פעם אחת וכולם ילגמו בו זמנית. צריך להציע דרך שבה עשרת העבדים ילגמו מהכוסות בו זמנית וכל אחד רק מכוס אחת, חלקם או כולם ימותו מיד ולפי מי שמת ומי שנותר בחיים נדע באיזה כוס היה הרעל בהתחלה. מותר להעביר טיפות מכל כוס לכל כוס כמה שרוצים. אם מישהו לא בטוח למה הכוונה מההסבר שלי, אז אני אשמח להסביר. אמנם נתקלתי במעט מאוד חידות, אבל החידה הזו (או יותר נכון הפתרון שראיתי) היא היפה ביותר שראיתי עד כה. למי שיש רעיון שיזכור לשים
אאל"ט, פתרון ../images/Emo58.gif
בעזרת 10 אנשים שיש להם שני מצבים (מת או חי) אתה יכול לייצג 1024 מספרים (2^10). נבחר 10 כוסות ראשונות שהאנשים ישתו מהן. יכול להיות שכוס הרעל נמצאת באחת מהן, ואז ימות איש אחד ונדע איפה הרעל. מכל שאר 989 הכוסות נשפוך קצת אל 10 הכוסות הראשונות, לפי הייצוג הבינארי של כל כוס. לדוגמה, כוס מס 13 מיוצגת כך: 0000001101 כך שנשפוך ממנה קצת אל הכוס מס' 1, 3 ו4. אם נגלה שלושת האנשים האלו מתו, נדע שכוס הרעל בכוס מס' 13. נמספר את החזקות של 2 שנותרו למספרים אחרי 999 בשביל שנוכל להבחין בין אלה לכוס רעל בכוסות המקוריות. אם יש לך כסף עשר כוסות נוספות זה יהיה קצת יותר פשוט...
בעזרת 10 אנשים שיש להם שני מצבים (מת או חי) אתה יכול לייצג 1024 מספרים (2^10). נבחר 10 כוסות ראשונות שהאנשים ישתו מהן. יכול להיות שכוס הרעל נמצאת באחת מהן, ואז ימות איש אחד ונדע איפה הרעל. מכל שאר 989 הכוסות נשפוך קצת אל 10 הכוסות הראשונות, לפי הייצוג הבינארי של כל כוס. לדוגמה, כוס מס 13 מיוצגת כך: 0000001101 כך שנשפוך ממנה קצת אל הכוס מס' 1, 3 ו4. אם נגלה שלושת האנשים האלו מתו, נדע שכוס הרעל בכוס מס' 13. נמספר את החזקות של 2 שנותרו למספרים אחרי 999 בשביל שנוכל להבחין בין אלה לכוס רעל בכוסות המקוריות. אם יש לך כסף עשר כוסות נוספות זה יהיה קצת יותר פשוט...
שים לב
הייצוג הבינארי של 16 הוא :
הייצוג הבינארי של 16 הוא :
0000010000
אז מעבירים טיפת נוזל מהכוס שממוספרת 16 אל הכוס שממוספרת 5. נניח שהעבד ששתה מהכוס החמישית מת ורק העבד ששתה מהכוס החמישית מת, אז יכול להיות שהרעל היה בכוס מספר 16, ויכול להיות שהוא היה בכוס מספר 5. משום כך נמחק את המספר 16 שכתוב על כוס מספר 16 ונרשום במקום 1006 למשל ואז נעביר טיפות מהכוס לפי המספר 1006. כך נמספר מחדש את כל המספרים שהם חזקות של 2 (2,4,8,16,32,...), כל אחד במספר שונה מעל 1000. כך נימנע מהמצב שתיארתי.Copyright©1996-2021,Tapuz Media Ltd. Forum software by XenForo® © 2010-2020 XenForo Ltd.