سؤال ۴۰
در یک خانواده‌ی مردسالار مجموعه‌ی «اجداد» یک نفر برابر است با پدر او، پدرِ پدر او و … و مجموعه‌ی «بزرگ‌تر»های یک نفر برابر است با اجداد و برادران اجداد او. در روز عید، بزرگ فامیل که هیچ برادر یا بزرگتری ندارد یک سکه به یکی از پسران خود می‌دهد. هر کس که سکه را دریافت کند یا آن‌را برای خود برمی‌دارد و یا آن را به یکی از پسرانش یا یکی از بزرگ‌ترهایش می‌بخشد. اگر $G$ نام بزرگ فامیل و $P$، $Q$، $R$ ، و $S$ نام ۴ نفر از اعضاء آن فامیل باشد که در یک دور بازی مشارکت داشته‌اند، کدام‌یک از ترتیبات دریافت سکه زیر ممکن نیست؟
- G→P→R→Q→S→R
- G→P→Q→R→S→P
- G→P→Q→R→S→Q→P
- G→P→R→Q→S→R
- G→P→Q→R→S→Q→S
پاسخ
گزینه (۵) درست است.
ابتدا باید توجه کرد که اگر $X$ به $Y$ و نیز $Y$ به $X$ سکه دهد آن‌گاه لازم است $X$ و $Y$ پدر و پسر باشند.
در گزینه «۵» نفرات $Q$ و $S$ پدر و پسر هستند و نمودار نفرات بدون $R$ مطابق شکل مقابل می‌شود. در آن نمودار جایگاه $R$ جایی است که بتوند به $S$ سکه بدهد که با توجه به نمودار٬ فقط می‌تواند پسر $S$ باشد(پدر $Q$،$S$ است و $R$ نمی‌تواند پدر $S$ باشد). اگر $R$ پسر $S$ باشد٬ آن‌گاه $Q$ نمی‌تواند به $R$ سکه بدهد در حالی که یکی از قسمت‌های گزینه «۵» به صورت $Q→R$ می‌باشد. نمودار سایر گزینه‌ها به اشکال زیر می‌تواند باشد:
ابزار صفحه
کلیه‌ی حقوق این سایت متعلق به کمیته‌ی ملی المپیاد کامپیوتر ایران است.
