فهرست مندرجات
سوالات ۱۷ و ۱۸
در شهر یاخچی‌آباد، هر خانه به صورت یک نقطه است که یک خانواده در آن زندگی می‌کند. فاصله‌ی نزدیک‌ترین خانه به هر خانه را شعاع همسایگی آن خانه می‌نامند. فاصله‌ی دو خانه برابر است با طول پاره‌خط واصل نقاط متناظرشان.
هر خانواده تمامی خانواده‌هایی را که در شعاع همسایگی‌اش باشند، همسایه‌ی خود می‌داند. دو خانواده صمیمی هستند اگر هر یک دیگری را همسایه‌ی خود بداند. تعداد جفت خانواده‌های صمیمی در یک محله صمیمی آن محله محسوب می‌شود.
شهردار یاخچی‌آباد قصد دارد یک محله‌ی جدید با ۹۱~خانه تاسیس کند.
سوال ۱۷
شهردار که می‌داند صمیمیت زیاد افراد می‌تواند برای قدرت او تهدید به حساب آید، می‌خواهد صمیمیت این محله کمترین مقدار ممکن را داشته باشد. این مقدار چه‌قدر است؟
- 1
- 0
- 45
- 90
- 2
پاسخ
گزینه (۱) درست است.
کمترین مقدار، ۱ است. اگر بین تمام جفت خانواده‌ها، آن دو خانواده‌ای که به هم نزدیک‌تر هستند را در نظر بگیریم .آن دو خانواده ، قطعا با هم صمیمی هستند. پس جواب حداقل ۱ می‌باشد. همچنین اگر خانواده‌ها را روی محور $x$ در نقاط $1, 2, 4, 8, ... 2^{91}$ قرار دهیم، تنها دو خانواده‌ی اول صمیمی هستند. پس جواب دقیقا یک می‌باشد.
سوال ۱۸
معاون شهردار در راستای راهبرد و برنامه‌ی سیاسی خویش، می‌خواهد نقشه‌ای پیشنهاد بدهد که صمیمیت این محله بیشترین مقدار ممکن را داشته باشد. اگر این مقدار $x$ باشد، چه تعداد از گزاره‌های زیر درست است؟
- $x \ge 80$
- $x \ge 160$
- $x \ge 240$
- $x \ge 320$
- 3
- 1
- 2
- 0
- 4
پاسخ
گزینه (۱) درست است.
- 91
- 156
- 179
- 234
- 240
می‌دانیم هر خانواده حداکثر می‌تواند با ۶ خانواده صمیمی باشد. فرض کنید خانواده‌ای بیش از ۶ همسایه صمیمی داشته باشد و آن را $c$ می‌نامیم، یک دایره به مرکز این خانواده و با شعاع همسایگی رسم کنید. واضح است که بیش از ۶ نقطه روی این دایره است پس زاویه بین دو تا از این خانه ها کمتر از ۶۰ می‌باشد پس $c$ نمی‌تواند با این دو خانواده صمیمی باشد. بنابرین حداکثر $\frac{91 \times 6}{2} = 273$ جفت خانواده صمیمی وجود دارد (با گراف مسطح نیز می‌توان این قسمت را اثبات کرد).
در شکل زیر بین هر جفت خانواده صمیمی یک خط کشیده شده است و ۲۴۰ جفت خانواده صمیمی وجود دارد. پس می‌تواند گفت که ۳ تا از ۴ گزاره ذکر شده صحیح می‌باشد.
ابزار صفحه
کلیه‌ی حقوق این سایت متعلق به کمیته‌ی ملی المپیاد کامپیوتر ایران است.
