المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


سوالات المپیاد:مرحله‌ی دوم:دوره‌ی ۱۱:سوال ۳

پادگان نظامی

در یک پادگان نظامی، $n$ فرمانده و $n^2$ سرباز حضور دارند. برای اجرا یک عملیات علیه دشمن، باید گروهی از همه‌ی فرماندها وتعداد دل‌خواهی سرباز تشکیل شود. برای شناسایی افراد این گروه، به هر کدام از آن‌ها یک کد عملیاتی تخصیص داده می‌شود. کد هر فرد، یک عدد طبیعی است و کد هیچ دو نفری یکسان نیست. به خاطر مسایل امنیتی کدها با این شرط انتخاب می‌شوند: برای هر دو فرد $A$ و $B$ عضو گروه با کدهای $a$ و $b$، عدد $a+b$ کد یکی دیگر از اعضای گروه است اگر و تنها اگر $A$ و $B$ هر دو فرمانده باشند (توضیح آن که به غیر از اعضای گروه، به کسی کد داده نمی‌شود).

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

ب) نشان دهید در هر کدگذاری درست با $n\geq 4$ فرمانده، ۳ فرمانده‌ی $A،B$ و $C$ با کدهای $a،b$ و $c$ وجود ندارند که $a+b=c$.


ابزار صفحه