جلسهی 32: ثابت کن و بساز Prove and Build
سؤالهای «حداکثر چند؟» دو نیمه دارند: یک نمونه که به آن عدد برسد، و اثباتی که بیشتر از آن نمیشود. شاهها روی صفحهی شطرنج، رخها، عددهای بیهمسایه و گرافِ بیمثلث.
در این جلسه یاد میگیری
- میدانی جوابِ «حداکثر» یک ساخت و یک کران لازم دارد.
- با تقسیم به تکهها (هر تکه حداکثر یکی) کران میگذاری.
- برای کران یک ساختِ منظم پیدا میکنی که دقیقاً به آن برسد.
درس
سؤالِ «حداکثر چند شاه را میشود روی صفحهی ۶ × ۶ گذاشت طوری که هیچ دو شاهی به هم حمله نکنند؟» جوابش یک عدد است، ولی در مرحلهی دوم باید دو چیز را ثابت کنی:
۱) ساخت: یک چیدمان با همین تعداد نشان بده.
۲) کران: ثابت کن بیشتر از آن ممکن نیست.
فقط یکی از این دو، نصفِ جواب است. اول بازی کن: چند شاه جا میدهی؟
کران: صفحه را به ۹ مربعِ ۲ × ۲ تقسیم کن. هر دو خانهی یک مربعِ ۲ × ۲ به هم چسبیدهاند (کنار یا گوشه)، پس هر مربع حداکثر یک شاه دارد: حداکثر ۹ شاه.
ساخت: شاهها را روی خانههایی بگذار که شمارهی سطر و ستونشان هر دو فرد است (۱، ۳، ۵): ۹ شاه، و هر دو تا دستکم یک خانه فاصله دارند.
پس جواب ۹ است، و حالا واقعاً ثابت شده.
همین ترفندِ «تکهها» همهجا به کار میآید. از ۱ تا ۱۰ چند عدد میشود برداشت که هیچ دو تایی پشتِ سرِ هم نباشند؟ جفتها: {۱، ۲}، {۳، ۴}، …، {۹، ۱۰}. از هر جفت حداکثر یکی: حداکثر ۵. ساخت: ۱، ۳، ۵، ۷، ۹.
اشتباه رایج: فقط یک نمونهی ۵تایی نشان دادن و گفتنِ «بیشتر پیدا نکردم». پیدا نکردن، اثبات نیست!
چالشها
- The Missing Half (آسان)
- Rooks on a Long Board (آسان)
- Kings on the Big Board (متوسط)
- No Two in a Row (متوسط)
- Friends Without a Triangle (سخت)
- Write Both Halves (سخت)
← جلسهی 31: ساختن و مثالِ نقض جلسهی 33: به بزرگترین نگاه کن →