المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:مرحله ی اول:دوره ی ۲۰:سوال ۴

سوال ۴

سعید و حسام بازی زیر را انجام می‌دهند. ابتدا٬ سعید یک عدد طبیعی و دو رقمی $n$ را نزد خودش انتخاب می‌کند. پس از آن و در هر مرحله٬ حسام یک عدد طبیعی یک‌رقمی مثل $k$ به همراه یک بطری نوشابه به سعید می‌دهد و سعید در ازای آن٬ باقی‌مانده‌ی تقسیم عدد $n$ (عدد خودش) بر عدد $k$ را به حسام می‌گوید.

فرض کنید حسام به اندازه‌ی کافی باهوش است. او در ابتدای کار حداقل چند بطری نوشابه باید همراه داشته باشد تا مطمئن شود که با آن تعداد بطری٬ همواره می‌تواند عدد سعید را حدس بزند؟

  1. ۲ بطری
  2. ۳ بطری
  3. ۴ بطری
  4. ۵ بطری
  5. ۹ بطری

پاسخ

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

طبق قضیه‌ی باقی‌مانده‌ی چینی اگر اعداد صحیح دو به دو نسبت به هم اول $n_1$ تا $n_k$ برای دستگاه معادلات زیر وجود داشته باشند آن‌گاه جواب‌های $x$ به پیمانه‌ی $N=∏_1^kn_i$ با یک‌دیگر برابرند.

$$x \equiv {a_1} \pmod {n_1}$$

$$x \equiv {a_2} \pmod {n_2}$$

$$\vdots$$

$$x \equiv {a_k} \pmod {n_k}$$

با این توضیح، باید ضرب اعداد اولیه بزرگ‌تر از $100$ باشد. در غیر این‌صورت دو عدد با باقی‌مانده‌های یکسان یافت می‌شوند و درنتیجه تشخیص عدد ممکن نیست. چون تمامی اعداد تک‌رقمی هستند حداقل سه عدد لازم است و اعداد ۷، ۸ و ۹ ویژگی مورد نظر ما را دارند. در نتیجه پاسخ گزینه‌ی ۲ است.


ابزار صفحه