חידה

[AltElAntE]

חידה

אפשר לקבל איזו חידה קשה לפיתרון, משהו שעליי לשבת שעות ולנסות לפתור?

 

[איגור קרסיק]

הייתה בפורום לפני זמן מה

נכון או לא נכון? נתון מספר שלם חיובי N אשר אינו מתחלק ב- 2 ואינו מתחלק ב- 5. ישנו מספר שהוא כפולה של N שצורתו 111...111 הצדק או הפרך.

 

[yatir]

דרך אגב, יש לי פתרון שונה לחידה

הזאת ממה שפורסם. גם פתרון מאוד יפה

 

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

וגם כזה קצר?

 

[yatir]

כן.

 

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

קדימה! למה אתה מחכה?

 

[yatir]

לא רציתי להרוס לAltElAntE, אבל

הוא לא נראה כל כך פעיל בשאלה שלו

, אז בסדר הנה זה: צריך לדעת קצת תורת המספרים...

10^phi=1 (mod n) because gcd(10,n)=1 it means that: 10^phi-1=nk multiply both sides by 10...010...010...01/9 and there is your answer. The number of zeros between each ´1´ in the string above is [the number of digits of 10^phi-1]-1. See why it works?​

 

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

לצערי אינני מבין את המונחים.

 

[yatir]

אני אסביר:

(phi(n נותנת את מספר המספרים מתחת ל-n שזרים ל-n. יש משפט שאומר שאם a זר ל-n אז a בחזקת (phi(n פחות אחד מתחלק ב-n.

 

[איגור קרסיק]

אגב

phi מכונה גם פונקצית אוילר. והמשפט שבו השתמשת נקרא המשפט הקטן של פרמה.

 

[yatir]

המשפט הקטן של פרמה, הוא במקרה

שn הוא ראשוני. מה שאויילר הוכיח זה ההרחבה לכל n

 

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

טוב. אבל הפתרון של איגור יותר פשוט.

אגב, לאן נעלם נשר?

 

[pallidfool]

הנה אחת טובה ../images/Emo13.gif

יש לך בניין עם p קומות. יש לך n ביצים. אתה יכול לזרוק ביצים מהבניין... אם ביצה נשברת, נניח, בקומה 20, היא תשבר בכל קומה מעליה גם. אם ביצה לא נשברת, נניח, בקומה 10, היא לא תשבר בכל קומה מתחת לה. אם ביצה אחת נשברת מקומה כלשהי, כמובן שגם כל האחרות, כלומר הביצים זהות. עליך למצוא את הדרך האופטימלית בה תזרוק את הביצים (מקומות שונות, אם יקרו תנאים כאלה וכאלה) כדי שתוכל, בסיום התהליך, לענות לי על השאלה: "האם מהקומה הככה וככה ביצה נשברת?" אפתור עבור n=1, שזהו מקרה פשוט. אם נתחיל לזרוק מקומה גדולה מ-1, הביצה עלולה להשבר. במקרה כזה, לא נוכל לבדוק מה קורה בקומות מתחת לה, ולא נצליח. לכן עלינו להתחיל מ-1, 2, וכו´. כלומר, מספר הזריקות המינימלי שאנחנו יכולים להבטיח הוא p. פתור עבור שתי ביצים, n=2 ו-p=100, כלומר מאה קומות. התשובה לכאן היא התהליך שתבצע ומספר הזריקות שתסתפק בהן. במקרה זה אתה יכול להרשות לעצמך לשבור ביצה אחת ועדין לא לסיים את התהליך, ולכן תוכל לעשות זאת בפחות זריקות. פתור עבור n=3 ומאה קומות. התשובה לכאן היא התהליך שתבצע ומספר הזריקות שתסתפק בהן. הכלל עבור כל n וכל מספר של קומות. התשובה לכאן היא התהליך שתבצע וביטוי עבור מספר הזריקות שתסתפק בהן שתלוי במספר הקומות ובמספר הביצים. פתור עבור אינסוף ביצים. לכאן התשובה היא התהליך שתבצע וביטוי התלוי במספר הקומות שאומר מהו מספר הזריקות שיספיקו לך.

 

[cauchy]

הממ

אני לא יודע אם אני אמור לפתור את החידה כדי לא להרוס למי שביקש אותה. למי שכן מכיר את המקרה הפרטי של 2 ביצים עם 100 קומות, שאלה קטנה: הפתרון הכללי האידיאלי הוא הכללה של המקרה הפרטי?

 

[pallidfool]

כמובן.

 

[AltElAntE]

נדמה לי

קודם כל נזרוק ביצה מהקומה n/2 אם היא תישבר נזרוק מ n/2/2, אם לא נזרוק מהקומה האמצעית בין הגג לקומה n/2 קרי 75%n או n*75/100. וכך נמשיך מחצי לחצי לחצי ונדע את הקומה במספר זריקות מינימלי?

 

[pallidfool]

לא.

השיטה אינה פועלת. מקרה 1) הביצה נשברת בכל הקומות. מקרה 2) הביצה נשברת בכל הקומות פרט לקומה 1. אם נזרוק מ-50, הביצה תשבר בשני המקרים. לאחר מכן תזרוק מ-25, והביצה השניה תשבר. לא נותרו לך ביצים לזרוק, אך עדין קיבלת תוצאה זהה עבור שני המקרים, ולכן אין לך דרך להבדיל ביניהם.

 

[jaXon]

הנה עוד אחת

אולי היא לא קשה מדי, אבל ההנאה מובטחת הוכח : בכל קבוצה של 6 אנשים, מתקיים תמיד אחד מהשניים : 1) יש שם 3 אנשים שמכירים זה את זה 2) יש שם 3 אנשים שזרים לחלוטין זה לזה (היכרות היא יחס הדדי)

 

[yatir]

יש משפט שאומר שבקבוצה

אם לכל שני אנשים יש ידיד משותף, אז יש משהו שהוא ידיד של כולם.

 

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

כנראה "לפחות אחד מהשניים"?