אינדוקציה

• שאלה: רמת קושי: 6

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

  א. הוכיחו שהקוסם המרושע יכול לעשות את זה.

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

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

  נושאים:

  קומבינטוריקה -> תורת הגרפים קומבינטוריקה -> אינדוקציה

• שאלה: רמת קושי: 4

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

  נושאים:

  קומבינטוריקה -> אינדוקציה קומבינטוריקה -> תהליכים

• שאלה: רמת קושי: 4

  נתון מספר ממשי `a` כך ש-`a+1/a` מספר שלם. הוכיחו כי גם `a^n+1/a^n` שלם לכל `n` טבעי.

  נושאים:

  קומבינטוריקה -> אינדוקציה אלגברה -> טכניקה אלגברית

• 26 מטבעות רמת קושי: 3

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

  הצג רמז

  התחבר לאתר על מנת לקבל את הרמז
  נושאים:

  קומבינטוריקה -> אינדוקציה תורת האלגוריתמים -> שקילות

• 80 מטבעות רמת קושי: 3

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

  הצג רמז

  התחבר לאתר על מנת לקבל את הרמז
  נושאים:

  קומבינטוריקה -> אינדוקציה תורת האלגוריתמים -> שקילות

• שאלה: רמת קושי: 3

  הוכיחו כי 

  `1+3+5+...+(2n-1)=n^2`

  נושאים:

  קומבינטוריקה -> אינדוקציה אלגברה

• האם לכל הסוסים יש אותו צבע? רמת קושי: 4

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

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

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

  האם שלומי ביצע טעות במהלך ההוכחה שלו? אם כן, מצאו את הטעות.

  נושאים:

  קומבינטוריקה -> אינדוקציה לוגיקה -> הגיון לוגיקה -> הגיון -> פרדוקסים

• תרגילי מינק וחומרים נוספים מהאתר תשע"ט תרגיל 4 שאלה: 1 רמת קושי: 3

  .המישור חולק על ידי n ישרים ומעגלים,

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

  הצג רמז

  התחבר לאתר על מנת לקבל את הרמז
  נושאים:

  קומבינטוריקה -> אינדוקציה גאומטריה -> גאומטריה במישור
  מקורות:
  • תרגילי מינק וחומרים נוספים מהאתר תשע"ט תרגיל 4