المپدیا

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

ابزار کاربر

ابزار سایت


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

سوال ۱۹

به ازای هر عدد ۷ رقمی در مبنای ۲ که اختلاف تعداد یک‌ها و تعداد صفرهای آن دقیقا برابر یک باشد٬ یک نقطه روی صفحه در نظر می‌گیریم. بین هر دو نقطه که اعداد متناظر با آن‌ها فقط در یک رقم متفاوت باشند٬ یک پاره‌خط رسم می‌کنیم. تعداد این پاره‌خط‌ها چندتاست؟

  1. صفر
  2. ۳۵
  3. ۷۰
  4. ۱۴۰
  5. ۱۲۲۵

پاسخ

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

تعداد اعداد ۷ رقمی در مبنای ۲ که تعداد ۱ های آن‌ها ۴ و تعداد ۰ های آن‌ها ۳ باشد برابر $ \binom{6}{3}$ یعنی ۲۰ می‌باشد(زیرا رقم سمت چپ قطعا ۱ است). این اعداد را دسته‌ی $A$ می‌نامیم.

تعداد اعداد ۷ رقمی در مبنای ۲ که تعداد ۱ های آن‌ها ۳ و تعداد ۰ های آن‌ها ۴ باشد برابر $ \binom{6}{2}$ یعنی ۱۵ می‌باشد(زیرا رقم سمت چپ قطعا ۱ است). این اعداد را دسته‌ی $B$ می‌نامیم.

هر عدد از دسته‌ی $A$ دقیقا به سه عدد از $B$ متصل می‌شود( رقم یک موجود در سمت چپ عدد را صفر کنیم یک عدد از دسته‌ی $B$ تولید می‌شود). بنابراین تعداد کل پاره‌خط‌های تولید شده برابر $20\times3$ یعنی ۶۰ خواهد شد٬ که متاسفانه در گزینه‌ها نیامده است.


ابزار صفحه