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

جلسه‌ی 31: ساختن و مثالِ نقض Constructions and Counterexamples

«آیا ممکن است؟» دو جواب دارد: اگر بله، یک نمونه بساز و نشان بده درست است؛ اگر نه، ثابت کن نمی‌شود. چیدن عددها با جمعِ اول، مربعِ جادویی، جدولِ مسابقه‌ی منصفانه و تقسیمِ ۱ تا n به دو گروهِ هم‌جمع.

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

درس

خیلی از سؤال‌های مرحله‌ی دوم می‌پرسند «آیا ممکن است…؟» یا «یک نمونه ارائه دهید». برای جوابِ «بله» کافی است یک نمونه بسازی و ثابت کنی همه‌ی شرط‌ها را دارد. ساختنِ خوب معمولاً منظم است: یک الگو که تکرار می‌شود، یا یک چرخش.
مثال: عددهای ۱ تا ۶ را دورِ یک دایره بچین طوری که جمعِ هر دو همسایه عددِ اول باشد: ۱، ۴، ۳، ۲، ۵، ۶ (جمع‌ها ۵، ۷، ۵، ۷، ۱۱، ۷).
پایین امتحان کن: عددهای ۱ تا ۹ را جابه‌جا کن تا یک مربعِ جادویی بسازی.

ساختِ چرخشی: ۵ تیم، هر دو تیم یک بازی؛ آیا می‌شود هر تیم دقیقاً ۲ برد داشته باشد؟ تیم‌ها را دورِ دایره بچین و بگو هر تیم دو تیمِ بعدی‌اش (در جهتِ ساعت) را می‌بَرد. هر تیم با هر تیمِ دیگر دقیقاً یک بار حساب شد و هر کدام ۲ برد دارد.

وقتی جواب «نه» است، یک شرطِ لازم پیدا کن. مثال: عددهای ۱ تا n را به دو گروه با جمعِ برابر تقسیم کن. جمعِ کل ⁦n(n + ۱) ÷ ۲⁩ است و باید زوج باشد؛ پس برای ⁦n = ۵⁩ (جمع ۱۵) غیرممکن است. وقتی جمع زوج است (⁦n = ۳⁩، ۴، ۷، ۸، …) هم باید یک ساخت ارائه دهی: مثلاً برای ⁦n = ۴⁩: {۱، ۴} و {۲، ۳}، و با چهارتایی‌های بعدی همین کار را تکرار کن.
اشتباه رایج: فقط شرطِ لازم را نوشتن و ساخت را جا انداختن (یا برعکس).

چالش‌ها

  1. A Wrong Rule (آسان)
  2. The Magic Centre (آسان)
  3. Prime Neighbours (متوسط)
  4. Equal Halves (متوسط)
  5. A Fair Tournament (سخت)
  6. Build the Rotation (سخت)

← جلسه‌ی 30: نوشتنِ اثباتِ استقرایی جلسه‌ی 32: ثابت کن و بساز →