שירשור החידות הגדול

[oferlaor]

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

חשבתי שיכול להיות נחמד לפצוח בחידה קלה במיוחד ולהמשיך משם.

חידה שאין לה כל קשר לקומבינטוריקה:

במדינת Hometheater יש לנו 100 ערים (מלשון עיר). מכל עיר יוצאות 5 דרכים לאחת מהערים האחרות באותה מדינה. אלה סך כל הדרכים שקיימים במדינה ההיא.

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

[droren]

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

[MartinHSabag]

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

[guyezra]

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

[MartinHSabag]

http://www.hometheater.co.il/modules.ph ... ic&t=28034

[guyezra]

http://www.hometheater.co.il/modules.ph ... ic&t=28034

...

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

[oferlaor]

וואלה, פספסתי (רואים שאני לא מבקר בפורום ללא קשר הרבה).

השאלה שלי בעודה עומדת (100 ערים, 5 דרכים מכל עיר, כמה דרכים סה"כ), אפשר להשתמש בקומבינטוריקה, אבל ידע בסיסי בחשבון מספיק.

[Zimer]

וואלה, פספסתי (רואים שאני לא מבקר בפורום ללא קשר הרבה).

השאלה שלי בעודה עומדת (100 ערים, 5 דרכים מכל עיר, כמה דרכים סה"כ), אפשר להשתמש בקומבינטוריקה, אבל ידע בסיסי בחשבון מספיק.

...

נראה לי קל מדי אז כנראה שלא הבנתי את השאלה נכון...
אתה אומר שיש 100 ערים ניקח רק חלק מהם [בתור דוגמא], נגיד עיר מספר אחת עיר מספר שתיים ועיר מספר שלוש, אז מעיר מספר אחת1 יוצאות חמש דרכים לעיר מספר 2, או דרך לחמש ערים שונות?
אם מעיר אחת לשנייה אז בעצם מהעיר האחרונה מגיעות 5 דרכים לעיר הראשונה.
ואז יש 500 דרכים, אבל אז אין בעצם חשיבה מאחורי התשובה.
???

[oferlaor]

zimer,

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

500 זו תשובה לא נכונה.

[osherov]

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

סה"כ יש לנו 10 כבישים בקבוצה הזאת (4+3+2+1=10)

ג. נעשה את אותו הדבר לשאר 20 הקבוצות הנותרות
(ערים 6,7,8,9,10 אח"כ ערים 11,12,13,14,15 .....עד לעיר 96,97,98,99,100)
סה"כ נגיע ל 200 כבישים (20 קבוצות שבכל קבוצה 10 כבישים)

ד. רק מה עד עכשיו לכל עיר יש 4 כבישים ולא 5 !! ולכן לשם הפשטות נחבר את עיר:
1 ל 51
2 ל 52
3 ל 53
...........
...........
50 ל 100

ככה נגיע בעצם לעוד 50 כבישים ולסה"כ של 250 כבישים (מכל עיר יוצאים 5 כבישים)

ה. הפתרון לא מלא מכיוון שאין חיבור בין כל הערים (כלומר לפי הפיתרון אין דרך להגיע מעיר 1 לעיר 6)
וכדי להגיע לזה נשנה את סעיף ד ונבצע חיבר בין עיר מקבוצה אחת לעיר בקבוצה שאחריה כלומר
1 ל 6 (חיבור בין קבוצה 1 לקבוצה 2)
7 ל 11(חיבור בין קבוצה 2 לקבוצה 3)
..........................................................
97 ל 2 (חיבור בין קבוצה 20 לקבוצה 1)

עכשיו רק נשאר לחבר את שאר הערים בקבוצה נעשה את זה כך:
3 ל 8
4 ל 9
5 ל 10
8 ל 13
9 ל 14
10 ל 15
.............
93 ל 98
94 ל 99
95 ל 100

סה"כ 50 כבישים
שמאפשרים להגיע מכל עיר לכל עיר
עדיין התשובה נשארה 250 כבישים



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

[Zimer]

אה עכשיו הבנתי אז את השאלה כנראה...
המטרה היא שכל עיר תחובר בסוף?
ושזה יקרה במינימום דרכים?

[osherov]

במדינת Hometheater יש לנו 100 ערים (מלשון עיר). מכל עיר יוצאות 5 דרכים לאחת מהערים האחרות באותה מדינה. אלה סך כל הדרכים שקיימים במדינה ההיא.

...

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

[Zimer]

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

[moco]

זה אומנם 250 אך ניתן להסביר את זה בצורה פשוטה בהרבה:
מכל עיר יוצאות 5 דרכים, 100X5 זה 500, אבל בעצם ספרנו פעמיים כי כל דרך מחוברת ל2 ערים, אז נחלק ב2 וקיבלנו 250.

לא צריך שכל המדינה תהיה מחוברת, אפשר גם 50 זוגות של ערים שמחוברות אחת לזוגתה עם 5 דרכים.

[oferlaor]

התשובות נכונות, אבל של moco נכונה "יותר" (לפי OCCAM'S RAZOR...)

osherov,

הכפפה אצלך (אלא אם כן תרצה שאלה "טיפה" יותר קשה)

[moco]

oferlaor,
OCCAM'S RAZOR זה שיקול בלהעדיף מסקנה מסוימת כיותר סבירה כנכונה מתוך כמה אפשריות כדי להסביר תופעות נצפות, כלומר, התיאוריה הפשוטה עדיפה.
במקרה הזה יש לנו אמת אחת וכמה הוכחות לאותה אמת אז זה רק עיניין של מה יותר אלגנטי .

[osherov]

לא לא השאלה הייתה מספיק קשה
להלן חידה נחמדה שמצאתי:

מהי שורת המספרים הבאה שצריכה לבוא בסידרה הזאת (כולל הסבר) ?
1
11
21
1211
111221
312211
13112221

[osherov]

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

moco,
אנא אמור לי איזה חדר המתנה לניתוח אתה מכיר שאומרים לפצוע לצאת ויותר הוא לא יכול יותר לחזור ? (זאת חידה לא חינוכית)

[moco]

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

אתה בטוח (בתור אחד שעבר על כל השרשור) שאת החידה האחרונה שלך לא שאלו כבר?
אני גם חושב שהיא אחלה. לצערי אני מוגבל בהנאתי בשרשור כי אני כבר מכיר יותר מידי חידות

[osherov]

בריפרוף מהיר בחידות לא מצאתי חידה זהה.

אגב, אני סוף סוף הגעתי לחידה של האנשים עם המספר על המצח (ראיתי את הפיתרון)
אני מנסה להבין\להוכיח את ההיגיון בפיתרון (או אולי לסתור אותו)