سوال ۳
شکل مقابل از ۱۵ توپ و ۳۰ میله تشکیل شده که هر میله دو توپ را به هم وصل می‌کند و هر توپ به ۴٬۲ یا ۶ توپ دیگر وصل است.
حداقل چند توپ را باید حذف کنیم به طوری که هر یک از توپ‌های باقی‌مانده حداکثر به دو توپ دیگر وصل باشد؟ دقت کنید وقتی یک توپ را حذف کنیم٬ میله‌هایی که یک سرشان این توپ باشد نیز حذف می‌شوند.
- ۸
- ۵
- ۴
- ۶
- ۳
پاسخ
گزینه‌ی (۴) درست است.
۶ توپ لازم و کافی است.
- اثبات لزوم شرط: سه دایره‌ی داخلی را در نظر بگیرید. اگر هرکدام از آن‌ها باقی بماند (مثلا دایره‌ی پایین راست)، باید ۴تا از همسایه‌هایش حذف شوند (اگر هرکدام از دو دایره‌ی داخلی دیگر باقی بماند حداقل ۶ دایره حذف می‌شود). پس از حذف این رئوس ۴ راس با درجه‌ی سه باقی می‌ماند که باید حداقل دو راس دیگر حذف شوند که در نتیجه در مجموع ۶ دایره حذف شد. اگر همه‌ی رئوس میانی نیز حذف شوند ۶ راس درجه‌ی سه باقی مانده که با حذف هر راس حداکثر دو تا از آن‌ها کم می‌شوند. در نتیجه حداقل باید سه راس دیگر حذف شوند.
- اثبات کافی بودن شرط: از مثلث داخلی (به طول دو) که برعکس است تمام رئوس آن را حذف کنید. در نتیجه سه مثلث به طول یک باقی می‌مانند که شرایط مسئله را دارند.