جلسهی 11: ناوردایی: چیزی که عوض نمیشود Invariants
وقتی کاری را بارها تکرار میکنیم، چیزی پیدا کن که هیچوقت عوض نمیشود: جمع، زوج و فرد بودن، باقیمانده. با همین، ثابت میکنیم بعضی کارها هرگز ممکن نیست.
در این جلسه یاد میگیری
- در یک فرایندِ تکراری، یک ناوردا (جمع، زوجیت، باقیمانده) پیدا میکنی.
- با ناوردا نشان میدهی رسیدن به یک حالت غیرممکن است.
- تعداد مرحلههایی که همیشه یکی است را میشماری (مثل شکستن شکلات).
درس
۷ سکه در یک ردیف داریم. با هر ضربه، یک سکه و سکهی کنارش با هم برمیگردند. میتوانی همه را «رو» کنی؟ امتحان کن و حواست به عدد «سکههای پشت» باشد: زوج است یا فرد؟
چه شد؟ هر ضربه دو سکه را برمیگرداند. اگر هر دو رو بودند، تعداد پشتها ۲ تا زیاد میشود؛ اگر هر دو پشت، ۲ تا کم؛ اگر یکی رو یکی پشت، عوض نمیشود. پس «زوج یا فرد بودنِ تعداد پشتها» هیچوقت عوض نمیشود. به چنین چیزی «ناوردا» میگوییم. شروع با ۴ پشت (زوج) بود و ۰ هم زوج است: ممکن است. ولی اگر با ۳ پشت شروع میکردیم، هرگز به ۰ نمیرسیدیم.
حالا تو امتحان کن: اینجا ۳ پشت داریم. هر چه بزنی، تعداد پشتها فرد میماند و هیچوقت ۰ نمیشود. همین استدلالِ یکخطی جای هزار بار امتحان کردن را میگیرد!
چند ناوردای معروف:
🍫 شکستن شکلات: هر شکستن یک تکه را دو تکه میکند، پس تعداد تکهها دقیقاً یکی زیاد میشود. شکلات ۴ × ۶ (۲۴ مربع) همیشه با ۲۳ شکستن تمام میشود، هر جور که بشکنی.
➕ جمع: روی تخته عددها نوشته شده؛ دو عدد را پاک کن و جمعشان را بنویس. جمعِ همه عوض نمیشود.
🔁 زوجیت: اگر بهجای جمع، اختلافشان را بنویسی، جمع عوض میشود ولی زوج یا فرد بودنِ آن نه (چون a + b و a − b همزوجیتاند).
نقشهی کلی در المپیاد: ۱) کاری که تکرار میشود را دقیق بنویس. ۲) دنبال چیزی بگرد که با یک حرکت عوض نمیشود (یا همیشه یکجور عوض میشود). ۳) آن را در شروع و در هدف حساب کن. اگر فرق دارند، هدف غیرممکن است.
اشتباه رایج: «امتحان کردم نشد، پس نمیشود» اثبات نیست؛ ناوردا اثبات است.
چالشها
- Breaking Chocolate (آسان)
- Adding on the Board (آسان)
- Writing the Difference (متوسط)
- Odd Tails (متوسط)
- Chameleon Island (سخت)
- The Robot's Walk (سخت)
← جلسهی 10: اصل لانهی کبوتری جلسهی 12: رنگآمیزی: یک استدلالِ رنگی →