درخت ساده
پیام یک درخت $n$ رأسی دارد ($n \ge 3$). او هر رأس این درخت را با یکی از دو رنگ سیاه و سفید رنگ کرده؛ طوری که هر دو رأس مجاور ناهم‌رنگ شده‌اند و هم‌چنین تعداد رأس‌های سفید بیش‌تر از تعداد رأس‌های سیاه شده است. حسام باید روی هر رأس سفید، یکی از اعداد $-1, 0, 1$ را بنویسد؛ طوری که عدد حداقل یک رأس سفید برابر ۰ نباشد. حسام باید طوری این کار را انجام دهد که به ازای هر رأس سیاه، مجموع اعداد هم‌سایه‌های آن برابر ۰ شود. برای مثال اگر درخت پیام به شکل (۱) باشد، حسام می‌تواند کارش را مانند شکل (۲) انجام دهد. ثابت کنید درخت پیام به هر شکلی که باشد، حسام قادر به انجام کارهای گفته شده، خواهد بود.
پاسخ
به استقرا‌ی قوی روی $n$ حکم را ثابت می‌کنیم. برای پایه‌ی استقرا $n=3$ و $n= 4$ را در نظر می‌گیریم. تنها حالت ممکن برای $n=3$، شکل (۱) است که حسام می‌تواند کارش را مانند شکل (۲) انجام دهد:
تنها حالت ممکن نیز برای $n=4$ شکل (۳) است که حسام می‌تواند کارش را مانند شکل (۴) انجام دهد:
فرض کنید حکم به ازای $<n$ برقرار باشد. ثابت می‌کنیم حکم به ازای $n$ نیز برقرار است. یک درخت $n$ رأسی در نظر بگیرید و آن را ریشه‌دار کنید. چند حالت داریم:
- دو برگ سفید با پدر مشترک داشته باشیم؛ در این صورت روی یکی از آن دو برگ عدد ۱ و روی دیگری $-1$ می‌نویسیم و عدد بقیه‌ی رأس‌های سفید را $0$ می‌گذاریم. تمام شرایط برقرار و کار حسام انجام می‌شود.
- در صورتی که حالت بالا رخ ندهد، پایین‌ترین برگ را در نظر می‌گیریم و آن را $u$ می‌نامیم. دو حالت داریم:
- این برگ سیاه باشد. فرض کنید $v$ پدر رأس $u$ باشد. $v$ را به همراه تمام فرزندان‌ش (از جمله $u$) از درخت حذف می‌کنیم. در درخت باقی‌مانده هم‌چنان تعداد رأس‌های سفید بیش‌تر است. هم‌چنین در درخت باقی‌مانده حداقل سه رأس وجود دارد؛ زیرا پدر $v$ رأسی سیاه است و بنابراین دست کم دو رأس سفید باید در درخت باقی‌مانده موجود باشند. پس درخت باقی‌مانده یک درخت معتبر است و می‌توانیم طبق فرض استقرا آن را به طور معتبر عددگذاری کنیم. حال عدد $v$ را صفر می‌گذاریم. تمام شرایط برقرار و کار حسام انجام می‌شود.
- این برگ سفید باشد. در این صورت فرض کنید پدر $u$ یک رأس سیاه مانند $v$ باشد. $v$ فرزند دیگری ندارد. $u, v$ را از درخت حذف می‌کنیم. یک درخت $n-2$ رأسی معتبر به دست می‌آید و طبق فرض استقرا می‌توان آن را به صورت معتبر عددگذاری کرد. حال فرض کنید عدد پدر رأس $v$ (که رأسی سفید است)، برابر $x$ باشد. عدد رأس $u$ را برابر $-x$ می‌گذاریم. تمام شرایط برقرار و کار حسام انجام می‌شود.