חידה

[טיקטי]

חידה

יש לכם שאלון עים n שאלות ולכל שאלה יש k אפשרויות אתה יכול למלא את השאלון כמה שאתה רוצה וכל פעם שאתה ממלא את השאלון אומרים לך בכמה שאלות צדקת כמה ניסיונות אתה צריך כדי לדעת את כל התשובות הנכונות עמרי

 

[Mahaoo]

לא ממש פתרון

אפשר בעזרת n*k נסיונות לדעת בטוח(לסמן כל פעם רק תשובה אחת אם לא נכון אז עוברים לתשובה הבאה וככה עד k נסיונות ולכל שאלה לעשות אותו דבר אז הפתרון בטוח יהיה n*k או פחות) אפשר גם לדעת כמה א' כמה ב' כמה ג' .... עד כמה k' יהיו בעזרת רק k ניסיונות(לסמן רק א' לבדוק כמה תשובות נכונות אחרי כן לסמן רק ב' ולבדוק שוב וככה עד k)

 

[טיקטי]

ככה גם אני פתרתי אבל מי שנתן לי את

החידה אמר שאפשר לדעת בטוח כאשר n שווה 98 וk שווה 4 רק ב1200 ניסיונות שזה הרבה יותר מn*k שזה 392 אז אים מישהו מסכים אים ה 1200 בבקשה תסביר/י למה עמרי

 

[snogal]

כי זה לא n*k

אלא k^n לכל שאלה יש k אפשריות.

 

[snogal]

אבל לפי התשובה (1200)

צריך לבצע את הבדיקות בצורה משולבת. כך שיחסכו בדיקות.

 

[טיקטי]

אני לא חושב שזה n^k כי זה לא

שאתה בודק את כל המקרים אתה בעצם בודק בכל שאלה האם התשובה הנוכחית נכונה/שינתה משהו אתה לא בודק את כל האפשרויות אתה פשוט משנה את הבחירה בשאלה מסוימת מגיש את השאלון ואז עושה את זה עוד פעם כך שזה בעצם הגשת השאלון k פעמים לכל שאלה ויש n שאלות כלומר n*k

 

[טלמון סילבר]

../images/Emo13.gif קיצור דרך ראשון:

(k-1)^n​

כי אחרי k-1 נסיונות כושלים (מקסימום), כבר ברור שהתשובה מס' k נכונה. לאמיתו של דבר עוד לא ניצלנו את העובדה שבכל שאלון אנו כבר נוגעים בכל השאלות. זה מזכיר לי את המשחק "שוורים ופרות" (Bulls & Cows) עם ניחוש 4 הספָרות. כשנמאס לי לשחק עם מישהו, כאשר שנינו משחקים בערך אותו דבר, וגם אין זמן לזה, היצעתי לכולם לערוך תחרות תוכניות שישחקו ביניהן. רבים הסכימו, אבל איש לא ביצע, לא כתב את תכנית "השחקן", חוץ ממני. גם כתבתי את תכנית "השופט", המריצה מספר "שחקנים". "השופט" ממציא מספרים רנדומליים, וסופר את מספר המהלכים שלוקח לכל שחקן לנחש כל מספר, ומסכם את הסה"כ - לניטרול האפקט של המזל. אז שיכפלתי את תכנית "השחקן" מספר פעמים, והרצתי אותם זה נגד זה.

חידה: איך זה יכול להיות, ש"השחקנים" השונים, שהיו העתקים מדוייקים של אותה התכנית, הגיעו כל פעם לתוצאות שונות? פעם היה מנצח אחד מהם, ופעם אחרת "מישהו" אחר? אגב, גם היום לא ידוע לי אלגוריתם אופטימלי של המשחק.

 

[טיקטי]

היי

מישהו מוכן בבקשה להסביר לי למה זה k^n ולא n*k הרי אנחנו לא מחפשים את כל המצבים? ולחידה: השתמשת במקרה בפונקציית ראנדום? ועוד שאלה:מישהו כאן יודע את תורת הגרפים?

 

[טלמון סילבר]

אהלן

מספר האפשרויות הוא כמובן k בחזקת n: לשאלה הראשונה יש k תשובות אפשריות. גם לשאלה השנייה יש סה"כ k תשובות אפשריות. מספר אפשרויות התשובה לשתי השאלות הראשונות הוא כבר k בריבוע. מספר אפשרויות התשובה ל-3 השאלות הראשונות זה כבר k בשלישית. וכו'. מה מספר אפשרויות הטוטו? 3 בחזקת 16. אם, למשל, אני ממלא טופס טוטו בצורה הבאה: ב-13 משחקים אני כותב ניחוש אחד בלבד, וב-3 משחקים אני ממלא את כל שלוש האפשרויות, אז אני משלם פי 27 יותר, כי מילאתי למעשה 3^3 טורים! זה לא אומר שאנחנו צריכים לבדוק את כל האפשרויות הנ"ל. במקרה שלנו אפשר, למשל, להסתפק ב:

3 * 2^97​

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

נכון, כל "שחקן" מבצע מהלך ראשון רנדומלי. אם אתה מכיר את משחק השוורים והפרות, אז זה במידה לא מעטה עניין של מזל. גם בחידה שלך. הרי אפשר תאורטית כבר בניסיון הראשון לנחש הכל, או, לפחות, לפסול במכה אחת את כל הטור שמילאנו, שזה משאיר פחות אפשרויות. ואגב, יכולים להיות שני סוגי פתרון: 1. כמו ששאלתָ: מה המספר המינימלי של נסיונות שנותנים תשובה בטוחה. 2. מהו אלגוריתם החיפוש המספק צפי מתמטי מינימלי של מספר הנסיונות? את תורת הגרפים מעולם לא למדתי.

 

[טיקטי]

היי שוב../images/Emo13.gif

אים היינו מחפשים את כל האפשרויות אז זה היה k^n אבל זה לא מה שאנחנו מחפשים אנחנו בעצם כל פעם (כל הגשה של השאלון לבדיקה) משנים אפשרות אחת בשאלה אחת ומגישים שוב וככה במקרה הרע עושים k בדיקות לכל שאלה ברגע שהגענו למסקנה שהתשובה נכונה אנחנו עושים את אותו תהליך על השאלה הבאה עד שכל השאלון נכון ולכן אני חוושב שזה k*n ולא k^n וחוץ מזה אני ממליץ לכולם ללמוד את תורת הגרפים לא צריך מורה לזה רק צריך את ההגדרות וזה פשוט חידת הגיון כל שאלה אים אנשים יידעו את זה אני יכול להעלות שאלות הן מאד כיפיות ואים מישהו רוצה את ההגדרות יש לי אותם ואני אוכל לכתוב אותן עמרי

 

[טלמון סילבר]

ואללה! אתה צודק!

ניקח 98 שאלות עם 4 תשובות אפשריות לכל אחת. ניסיון ראשון: לא משנה. ניסיון שני: משנים את התשובה בשאלה הראשונה. במקרה הגרוע, מספר התשובות הנכונות לא ישתנה, ואז: ניסיון שלישי: מנסים תשובה שלישית לשאלה הראשונה, ושוב מבלי לשנות את התשובות לשאר השאלות. עכשיו יודעים לבטח מה התשובה הנכונה לשאלה הראשונה. בדרך זו, אפשר למצוא את התשובה הנכונה לכל אחת משאר השאלות, בשני נסיונות בלבד. כלומר התשובה היא 3 + 2*97 = 197 נסיונות בלבד, ולא 1200, או שמשהו לא נכון בהבנת השאלה? ובמקרה הכללי:

n(k - 2) + 1​

והערה חשובה: עוד לא הוכחנו שזה הפתרון האופטימלי!

 

[טיקטי]

היי

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

 

[Mahaoo]

ואללה נכון!!

יפה אני הלחתי להגיע רק ל n(k-1) i מחשבה ממש יפה-לא בטוח שהייתי מגיע לזה

 

[טלמון סילבר]

וכן,

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