כמה שאלונים צריך למלא כדי לפתור?

[CodeGuru]

בהנתן שאלון של N שאלות (למשל 98) שלכל אחת מהן יש K (נניח ארבע) תשובות אפשריות, כמה פעמים צריך למלא את השאלון ולקבל ציון כדי לדעת את כל התשובות הנכונות?
נסו לתת חסמים תחתונים ועליונים. למשל:
1) אפשר לפתור שאלון של חמש שאלות של שתי תשובות אפשריות (כן/לא) על ידי מילויו ארבע פעמים בלבד (איך?)
2) אפשר לפתור שאלון של שתי שאלות של ארבע תשובות אפשריות על ידי מילויו ארבע פעמים בלבד (איך?)
3) מצד שני, אפשר להוכיח שאי אפשר להבטיח פתרון מלא של שאלון בעל עשר שאלות עם חמש תשובות אפשריות לכל שאלה בפחות מתשע נסיונות (נסו להוכיח)

[MoD]

כותרת: חיחי… ממש חיכיתי שתגיע השאלה בנושא )

[CodeGuru]

כותרת: תחרות. מתחילים ב (1,400)
למאה שאלות, עם ארבע תשובות אפשריות לכל אחת, כדי לפתור את השאלון צריך לפחות לשלוח פעם אחת (טריוויאלי להוכיח), ואפשר לפתור עם 400 שליחות (קל למדי).
נסו לשפר לפחות את אחד החסמים.

[דניאלק]

כותרת: צמצום לחימום…
לא צריך לבדוק כל שאלה 4 פעמים, אפשר להסיק תוך 3(במידה ו3 הראשונות לא נכונות, הרביעית בהכרח נכונה) – צמצמנו ל300.

צמצום קצת יותר טוב:
מ400 שליחות ל200 – על ידי מציאת התשובות לכל זוג בנפרד:
נחלק את זה לשני מקרים: 1. שתי השאלות עם מספר תשובה זהה, 2. מספר התשובה שונה.
1. נבדוק כל תשובה בנפרד: 11, 22, 33. נקבל 0 אם זה לא הזוג, 2 אם זה כן(אם קיבלנו 0 ב3 השאלות הראשונות, התשובות היא 44 מן הסתם).

2. מתחילים בשיטה הקודמת, עד שנתקלים במצב שרק תשובה אחת נכונה,
ומשם משנים רק את אחד מהתשובות – קודם כדי לברר איזה מן התשובות היא הנכונה, ואח"כ לגלות מה הערך של התשובה השניה:
אפשר לחלק את זה ל3 תתי מצבים:
* 1 התשובות היא 1: במצב זה נקבל תשובה של 1 כבר על ההתחלה. נבדוק 12 – ולפי זה נקבע אם השמאלי או הימני הוא 1. לאחר מכן נבדוק 21 ואז 31(במקרה והתשובה 12 היא 0, אם היא 1 – צריך לבדוק רק 13) כדי לבדוק מה התשובה השניה (4 שאלות)
* 1 התשובות היא 2: במצב זה נקבל תשובה של 1 אחרי 2 שאלות, נשאר רק לבדוק מי הנכונה(בדיקה של 23), ואז בדיקה של 24 או 32.
* 1 התשובות היא 3: אחרי 3 בדיקות, צריך לבדוק רק אם זה 34 או 43.

בקיצור – 4 בדיקות המפיקות 2 תשובות. או 4*50 בדיקות, המפיקות 2*50 תשובות.

Let the games begin =]

[CodeGuru]

כותרת: שתי הערות לגבי (1,200)
הפתרון נכון, אבל:
א. איך אפשר להשיג תוצאה דומה אם חייבים להגדיר את כל השאלונים מראש (ולא לבחור איך למלא שאלון מסוים כתלות בתוצרי שאלונים קודמים)?
ב. ומה אם אסור למלא שאלון חלקי (צריך לתת תשובה לכל שאלה)?

[דניאלק]

כותרת: 1,200, שאלונים קבועים(אך עם תשובות לכל זוג בנפרד)
עוד חושב על איך לעשות את כל השאלון בבת אחת…

נבחר את הרצף:
11
12
23
33

קל לראות שכל אפשרות לפתרון תתן תשובות שונות(כאשר ? = לא רלוונטי, כי ברגע שקיבלנו 2, אנחנו יודעים מה הפתרון)
11 – 2???
12 – ?2??
13 – 1111
14 – 1100
21 – 1010
22 – 0110
23 – ??2?
24 – 0010
31 – 1001
32 – 0101
33 – ???2
34 – 0001
41 – 1000
42 – 0100
43 – 0011
44 – 0000

או לפי הסדר של התשובות(למי שרוצה לוודא שאין כפילויות:)
11 – 2???
12 – ?2??
23 – ??2?
33 – ???2
44 – 0000
34 – 0001
24 – 0010
43 – 0011
42 – 0100
32 – 0101
22 – 0110
41 – 1000
31 – 1001
21 – 1010
14 – 1100
13 – 1111

איך בודקים את זה בלי טבלת אמת?
על ידי השוואה בין התשובות, וההבדלים ביניהם.
על ידי השוואה בין התשובה הראשונה לשניה, אפשר לדעת האם הספרה הימנית היא 1 או 2, או האם הספרה השמאלית היא 1.(רצף של 11 או 10/01).
על ידי השוואה בין התשובה השלישית לרביעית, אפשר לדעת האם הספרה הימנית היא 3, או אם השמאלית היא 2 או 3(לפי רצפים של 11, 10, 01)
ומן הסתם, אם הספרה הימנית היא לא 1 לא 2 ולא 3, היא חייבת להיות 4
כנ"ל לגבי הספרה השמאלית…

הדגמה:
נניח שהרצף הוא 24.
11 – יחזיר 0.
12 יחזיר 0.
23 יחזיר 1
33 יחזיר 0.

ההשוואה בין 2 התשובות הראשונות לא תתן לנו מידע משמעותי, מלבד העובדה שהספרה הימנית איננה 1 או 2, והשמאלית איננה 1.
השוואה בין השלישת לרביעית תראה שהספרה הימנית איננה 3(ולכן חייבת להיות 4), והספרה השמאלית חייבת להיות 2. ומצאנו את הפתרון..

[דניאלק]

כותרת: 1,200 – שאלונים קבועים ותשובה לכל שאלה…
מתחילים משני כיוונים:
מלמעלה: …1111111
מלמטה: 333333…

כאשר יורדים למטה, מהאחדות, מחליפים אחד אחד את התשובות מ1 ל2:
111111
111112
111122
111222
וכו´…
כאשר עולים למעלה – מחליפים תשובות מ3 ל2:
222333
223333
233333
333333
כאשר אין צורך לבדוק את המצב של הכל 2(נקודת המפגש).

השוואה בין 2 הנסיונות שבהם מתחלפת ספרה בודדת מa לb, יכולה להניב 3 אופציות:
1. מספר התשובות הנכונות גדל – הספרה במיקום המדובר הינה b
2. מספר התשובות הנכונות קטן – הספרה במיקום המדובר הינה a
3. מספר התשובות הנכונות נשאר אותו הדבר – הספרה איננה a ואיננה b

3 אופציות אלה מאפשרים לנו לגלות בקלות יחסית את ערכה של ספרה כלשהיא שאיננה אחד מהספרות בקצוות(יש התחלפות מ1 ל2, ומ2 ל3, או שנגלה שזה 1 2 או 3, או שנגלה שזה אף אחד מהם)

הספרות בקצוות דורשות קצת יותר התחכמות:
*** תחילה, על ידי השוואה בין הנסיון הראשון לשני, והאחרון לזה שלפניו, ניתן לגלות את המצבים הבאים:
השמאלית היא 3 או 2(או לפסול את שניהם)
הימנית היא 1 או 2(או לפסול את שניהם) ***
לאחר מכן, נבנה תמונה שלמה של כל הספרות מלבדן
?123124122341?
נספור את מספר האחדות, ואת מספר השלשות, ונשווה למספר התשובות בבדיקה הראשונה ולמספר התשובות בבדיקה האחרונה. אם יש הפרשים של 2 – שתי הקיצוניות הן או 1 או 3.
אם אין הפרשים – שתי הקיצוניות הן 4.
אם יש הפרש של 1 גם בשלשות וגם באחדות – אחת מהספרות היא 1, והשניה היא 3, ונחליט על המיקום שלהן, לפי הבדיקה שצוינה ב***.
אם יש הפרש של 1 רק באחדות(או בשלשות) – אחת מהספרות היא 4, והשניה 1(או 3), ונחליט איזה מן הספרות היא ה4 על פי הבדיקה שצוינה ב***.
למשל:
?…?
וגילינו שיש +1 לטובת השלשות.
באמצעות הבדיקה שסומנה ב***, ניתן לקבוע אם השמאלית היא 3 או לא(ותוך כדי, לקבוע אם הימנית היא 4 או לא).

טוב, מקווה שההסבר לא היה מסובך מדי, רוב הסיכויים שכן, אולי אני אכתוב תוכנה להמחיש את זה…

[דניאלק]

כותרת: חבל שאין פה אפשרויות עריכה…
"אם אין הפרשים, 2 הקיצוניות הן 4" – הן חייבות להיות 4, שכן אם הן היו 2, היינו עולים על זה שוב פעם, לפי הבדיקה שצוינה ב***.
(הייתי צריך לתת לזה איזה שם בומבאסטי, אבל אני לא אוהב להמציא מונחים).

[CodeGuru]

כותרת: אפשר לרדת מ200? הוכחה שצריך לפחות 3
אם לא נמלא שלושה שאלונים – יהיו לפחות שתי תשובות אפשריות לשאלה הראשונה שלא נמלא. לכן לא נוכל להבחין בינהן אם אחת מהן נכונה.

אפשר לשפר?
את החסם העליון (האם אפשר בפחות ב 200)?
את החסם התחתון (האם ניתן להוכיח שצריך לפחות מארבע שאלות)?

[דניאלק]

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

[רועי]

כותרת: אפשר ב- 137
אפילו נניח שהיו 102 שאלות. נחלק אותן ל- 17 שישיות. נמצא דרך לפתור 6 שאלות בעזרת 9 שאלונים.

השאלונים:

1) 1 1 1 1 1 1
2) 2 2 2 2 2 2
3) 3 3 3 3 3 3
4) 4 4 4 3 2 1
5) 4 3 1 2 4 2
6) 3 1 4 4 2 2
7) 4 1 4 1 3 2
3 2 4 1 4 4
9) 2 2 2 3 1 1

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

אז מה עושים?
א) ממלאים שאלון עם הכל 1
ב) לכל שישית שאלות, ממלאים שאלון עם אחת האפשרויות 2-9 בשישיה ו- 1 בשאר

סך הכל 137 שאלונים.

לכל שישיה יש לנו את 9 השאלונים שרצינו, בהוספת בונוס לא ידוע שזה הציון על שאר המבחן (כשממלאים בו 1).

אגב, 9 שאלונים זה חסם תחתון עבור 6 שאלות. אבל בטוח שאפשר פחות מ- 137 שאלונים ל- 100 שאלות, בדרך אחרת (נגיד לחלק לשביעיות או יותר).

[מאת]

תגובות