חידות כי הגיע הזמן

[נופרבלע]

אלגוריתם.

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

 

[vinney]

חידות../images/Emo70.gif כי הגיע הזמן ../images/Emo70.gif

 

[johnny d]

חידה

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

 

[Fingertip]

לא קשה...

נבנה שתי סדרות. אחת באורך 4 ואחת באורך 3 בצורה הבאה: נעשה חיפוש בינארי על הקבוצה, כלומר, נחלק ל-2, נבדוק קרינה שרירותית באחת הקבוצות ונעבור לזו עם הקרינה. לשם כך נשתמש בסדרה באורך 4. השימוש בסדרה באורך 3 יהיה כדלהלן: בכל פעם שהבדיקה שלנו הראתה קרינה, נסמן את הקבוצה השנייה כאבר בסדרה באורך 3, חוץ מהבדיקה האחרונה. כעת, בחיפוש הבינארי יש 4 שלבים, ובסופם מצאנו כדור אחד. כעת עלינו למצוא את הכדור השני. איפה הוא יכול להסתתר? ובכן, בכל פעם שמדדנו ומצאנו קרינה, בחרנו שרירותית באחת הקבוצות. ייתכן שאם היינו מודדים את הקבוצה השנייה גם היינו מוצאים קרינה. לכן נתחיל לעבור על הסדרה של ה-3 ולחפש קרינה. אם מצאנו באחד השלבים, אזי (תספרו ותראו) ישארו לנו מספיק בדיקות בשביל לחפש בינארית את הכדור השני. אם לא מצאנו באף אחד מהשלבים, אזי האפשרות היחידה היא שהכדור השני היה בקבוצה הנבדקת על השלב האחרון, ושם הפרדנו בין שני הכדורים, ולכן הכדור המוקרן הוא הכדור הלפני אחרון. אהד.

 

[johnny d]

לא הבנתי,

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

 

[ron369]

מותר אחת במתמ'? ../images/Emo13.gif

הנה אחת נחמדה. נתקלתי בה לא מזמן, ולצערי הפתרון... חמק ממני, בינתיים. כידוע [לפחות, אחרי משפט זה], בהנתן מספר N, המיוצג כספרות בבסיס עשרוני, ניתן להופכו לפלינדרום ע"י התהליך הבא. נניח של-N ישנן בדיוק n ספרות. אם n זוגי, הוסף לכל ספרה במיקום ה-i את הספרה במיקום ה-n-i. אם n אי-זוגי, הוסף לכל ספרה במיקום ה-i (בחצי הראשון של המספר), את הספרה במיקום ה- ZZZ (n+1)-i. ואז חזור על התהליך עד שיתקבל פלינדרום. (זה פשוט מאיך שזה נראה, לדעתי) למשל, עבור 123: 123 + 321 -> 444. פלינדרום. 8954 + 4598 -> 13552 + 25531 -> 39083 + 38093 -> 77176 + ... -> 4888884. פלינדרום, תודה לאל. האם אפשר לייעל את התהליך, ולהפוך מספר לפלינדרום בדרך הזו, בצורה מהירה יותר? האם עדיין נוכל לדעת מה היה צריך להיות מספר הצעדים, בדרך הישנה?

 

[ron369]

(זה במחשבים, צחקתי בקשר למתמ')

 

[עריסטו]

לא בטוח שהבנתי את התהליך

האם תוכל להראות איך מגיעים מ - 196 לפלינדרום?

 

[ron369]

כן, כמובן

196 -> 196+691 = 887 -> 887+788 = 1675 (אני פשוט ארשום מעכשיו את המספרים הבאים בסדרה), 7436, 13783, 52514, 94039, 187088, 1442045, 6844486.

 

[עריסטו]

איך הגעת מ - 187088 ל - 1442045?

 

[ron369]

טעות חישוב, לעזאזל

הבנת אבל את הרעיון, לא?

 

[עריסטו]

הבנתי. שאלתי בגלל שהמספר 196

לא מוביל לפלינדרום, ולכן חשבתי שאולי התכוונת לתהליך אחר.

 

[ron369]

כן, *אנחה*, חשבתי שלכך התכוונת

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

)

 

[עריסטו]

חידת משחק

שני שחקנים משחקים במשחק הבא. יש מספר ערימות של אגוזים. שני השחקנים יודעים את מספר האגוזים בכל ערימה. כל שחקן בתורו לוקח n אגוזים מערימה כלשהי, כאשר n חייב להיות 1 או מספר ראשוני. מי שלוקח את האגוז האחרון הוא המנצח. מהי אסטרטגיית הנצחון? (למי שמכיר - זהו פשוט המשחק Nim, בתוספת התנאי שמספר האגוזים שלוקחים בכל צעד חייב להיות ראשוני או 1). צריך למצוא אלגוריתם יעיל, שיאפשר, למשל, למחשב למצוא את הצעד הזוכה (אם יש כזה) תוך פחות משנייה, במקרה שיש, לדוגמה, 100 ערימות שבכל אחת מהן פחות מ - 100 אגוזים.

 

[ron369]

שמעתי על NIM. עוזר לדעת אותה?

(אולי ידעתי ושכחתי)

 

[עריסטו]

עוזר.

 

[carlos22]

חלק מהאסטרגיה

היא אם להתחיל ראשון או שני ? או אלגוריתם שיתאים לשני המקרים ? נראה לי שיש מקרים שבהם לשחקן הראשון אבוד מראש. לדוג' 4 ערימות של 4 אגוזים (אם לא פספסתי פה משהו).

 

[עריסטו]

ברור שיש מקרים בהם הראשון אבוד

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

 

[neko]

להיפך - בד"כ הראשון מנצח

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

 

[עריסטו]

חידה - אלגוריתם לשברים

מיצאו אלגוריתם בעל סיבוכיות זכרון O(1) וסיבוכיות זמן O(n^2) המבצע את הפעולה הבאה: מקבל מספר טבעי n, ומדפיס את כל השברים המצומצמים בין 0 ל - 1 שהמכנה שלהם הוא לכל היותר n, בסדר עולה. למשל אם הקלט הוא 4 הפלט הוא:

0/1 1/4 1/3 1/2 2/3 3/4 1/1​