۱۴۰۰ نفر از سه کشور مختلف داریم. هدف جبارزید یافتن سه نفر از این افراد است که از سه کشور متمایز باشند. جبارزید تعداد افراد هر کشور را نمی‌داند و فقط می داند که این ۱۴۰۰ نفر، از سه کشور مختلف هستند و از هر کشور حداقل یک نفر وجود دارد. او در هر مرحله می‌تواند تعدادی از این افراد را انتخاب کند و به استاد نشان دهد تا استاد در جواب، عددی بین یک تا سه بگوید که مشخص می‌کند این افراد از چند کشور مختلف هستند. جبارزید میخواهد با کمترین تعداد مرحله به هدف خود برسد.

الف) ثابت کنید جبارزید می‌تواند این کار را در حداکثر ۲۳ مرحله (یا حتی کمتر!) انجام دهد. (۱۴نمره)

ب) ثابت کنید جبارزید نمی‌تواند در کمتر از ۱۲ مرحله به هدف خود برسد. (۱۴نمره)

توضیح برای بخش ب: اگر ثابت کنید جبارزید در کمتر از ۱۱ مرحله نمی‌تواند این کار را انجام دهد ۸ نمره از ۱۴ نمره‌ی بخش را می‌گیرید و اگر ثابت کنید در کمتر از ۱۰ مرحله نمی‌تواند این کار را انجام دهد ۶ نمره از بخش را دریافت می‌کنید.

• سوال قبل