תורת האלגוריתמים, שקילות

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

• שאלה

  האם תוכלו לחלק `24` קילו של מסמרים לשני חלקים של `15` ו-`9` קילו בעזרת מאזני כף ללא משקולות?

  נושאים:

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

• המשימה המתוחכמת

  לחנה יש סלסלה בה `13` תפוחים. חנה רוצה לדעת את המשקל הכולל של כל התפוחים האלה. לרחל יש משקל דיגיטלי, והיא מוכנה לעזור לחנה, אבל רק בתנאים הבאים: בכל שקילה חנה יכולה לשקול בדיוק `2` תפוחים, והמספר של השקילות לא יכול לעבור את `8`.

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

  נושאים:

  קומבינטוריקה -> ספירה כפולה אלגברה -> משוואות אלגברה -> בעיות מילוליות הוכחה ודוגמה -> בניית דוגמה תורת האלגוריתמים -> שקילות
  מקורות:
  • אתר האינטרנט problems.ru

• 9 מטבעות

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

  נושאים:

  לוגיקה -> הגיון תורת האלגוריתמים -> שקילות בעיות מינימום ומקסימום

• 26 מטבעות

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

  הצגת רמז

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

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

• 80 מטבעות

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

  הצגת רמז

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

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

• 9 קילו של אורז

  ברשותכם `9` קילו של אורז. איך למדוד `2` קילו אורז באמצעות שלוש שקילות במאזני כף ושימוש בשתי משקולות: של `200` גרם ושל `50` גרם?

  נושאים:

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

• שקילת מטבעות

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

  נושאים:

  לוגיקה -> הגיון תורת האלגוריתמים -> שקילות קומבינטוריקה -> בדיקת מקרים -> תהליכים בעיות מינימום ומקסימום
  מקורות:
  • אולימפיאדת גיליס, תש"פ שאלה 1

• שאלה

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

  נושאים:

  לוגיקה -> הגיון תורת האלגוריתמים -> שקילות קומבינטוריקה -> בדיקת מקרים -> תהליכים
  מקורות:
  • אולימפיאדת בנו ארבל, 2019, כיתה ח שאלה 8

• גְּנֵבַת אוֹצַר הַטִּירָה

  הַדֶּרֶךְ הַמְּתוּחְכֶּמֶת בָּהּ נִגְנְבָה תֵּבַת אוֹצָר, הַמְּכִילָה בְּעִיקָרָהּ תַּכְשִׁיטִים וַאֲבָנִים יְקָרוֹת, מִטִּירַת גְּלוּמְהֶרְסְט, עָבְרָה כְּמָסֹרֶת בְּמִשְׁפַּחַת דֶּה גּוּרְנֵי. הַגַּנָּבִים הִתְכַּלְּלוּ מֵאִישׁ, נַעַר וְיֶלֶד קָטָן, שֶׁדֶּרֶךְ הַמִּלּוּט הַיְּחִידָה שֶׁלָּהֶם עִם תֵּבַת הָאוֹצָר הָיְתָה דֶּרֶךְ חַלּוֹן גָּבוֹהַּ. מִחוּץ לַחַלּוֹן הוּצַּב גַּלְגֶּלֶת, שֶׁעָלֶיהָ עָבַר חֶבֶל עִם סַל בְּכָל קָצֶה. כְּשֶׁסַּל אֶחָד הָיָה עַל הַקַּרְקַע, הַשֵּׁנִי הָיָה בַּחַלּוֹן. הַחֶבֶל סֻדַּר כָּךְ שֶׁהָאֲנָשִׁים בַּסַּל לֹא יָכְלוּ לַעֲזֹר לְעַצְמָם בְּאֶמְצָעוּתוֹ וְלֹא לְקַבֵּל עֶזְרָה מֵאֲחֵרִים. בְּקִצּוּר, הַדֶּרֶךְ הַיְּחִידָה לְשִׁמּוּשׁ בַּסַּלִּים הָיְתָה עַל יְדֵי הַצָּבַת מִשְׁקָל כָּבֵד יוֹתֵר בְּאֶחָד מֵהַשֵּׁנִי.

  עַכְשָׁו, מִשְׁקַל הָאִישׁ הָיָה `195` לִיבְּרוֹת, הַנַּעַר `105` לִיבְּרוֹת, הַיֶּלֶד `90` לִיבְּרוֹת וְתֵּבַת הָאוֹצָר `75` לִיבְּרוֹת. הַמִּשְׁקָל בַּסַּל הַיּוֹרֵד לֹא יָכֹל לַחְרֹג מִזֶּה שֶׁבַּשֵּׁנִי בְּיוֹתֵר מִ `15` לִיבְּרוֹת בְּלִי לִגְרֹם לִירִידָה כֹּה מְהִירָה שֶׁתִּהְיֶה מְסֻכֶּנֶת בְּיוֹתֵר לְבֶן אָדָם, אַף עַל פִּי שֶׁלֹּא תִּגְרֹם נֶזֶק לָרְכוּשׁ הַגָּנוּב. רַק שְׁנֵי אֲנָשִׁים, אוֹ אָדָם אֶחָד וְהָאוֹצָר, יָכְלוּ לְהָנִיחַ בְּאוֹתוֹ סַל בְּבַת אַחַת. אֵיךְ הֵם הִצְלִיחוּ לִבְרֹחַ וְלָקַחַת אִתָּם אֶת תֵּבַת הָאוֹצָר?

  הַחִידָה הִיא לִמְצֹא אֶת הַדֶּרֶךְ הַקְּצָרָה בְּיוֹתֵר לְבִצּוּעַ הַמַּעֲשֶׂה, שֶׁכְּשֶׁעַצְמוֹ אֵינוֹ קָשֶׁה. זִכְרוּ, אָדָם לֹא יָכוֹל לַעֲזֹר לְעַצְמוֹ עַל יְדֵי תְּלִיָּה עַל הַחֶבֶל, הַדֶּרֶךְ הַיְּחִידָה הִיא לָרֶדֶת "עִם מַהֲלוּמָה," כְּשֶׁהַמִּשְׁקָל בַּסַּל הַשֵּׁנִי כְּמִשְׁקָל נֶגְדִּי.

  נושאים:

  אלגברה -> בעיות מילוליות תורת האלגוריתמים -> שקילות קומבינטוריקה -> בדיקת מקרים -> תהליכים בעיות מינימום ומקסימום
  מקורות:
  • שעשועונים במתמטיקה, הנרי ארנסט דודני שאלה 377