جمع دو به دو نصفشان گنگ است

از shaazzz
پرش به ناوبری پرش به جستجو

n عدد گنگ به ما داده شده است. ثابت کنید تا از آن ها پیدا می شوند که جمع دو به دو آن ها گنگ باشد.

پاسخ

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

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