المپدیا

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

ابزار کاربر

ابزار سایت


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

سوال ۱۳

به یک مجموعه از اعداد شکننده گوییم، اگر بتوان اعداد آن را به دو مجموعه افراز کرد، طوری که مجموع اعداد آن‌ها برابر باشد. چند تا از مجموعه‌های زیر شکننده هستند؟ $$A = \{1, 2, \ldots, 100\} \qquad B = \{2, 4, \ldots, 100\} \qquad C = \{1, 3, \ldots, 99 \} \qquad \ D = \{\frac{1}{1}, \frac{1}{2}, \ldots, \frac{1}{100}\}$$

  1. ۰
  2. ۱
  3. ۲
  4. ۳
  5. ۴

پاسخ

گزینه‌ی ۳ درست است.

  • مجموعه‌ی $A$ شکننده است. اعداد به صورت $4k+1$ و $4k$ را در یک دسته و بقیه‌ی اعداد را در دسته‌ی دیگر می‌گذاریم.
  • مجموعه‌ی $B$ شکننده نیست. فرض کنید مجموعه‌ی $B$ به دو دسته‌ی $X$ و $Y$ تقسیم شود. در این صورت اگر تمام اعداد $X$ و $Y$ را تقسیم بر دو کنیم، باز هم مجموع $X$ و $Y$ یکسان می‌ماند. در نتیجه باید مجموعه‌ی $\{1, 2, \ldots, 50\}$ هم شکننده باشد، در حالی که مجموع اعداد آن فرد است و این امر ممکن نیست.
  • مجموعه‌ی $C$ شکننده است. می‌توانیم آن را به دو دسته‌ی $$X = \{1, 3, 5, 9\} \cup \{13, 19, 21, 27, \ldots, 93, 99\}$$ و $$Y = \{7, 11\} \cup \{15, 17, 23, 25, \ldots, 95, 97\}$$ افراز کنیم.
  • مجموعه‌ی $D$ شکننده نیست. فرض کنید مجموعه‌ی $D$ به دو دسته‌ی $X$ و $Y$ تقسیم شود. ک.م.م اعداد ۱ تا ۱۰۰ را $L$ در نظر بگیرید. همه‌ی اعداد $X$ و $Y$ را در $L$ ضرب کنید. تمام اعداد به جز $\frac{1}{64}$ پس از این عمل زوج می‌شوند و تنها یک عدد فرد ($\frac{L}{64}$) به وجود می‌آید. پس مجموع یکی از $X$ و $Y$ زوج و دیگری فرد می‌شود که تناقض است.

ابزار صفحه