المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


آموزش:آماده‌سازی برای المپیاد:روش نوشتن اثبات

روش نوشتن اثبات

هر سال بعد از برگزاری و تصحیح برگه‌های مرحله دو، شاهد سیلی از اعتراضات هستیم. خیلی از بچه‌ها ادعا می‌کنن جوابی که در برگه نوشتن، کاملا درسته و اشتباهی از آن‌ها نمره کم شده. در صورتی که آخرش معمولا نمره‌ای بهشون تعلق نمی‌گیره. یکی از مهمترین علت‌هایی که باعث میشه از شما نمره کم بشه، نحوه‌ی نوشتن جوابه. یعنی خیلی وقت‌ها شما به ایده‌ی اصلی مسئله رسیدید و حلش کردید، ولی جوابی که توی ذهن شماست زمین تا آسمون با چیزی که مینویسین فرق داره! با بررسی برگه‌های سال‌های گذشته تصمیم گرفتیم در قالب این متن، مشکلات مختلف رو توضیح بدیم تا در نهایت ادبیات مشترکی برای نوشتنِ پاسخ پیدا کنیم. سعی کردیم تمام نکات رو گویا و به همراه مثال بیان کنیم، ولی به هرحال هیچ متنی خالی از اشکال نیست و خوشحال می‌شیم اگر نقد یا نظری دارید بهمون اطلاع بدید.

در ادامه در هر بخش موضوعی مطرح شده و در آخرِ متن هم توصیه‌هایی رو آوردیم که خوندنش خالی از لطف نیست.

سازمان‌دهی اولیه‌ی گزاره‌ها

راه‌حل هر مسئله‌ای از یه سری گزاره تشکیل شده که باید با ترتیب مشخصی بیان بشن. زمانی که فکر می‌کنین سوال رو حل کردین، لزوما آماده‌ی نوشتن جواب نیستین. باید قبل از نوشتن، ترتیب قرار دادن گزاره‌ها و روند منطقی بینشون رو مرور کنین. استفاده از چرک‌نویس به شدت توصیه میشه. شاید یکم ازتون وقت بگیره ولی مطمئن باشین همین وقت رو باید وسط نوشتن بذارید تا اشکالات نوشتن‌تون رو برطرف کنین.

شکستن اثبات به چند زیرمساله

معمولا راه‌حل سوال، از چند قسمتِ مختلف تشکیل شده که طراح نمره‌ی هر بخش را مشخص کرده تا اگه قسمتی از راه‌حلتون اشتباه بود نمره‌ی بقیه‌ی بخش‌ها رو از دست ندین. پس مهمه که بتونید بخش‌های مختلف راه‌حل رو از هم جدا کنین. می‌تونین قسمت‌های مختلف را تحت عنوانِ لم بیان و اثبات کرده و در راه‌حل اصلی استفاده کنین.

بخش‌هایی که بیش از یک بار در حل مساله‌ی اصلی ازشون استفاده می‌کنین هم گزینه‌ی خوبی برای لم شدن هستن. ولی حواستون باشه که هر لمی رو در کلی‌ترین حالتی که میخواین استفاده کنین به کار ببرین. در ضمن جو گیر نشید همه چی رو با لم بنویسین، لم زیاد در راه‌حل هم میتونه گیج‌کننده باشه!

خوبه که هر لم، یه اسمی داشته باشه تا در مسیر اثبات با اون اسم بهش رجوع کنین. مصحح سطح معلوماتش کافیه و میتونید از تعریف‌های مرسوم مثل: گراف، جایگشت و یا الگوریتم‌های مختلف و … استفاده کنین. ولی هیچ‌‌جایی نباید روی قضیه‌هایی که بلده یا عمق استنتاجش حساب کنین. یعنی اثبات شما باید جوری باشه که هر آدم منطقی‌ای با یه بار خوندنش جواب رو بفهمه.

اگه میخواین سوال رو در چند حالت مختلف حل کنین، اول درباره اینکه چجوری تقسیم‌بندی کردین توضیح بدین و بعد از اون ویژگی هر حالت رو قبل از بیانش به شکل متفاوتی بنویسین (مثلا با اندازه‌ی بزرگتر بنویسین یا اینکه زیرش خط بکشین)

فرض کنید می‌خواهیم حکم یک مسئله‌ را برای عددهای زوج و فرد به صورت مجزا حل کنیم:

حالت ۱. اگر n زوج باشد:
توضیحات حالت اول . . .
حالت ۲. اگر n فرد باشد:
توضیحات حالت دوم . . .

بررسی نهایی: بررسی صحت اثبات

حالا وقتشه که یه بار خودتون رو جای مصحح‌ِ بیچاره بذارین و ببینین که اون باید چجوری منظور شما رو بفهمه. میتونین سوالایی مثل سوالای پایین رو با خودتون مرور کنین تا اشکالای اثباتتون مشخص بشه:

  1. آیا با زیرمساله‌های اثبات‌شده میشه مساله‌ی اصلی رو نتیجه گرفت؟
  2. آیا به همه‌ی زیرمساله‌هایی که استفاده کردیم برای اثبات مساله‌ی اصلی احتیاج داریم؟
  3. آیا هرکدوم از زیرمساله‌ها درست اثبات شدن؟
  4. آیا حالتی در مساله‌ی اصلی وجود داشته که بررسی نشده باشه؟

یادتون نره که هر اشتباه یا نقصی در راه‌حلتون مساوی با کسر نمره‌ی اون بخش از جوابه. گاهی ارزش اون قسمت‌ها برابر با کل مساله میشه که در اینصورت به شما هیچ نمره‌ای داده نمیشه. نحوه‌ی ارزش‌گذاری هر بخش با توجه به سوال تعیین میشه، ممکنه نوشتن یک حدس نمره‌ داشته باشه یا در نظر نگرفتن یه حالت خاص از مساله کل نمره را از شما بگیره.

توضیح اجمالی روند اثبات

زمانی مجاز به شروع نوشتن هستین که اثباتی یکپارچه داشته باشین. وقتی که زیرمساله‌ها رو مشخص کردین و از درستی و کامل‌بودنش اطمینان دارین. بهتره ابتدا روند کلی اثبات رو برای مصحح بیان کنین تا بتونه راحت‌تر در طول اثبات شما رو همراهی کنه. در این چکیده هر حکمی که نیاز دارین را بیان و ایده‌ی اثبات هر کدوم رو ذکر کنین.

سوال. می‌خواهیم اعداد ۱ تا $n$ را به ۳ دسته افراز کنیم که مجموع اعداد هر ۳ دسته با یکدیگر برابر باشند. به ازای چه $n$هایی اینکار ممکن است؟

جواب. ابتدا ثابت می‌کنیم اگر باقیمانده‌ی n بر ۳ برابر با ۱ باشد اینکار ممکن نیست. به ازای باقی اعداد روشی برای یافتن ۳ دسته ارائه می‌دهیم. اینکار را به کمک استقرا بیان می‌کنیم و از $n$، حکم را به ازای $n+3$ نتیجه خواهیم گرفت. ادامه‌ی راه‌حل . . .

نام‌گذاری پارامترها

بهتره پارامترهایی که توی راه‌حل ازشون زیاد استفاده می‌کنین نام‌گذاری بشن تا هر دفعه مجبور به توضیح دوباره‎‌ی اونها نباشین. خوبه نام‌گذاری پارامترها به ویژگی‌هاشون مربوط باشه. در مورد تعاریف، قضیه‌ها و بقیه‌ی موجوداتی که اسم‌های مشخصی دارن (مثل ماتریس، دور و درخت (در گراف) …) یا در صورت مساله اسم واسشون انتخاب شده، همون اسامی رو استفاده کنین.

یک مثال بدون نام‌گذاری پارامترها

«نشان می‌دهیم سن بزرگ‌ترین دوست هم‌مدرسه‌ای علی از سن کوچک‌ترین دوست هم‌مدرسه‌ای علی حداکثر دو سال بیشتر است. اگر سن بزرگ‌ترین دوست هم‌مدرسه‌ای علی . . . آنگاه سن کوچک‌ترین دوست هم‌مدرسه‌ای علی . . . سپس سن بزرگ‌ترین دوست هم‌مدرسه‌ای علی . . .»

نام‌گذاری پارامترها در مثال بالا

«سن بزرگ‌ترین دوست هم‌مدرسه‌ای علی را با بزرگه و سن کوچک‌ترین دوست هم‌مدرسه‌ای علی را با کوچیکه نمایش می‌دهیم. حال نشان می‌دهیم بزرگه از کوچیکه حداکثر دو سال بیشتر است. اگر بزرگه . . . آنگاه کوچیکه . . . سپس بزرگه . . .»

رسم شکل

یه ضرب‌المثل چینی میگه: «یک تصویر به هزار کلمه می‌ارزد»

بعضی از اطلاعات مسئله هستن که با شکل بسیار زیباتر و ساده‌تر بیان میشن. همچنین شکل می‌تونه یک دید کلی به مصحح بده و به اون در فهمیدن درست اثبات کمک کنه. در صورتی که از شکل در روند اثبات استفاده می‌کنین باید اطلاعاتش با متن همخونی داشته باشد و نام‌گذاری‌ها هم یکسان باشن. بهتر که شکل رو در کلی‌ترین حالت ممکن بکشین و اطلاعاتی که اون رو حالتی خاص از مسئله نشان میده استفاده نکنین. مثلا اگه فضای مساله را با گراف مدل می‌کنیم، قشنگ‌تره که بعد از کشیدن گراف راس‌هایی که در متنِ اثبات براشون اسم انتخاب کردیم در شکل نیز نام‌گذاری بشن.

فراموش نکنین که برای چی شکل می‌کشین. شکل، اثبات نیست و فقط قراره روند اثبات را راحت‌تر بیان کنه. پس نباید باعث گیج‌شدن مصحح بشه. سعی کنین اندازه‌ی شکل‌هاتون با متن همخونی داشته باشد و در کنار متن (و نه وسط آن) کشیده بشه. مثلا حواستون باشه توضیحات یک شکل در صفحه‌ی دیگه‌ای نوشته نشه.

در شکل‌هاتون میتونین از فلش (برای توضیح یک حرکت)، خط‌چین و نقطه‌چین (برای وجود یا عدم وجود یک خط) و هاشور افقی و عمودی (برای تمایز بین چند ناحیه) هم استفاده کنین.

شکل‌ها باید به ساده‌ترین و کلی‌ترین حالت ممکن کشیده بشن و نباید اطلاعات بی‌اهمیت نمایش داده بشه. مثلا اگه سوال درباره‌ی تعدادی خرگوش و روباه است، در شکل لازم نیست سعی کنید خرگوش و روباه بکشین! کافیه مثلا به جای خرگوش، مربع و به جای روباه، مثلث کشیده بشه و کنار شکل هم معنای هرکدوم رو بنویسین.

تاکید شکل باید روی اطلاعاتی باشه که به اثبات کمک میکنه. مثلا اگه توی مثالمون حمله‌کردن یه روباه به یه خرگوش مهمه، می‌تونیم اون رو با یک خط بینشون نشون بدیم (و نه بیشتر!).

شماره‌گذاری شکل‌ها، فرمول‌ها و لم‌ها

کلمه‌هایی مثل فرمول بالا، شکل مربوطه، بر طبق لم، آن شکل و … فقط باعث ایجاد ابهام میشه که کدام شکل؟ کدام فرمول بالا؟ و … . این مشکل هم با شماره‌گذاری یا نام‌گذاری شکل‌ها، فرمول‌ها، لم‌ها و . . . به سادگی رفع میشه. کافیه زیر عکس، کنار فرمول و قبل از لم یه شماره بذارید و با استفاده از اون شماره در رابطه با شکل، فرمول یا لم صحبت کنین. مثل: شکل (i) یا فرمول (۳).

ذکر مثال

گاهی در طول اثبات، برداشت‌های مختلفی از متن بوجود میاد. در اینصورت یک مثال می‌تونه ابهام بوجود اومده رو برطرف کنه. درنتیجه باید حواستون باشه مثال جوری انتخاب بشه که از همه‌ی برداشت‌های مختلف، فقط منظور شما با مثال جور دربیاد. در ضمن مثال باید با چیزی که نوشتین تطابق داشته باشه و ساده‌ترین حالت ممکن انتخاب بشه.

تاکید می‌کنیم که مثال جای اثبات را نمی‌گیره و بررسی چند حالت خاص نمی‌تونه ثابت کنه حکم مسئله درسته.

نمونه‌ای از توصیف‌ غیر‌دقیق و مثال اشتباه

توصیف: موجوداتی را که از گیاهان تغذیه می‌کنند گیاه‌خوار و باقی موجودات را غیرگیاه‌خوار می‌نامیم.

مثال: گاو و گوسفند گیاه‌خوار هستند و زنبور (چون کل گیاه را نمی‌خورد) غیرگیاه‌خوار است.

صورت دقیق‌تر توصیف و مثالِ آن

توصیف: موجوداتی را که از گیاهان تغذیه می‌کنند و کل گیاه را می‌خورند گیاه‌خوار و باقی موجودات را غیرگیاه‌خوار می‌نامیم.

مثال: برای مثال گاو و گوسفند گیاه‌خوار هستند و زنبور غیرگیاه‌خوار است.

قضیه

گاهی در روند اثبات به حکم‌هایی می‌رسین که بسیار معروفن و همه درستیِ اون رو تایید میکنن. یا قضیه‌هایی هستن که اثباتشون در کتاب مرجعی اومده. در اینصورت میتونین با نوشتن صورت دقیق قضیه و توضیح کافی درباره‌ی منبع‌ِ آن از قضیه‌ استفاده کنین. در غیراینصورت ممکنه قضیه‌ی بیان‌شده مورد قبول قرار نگیره.

مهم

در آخر می‌خوایم به دو نکته‌ی بسیار مهم در اثبات‌ها اشاره کنیم. اشکالایی که دیگه ربطی به نوشتن ندارن. یعنی کلا شما از بیخ و بُن سوال رو اشتباه حل کردین!

بدترین حالت. توی یه سوال ممکنه حالت‌های مختلفی برای مساله وجود داشته باشه. شما هم روشی رو برای حل پیشنهاد میدین و برای اثبات، روش‌ِتون رو در یک حالت خاصی از مسئله (که به قول خودتون بدترین حالت ممکنه) توضیح میدین و بعدش نتیجه می‌گیرین در حالت کلی هم اثبات درسته! بررسی اینکه یه حالت، بدترین حالت ممکنه واقعا کار سختیه و خودش اثبات میخواد و شما نمیتونین با تکیه بر این فرض جوابتون رو درست فرض کنین. باید راه‌حل رو در حالت کلی ارائه بدین و اثباتش رو هم برای تمامی حالات بیان کنین تا جواب مورد قبول واقع بشه.

اثبات با مثال. در خیلی از برگه‌های پاسخ‌ دیدیم که به جای حل مسئله در حالت کلی، اومدین نحوه‌ی حلتون رو واسه یه مثال توضیح دادین و تهش هم یه سه نقطه گذاشتین که یعنی جواب به همین ترتیب بدست میاد. اینکار نه تنها بخشی که حتی همه‌ی نمره‌ی اون سوال رو از شما می‌گیره. همانطور که بالاتر توضیح دادیم مثال خیلی کمک خوبی برای فهمیدن راه‌حله ولی راه‌حل نیست! پس به جز ارائه‌ی مثال باید روند راه‌حل رو برای حالت کلی بنویسین و اثبات کنین.


ابزار صفحه