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

جلسه‌ی 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‌اند.
اشتباه رایج: گفتنِ «بزرگ‌ترین را بگیر» وقتی ممکن است بزرگ‌ترین وجود نداشته باشد (مثلاً بی‌نهایت عدد). در مجموعه‌های متناهی همیشه هست.

چالش‌ها

  1. Averages Round a Circle (آسان)
  2. The Fewest Top Wins (آسان)
  3. What the Top Player Knows (متوسط)
  4. The Longest Path (متوسط)
  5. How Many Kings? (سخت)
  6. Write the King Proof (سخت)

← جلسه‌ی 32: ثابت کن و بساز جلسه‌ی 34: یک مسئله‌ی بلند: بازیِ گلدان‌ها →