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

جلسه‌ی 32: ثابت کن و بساز Prove and Build

سؤال‌های «حداکثر چند؟» دو نیمه دارند: یک نمونه که به آن عدد برسد، و اثباتی که بیشتر از آن نمی‌شود. شاه‌ها روی صفحه‌ی شطرنج، رخ‌ها، عددهای بی‌همسایه و گرافِ بی‌مثلث.

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

درس

سؤالِ «حداکثر چند شاه را می‌شود روی صفحه‌ی ⁦۶ × ۶⁩ گذاشت طوری که هیچ دو شاهی به هم حمله نکنند؟» جوابش یک عدد است، ولی در مرحله‌ی دوم باید دو چیز را ثابت کنی:
۱) ساخت: یک چیدمان با همین تعداد نشان بده.
۲) کران: ثابت کن بیشتر از آن ممکن نیست.
فقط یکی از این دو، نصفِ جواب است. اول بازی کن: چند شاه جا می‌دهی؟

کران: صفحه را به ۹ مربعِ ⁦۲ × ۲⁩ تقسیم کن. هر دو خانه‌ی یک مربعِ ⁦۲ × ۲⁩ به هم چسبیده‌اند (کنار یا گوشه)، پس هر مربع حداکثر یک شاه دارد: حداکثر ۹ شاه.
ساخت: شاه‌ها را روی خانه‌هایی بگذار که شماره‌ی سطر و ستونشان هر دو فرد است (۱، ۳، ۵): ۹ شاه، و هر دو تا دست‌کم یک خانه فاصله دارند.
پس جواب ۹ است، و حالا واقعاً ثابت شده.

همین ترفندِ «تکه‌ها» همه‌جا به کار می‌آید. از ۱ تا ۱۰ چند عدد می‌شود برداشت که هیچ دو تایی پشتِ سرِ هم نباشند؟ جفت‌ها: {۱، ۲}، {۳، ۴}، …، {۹، ۱۰}. از هر جفت حداکثر یکی: حداکثر ۵. ساخت: ۱، ۳، ۵، ۷، ۹.
اشتباه رایج: فقط یک نمونه‌ی ۵تایی نشان دادن و گفتنِ «بیشتر پیدا نکردم». پیدا نکردن، اثبات نیست!

چالش‌ها

  1. The Missing Half (آسان)
  2. Rooks on a Long Board (آسان)
  3. Kings on the Big Board (متوسط)
  4. No Two in a Row (متوسط)
  5. Friends Without a Triangle (سخت)
  6. Write Both Halves (سخت)

← جلسه‌ی 31: ساختن و مثالِ نقض جلسه‌ی 33: به بزرگ‌ترین نگاه کن →