المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:مرحله ی اول:دوره ی ۷:سوال ۴۹

سوال ۴۹

آیا می‌توان عددهای صفر تا ۱۲۷ را به دو دسته چنان تقسیم کرد که هر دو عددی که نمایش آن‌ها در مبنای دو دقیقا در یک رقم با هم تفاوت دارند در یک دسته نباشند؟

پاسخ

اعداد از صفر تا ۱۲۷ در مبنای ۲ به صورت ۰۰۰۰۰۰۰ تا ۱۱۱۱۱۱۱ نمایش داده می‌شوند. به‌جای نوشتن این ۱۲۸ عدد به ترتیب صعودی٬ کافی است آنان را چنان نوشت که هر دو عدد متوالی دقیقا در یک رقم متفاوت باشند. در این صورت اگر اعداد به‌دست آمده یک در میان در یک رقم متفاوت باشند در این صورت اگر اعداد به‌دست‌آمده یک در‌ میان در یک دسته و باقی‌مانده اعداد را در دسته دیگر قرار دهیم مسلم است که در یک دسته هیچ دو عدد پیدا نمی‌شود که دقیقا در یک رقم باهم تفاوت داشته باشند. یا به طریق دیگر می‌توان مسئله را بیان کرد به این صورت که اعدادی که دارای تعداد زوجی «۱» هستند را در یک دسته و اعدادی که دارای تعداد فردی «۱» هستند را در دسته دیگر قرار می‌دهیم. بدیهی است که در یک دسته هرگز دو عدد نمی‌توان یافت که دقیقا در یک رقم با هم تفاوت داشته باشند. زیرا چنین دو عددی در تعداد یک‌هایشان فقط یک واحد اختلاف دارند.


ابزار صفحه