سوال ۱۱

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

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

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

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

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

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

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

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

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

• سوال قبل
• سوال بعد