سوال ۱۱

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

ایلیچ به سلطان برای ساختن $n$ دست لباس، الگوریتم زیر را پیشنهاد داده است:

«تا زمانی که می‌توانیم با دست‌کش‌ها، کلاه‌ها و شال‌گردن‌های موجود یک دست لباس ۳ امتیازی دل‌خواه می‌سازیم. سپس تا زمانی که می‌توانیم یک دست لباس ۲ امتیازی دل‌خواه می‌سازیم و در انتها دست‌های ۱ امتیازی تشکیل می‌دهیم.»

از میان گزاره‌های زیر، کدام گزاره یا گزاره‌ها صحیح هستند؟

آ) الگوریتم ایلیچ هم‌واره سلطان را به هدف‌ش می‌رساند؛ یعنی بیشینه‌ی مجموع امتیاز ممکن را می‌سازد.

ب) اگر در میان $3n$ عنصر موجود از هر رنگ $n$ عنصر داشته باشیم، می‌توان $n$ دست لباس با مجموع امتیاز $3n$ ساخت.

ج) اگر در میان $3n$ عنصر موجود از هر رنگ $n$ عنصر داشته باشیم، الگوریتم ایلیچ بیشینه‌ی مجموع امتیاز ممکن را می‌سازد.

د) اگر دست 3 امتیازی قابل ساخت نباشد و هم‌چنین دست‌کش‌ها از دقیقن دو رنگ، کلاه‌ها از دقیقن دو رنگ و شال‌گردن‌ها نیز از دقیقن دو رنگ باشند، می‌توان نتیجه گرفت که $3n$ عنصر موجود دقیقن از دو رنگ هستند.

  1. هیچ کدام از گزاره‌ها
  2. گزاره‌های ب، ج و د
  3. گزاره‌های ب و د
  4. فقط گزاره‌ی د
  5. تمام گزاره‌ها

پاسخ

گزینه (۲) درست است.

گزاره‌ی (آ) غلط است. فرض کنید $n=2$ باشد و یک دست‌کش آبی و یک کلاه آبی داریم و بقیه‌ی عناصر قرمز هستند. در این صورت ما می‌توانیم در انتها چهار امتیاز داشته باشیم، امّا در الگوریتم ایلیچ ممکن است در مرحله‌ی اول دو عنصر آبی به همراه یک شال‌گردن قرمز برداشته شود و در مرحله‌ی دوم یک دست با عناصر قرمز برداریم که در انتها ۳ امتیاز خواهیم داشت. پس الگوریتم ایلیچ لزومن درست کار نمی‌کند.

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

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