بتل کد Battle Codeدارد باز می‌شود…

جلسه‌ی 11: ناوردایی: چیزی که عوض نمی‌شود Invariants

وقتی کاری را بارها تکرار می‌کنیم، چیزی پیدا کن که هیچ‌وقت عوض نمی‌شود: جمع، زوج و فرد بودن، باقی‌مانده. با همین، ثابت می‌کنیم بعضی کارها هرگز ممکن نیست.

در این جلسه یاد می‌گیری

درس

۷ سکه در یک ردیف داریم. با هر ضربه، یک سکه و سکه‌ی کنارش با هم برمی‌گردند. می‌توانی همه را «رو» کنی؟ امتحان کن و حواست به عدد «سکه‌های پشت» باشد: زوج است یا فرد؟

چه شد؟ هر ضربه دو سکه را برمی‌گرداند. اگر هر دو رو بودند، تعداد پشت‌ها ۲ تا زیاد می‌شود؛ اگر هر دو پشت، ۲ تا کم؛ اگر یکی رو یکی پشت، عوض نمی‌شود. پس «زوج یا فرد بودنِ تعداد پشت‌ها» هیچ‌وقت عوض نمی‌شود. به چنین چیزی «ناوردا» می‌گوییم. شروع با ۴ پشت (زوج) بود و ۰ هم زوج است: ممکن است. ولی اگر با ۳ پشت شروع می‌کردیم، هرگز به ۰ نمی‌رسیدیم.

حالا تو امتحان کن: این‌جا ۳ پشت داریم. هر چه بزنی، تعداد پشت‌ها فرد می‌ماند و هیچ‌وقت ۰ نمی‌شود. همین استدلالِ یک‌خطی جای هزار بار امتحان کردن را می‌گیرد!

چند ناوردای معروف:
🍫 شکستن شکلات: هر شکستن یک تکه را دو تکه می‌کند، پس تعداد تکه‌ها دقیقاً یکی زیاد می‌شود. شکلات ⁦۴ × ۶⁩ (۲۴ مربع) همیشه با ۲۳ شکستن تمام می‌شود، هر جور که بشکنی.
➕ جمع: روی تخته عددها نوشته شده؛ دو عدد را پاک کن و جمعشان را بنویس. جمعِ همه عوض نمی‌شود.
🔁 زوجیت: اگر به‌جای جمع، اختلافشان را بنویسی، جمع عوض می‌شود ولی زوج یا فرد بودنِ آن نه (چون ⁦a + b⁩ و ⁦a − b⁩ هم‌زوجیت‌اند).

نقشه‌ی کلی در المپیاد: ۱) کاری که تکرار می‌شود را دقیق بنویس. ۲) دنبال چیزی بگرد که با یک حرکت عوض نمی‌شود (یا همیشه یک‌جور عوض می‌شود). ۳) آن را در شروع و در هدف حساب کن. اگر فرق دارند، هدف غیرممکن است.
اشتباه رایج: «امتحان کردم نشد، پس نمی‌شود» اثبات نیست؛ ناوردا اثبات است.

چالش‌ها

  1. Breaking Chocolate (آسان)
  2. Adding on the Board (آسان)
  3. Writing the Difference (متوسط)
  4. Odd Tails (متوسط)
  5. Chameleon Island (سخت)
  6. The Robot's Walk (سخت)

← جلسه‌ی 10: اصل لانه‌ی کبوتری جلسه‌ی 12: رنگ‌آمیزی: یک استدلالِ رنگی →