חידה מפורום שוקולד

[freedom rider]

חידה מפורום שוקולד

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

 

[sagybp]

פשוט...

בתחילה יש לנו חתיכה אחת ובסוף אנחנו רוצים שיהיו לנו MxN חתיכות. מכיוון שבכל שבירה אנו מגדילים את כמות החתיכות ב-1 דרושות לנו מינימום של MxN-1 שבירות כדי לקבל MxN חתיכות... נראה לי...

 

[freedom rider]

אינטואיציה טובה

הוכחה?

 

[Fingertip]

זו בדיוק ההוכחה, לא?

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

 

[sagybp]

אוף ../images/Emo13.gif

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

). בקיצור, איך אומרים, enlighten me.

 

[Fingertip]

ההוכחה שלך הייתה כמעט בסדר גמור...

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

 

[sagybp]

יש לי על זה קטע

באחד מהשיעורים שאלה אחת מהסטודנטיות את רועי (המרצה ה*חתיך*

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

האמת שעכשיו זה לא נשמע כל כך מצחיק... אבל כנראה שצריך להיות שם באותו רגע...

 

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

זו הוכחה נכונה.

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