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

עמוד

ברוכים הבאים לאתר תחרויות קודגורו! פורומים חידות כמה שאלונים צריך למלא כדי לפתור?

מוצגות 11 תגובות – 1 עד 11 (מתוך 11 סה״כ)
  • מאת
    תגובות
  • #77470
    CodeGuru
    מנהל בפורום

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

    #79577
    MoD
    משתתף

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

    #79608
    CodeGuru
    מנהל בפורום

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

    #79609
    דניאלק
    משתתף

    כותרת: צמצום לחימום…
    לא צריך לבדוק כל שאלה 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 =]

    #79610
    CodeGuru
    מנהל בפורום

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

    #79611
    דניאלק
    משתתף

    כותרת: 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. ומצאנו את הפתרון..

    #79612
    דניאלק
    משתתף

    כותרת: 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 או לא).

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

    #79613
    דניאלק
    משתתף

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

    #79621
    CodeGuru
    מנהל בפורום

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

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

    #79622
    דניאלק
    משתתף

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

    #79696
    רועי
    משתתף

    כותרת: אפשר ב- 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
    8) 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 שאלות, בדרך אחרת (נגיד לחלק לשביעיות או יותר).

מוצגות 11 תגובות – 1 עד 11 (מתוך 11 סה״כ)
  • יש להתחבר למערכת על מנת להגיב.