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

جلسه‌ی 29: برهانِ خلف Proof by Contradiction

فرض کن ادعا غلط است و ببین به چیزِ غیرممکنی می‌رسی. اگر رسیدی، ادعا درست است. عددهای اولِ بی‌شمار، زوج بودنِ n از زوج بودنِ n²، و دو نفر با تعدادِ دوستِ برابر.

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

درس

برهانِ خلف: برای ثابت کردنِ P، فرض کن P غلط است. قدم‌به‌قدم جلو برو تا به چیزی برسی که نمی‌شود (تناقض)، مثلاً «عددی هم زوج است هم فرد» یا «⁦۵ < ۴⁩». چون فرضِ تو به تناقض رسید، فرض غلط بوده و P درست است.
مثال: «بزرگ‌ترین عددِ طبیعی وجود ندارد.» فرض کن N بزرگ‌ترین باشد. ولی ⁦N + ۱⁩ هم طبیعی است و از N بزرگ‌تر: تناقض.

عددهای اول بی‌شمارند (اقلیدس، بیش از دو هزار سال پیش): فرض کن فقط تعدادِ محدودی عددِ اول هست: p₁، p₂، …، pₖ. عددِ ⁦M = p₁ × p₂ × … × pₖ + ۱⁩ را بساز. M بر هیچ‌کدام از pها بخش‌پذیر نیست (باقی‌مانده‌ی ۱ می‌دهد). ولی هر عددِ بزرگ‌تر از ۱ یک مقسوم‌علیهِ اول دارد؛ پس M یک مقسوم‌علیهِ اولِ تازه دارد که در فهرست نیست: تناقض.

لانه‌ی کبوتری همان برهانِ خلف است: «اگر هیچ لانه‌ای دو کبوتر نداشت، حداکثر k کبوتر جا می‌شد؛ ولی ⁦k + ۱⁩ کبوتر داریم: تناقض.»
اشتباه رایج: فرض را برعکس نکردن. خلافِ «همه‌ی …ها زوج‌اند» این است که «دست‌کم یکی فرد است»، نه این‌که «همه فردند».

چالش‌ها

  1. The First Line (آسان)
  2. Negating Correctly (آسان)
  3. If n Squared Is Even (متوسط)
  4. Euclid's Primes (متوسط)
  5. Same Number of Friends (سخت)
  6. Five Points in a Square (سخت)

← جلسه‌ی 28: اثبات یعنی چه؟ جلسه‌ی 30: نوشتنِ اثباتِ استقرایی →