שתי חידות

[טיקטי]

שתי חידות

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

 

[Grimble Grumble]

2)

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

 

[טיקטי]

יפה מאד אני עשיתי את זה בדרך שונה

לגמרי

 

[טיקטי]

במחשבה שנייה נראה לי שטעית

הסבר: זה נכון שאים אפשר להגיע מהריבוע לקטן לגדול אז אפשר להגיע מהגדול לקטן אבל כשאתה בודק בדרך ההפוכה הקפיצות צריכות להיות גם 1 ולא 2 (אים הגעת לריבוע כפול) אים טעיתי תתקנו אותי בבקשה

 

[Grimble Grumble]

הסבר

כל קפיצה שצפרדע עושה היא יכולה גם לקפוץ הפוך... (ז"א לחזור אחורה...)... על כן אם אפשר לעבור מריבוע קטן לריבוע גדול חייבת להיות אפשרות גם לעבור מגדול לקטן... עכשיו נניח את הריבוע הגדול על ציר המספרים כאשר הנקודות שלו הן (0,0) (1,0) (1,1) (0,1)... בשביל ליצור ריבוע קטן יותר צריך להגיע למצב שבו אורך כל צלע הוא פחות מ1, ז"א שבר... כל קפיצה של צפרדע תוביל אותה לנקודה (M,N) כאשר גם M וגם N מספרים שלמים ולכן האורך של הצלעות (המרחק בין הצפרדעים) הוא לעולם לא יהיה שבר הקטן מאחד (יכול להיות מספר לא שלם גדול מאחד אם המרחק הוא אלכסון מסויים)... הצפרדע על הנקודה 0,0 לדוגמא, יכולה לקפוץ רק ל: (0,2) (2,2) או (2,0)... היות שההפרשים בין הנקודות תמיד יהיו מספרים שלמים הצפרדעים תמיד ינחתו על מספרים שלמים ולכן לעולם לא יוכלו ליצור ריבוע שהצלעות שלו קטנות מ1... היות שהוכחנו שאם אפשר ליצור ריבוע גדול יותר, בטוח אפשר ליצור גם ריבוע קטן יותר... והיות שהוכחנו שאי אפשר ליצור ריבוע קטן יותר... אז אי אפשר ליצור גם ריבוע גדול יותר... מקווה שעכשיו ההסבר יותר מפורט...

 

[טיקטי]

בזה אתה צודק אבל זה לא מה

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

 

[שדון קטן]

../images/Emo62.gif 1)

M+N-2 ??

 

[The6thAngel]

שאלה לגבי 1...

אם שוברים n שכבות ביחד (אחת על השנייה) - זה נחשב שבירה אחת?

 

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

אני מכיר את הגרסה

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

 

[טיקטי]

m+n-2 זה הפתרון שאמרתי שהוא הרגיל

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

 

[Grimble Grumble]

אבל זה לא נכון

M+N-2 זה לא הפיתרון הנכון אם לשבור כמה אחד על השני נחשב לכמה שבירות... תחשבו על לוח של 2X5 לדוגמא... נגיד שוברים קודם כל את העסק ל1X5 ועוד 1X5... אז צריך עוד 8 שבירות בשביל לחלק את הכל לקוביות... סה"כ 9 (2+5-2=5...) גם בדרך ההפוכה (קודם לשבור ל5 חלקים של 1X2 ואז לשבור כל חלק בנפרד גם זה נותן 9 שבירות...

 

[טיקטי]

מה שטלמון אמר נכון זה נחשב ככמה

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

 

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

אינני יודע איזו חידה היתה בפורום

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

ממש מומלץ למי שאינו מכיר

 

[The6thAngel]

../images/Emo62.gif

אולי

(m-1)*(n-1)​

? כי לפי מה שאתה אומר, צריך פשוט לשבור הכל...

 

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

טיפ טיפה לא מדוייק...

 

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

../images/Emo35.gif חידה קצת דומה.

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

 

[Grimble Grumble]

חידה יפה...

האמת די קלה... היות שכל משחק, מישהו עף... וצריך שכולם חוץ מ1 יעופו... התשובה היא... n-1

 

[snogal]

צריך לזכור

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

 

[guyto]

../images/Emo62.gifאולי...

זה למעשה כמו עץ בינארי, כמות המשחקים n-1

 

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

כמובן ../images/Emo127.gif לשלושתכם.

מדוע זה דומה לשוקולד?