جلسهی 33: به بزرگترین نگاه کن Look at the Extreme
اصلِ اکسترمم: وقتی نمیدانی از کجا شروع کنی، به بزرگترین، کوچکترین یا طولانیترین نگاه کن. پادشاهِ مسابقه، دور در گرافی که درجهها دستکم ۲ است، و عددهایی که میانگینِ همسایههایشاناند.
در این جلسه یاد میگیری
- در یک اثبات، «بزرگترین» یا «طولانیترین» را انتخاب میکنی و از آن نتیجه میگیری.
- با «اگر نه، چیزی بزرگتر پیدا میشد» به تناقض میرسی.
- ثابت میکنی کسی که بیشترین برد را دارد پادشاهِ مسابقه است.
درس
در یک مسابقه هر دو بازیکن یک بار با هم بازی میکنند و مساوی نداریم. به بازیکنِ A «پادشاه» میگوییم اگر برای هر بازیکنِ دیگرِ Y، یا A خودش Y را برده باشد، یا A کسی را برده باشد که Y را برده.
ادعا: کسی که بیشترین برد را دارد، پادشاه است.
اثبات: فرض کن A بیشترین برد را دارد ولی پادشاه نیست. پس یک Y هست که A را برده و همهی کسانی را هم که A برده، برده. آنوقت Y از A بیشتر برد دارد (همهی بردهای A بهعلاوهی خودِ A). تناقض!
دومین مثال: اگر در یک گراف هر رأس دستکم ۲ یال داشته باشد، گراف یک دور دارد.
اثبات: طولانیترین مسیرِ v₁، v₂، …، vₖ را در نظر بگیر. v₁ دستکم ۲ همسایه دارد؛ یکی v₂ است. همسایهی دیگرش اگر بیرونِ مسیر بود، مسیر را طولانیتر میکرد، که ممکن نیست. پس روی مسیر است، مثلاً vᵢ با i ≥ ۳، و v₁ → v₂ → … → vᵢ → v₁ یک دور است.
بازی کن: به هر نقطه دقیقاً ۲ یال بده. ببین بدونِ دور میشود؟
سومین مثال: ۱۰ عدد دورِ یک دایرهاند و هر کدام میانگینِ دو همسایهاش است. بزرگترین عدد، M، را بگیر. میانگینِ دو همسایهاش M است، ولی هیچکدام از M بزرگتر نیست؛ پس هر دو برابرِ Mاند. همین را برای آنها تکرار کن: همهی عددها برابرِ Mاند.
اشتباه رایج: گفتنِ «بزرگترین را بگیر» وقتی ممکن است بزرگترین وجود نداشته باشد (مثلاً بینهایت عدد). در مجموعههای متناهی همیشه هست.
چالشها
- Averages Round a Circle (آسان)
- The Fewest Top Wins (آسان)
- What the Top Player Knows (متوسط)
- The Longest Path (متوسط)
- How Many Kings? (سخت)
- Write the King Proof (سخت)
← جلسهی 32: ثابت کن و بساز جلسهی 34: یک مسئلهی بلند: بازیِ گلدانها →