سوالات المپیاد:مرحله ی اول:دوره ی ۲۸:سوال ۸
سوال ۸
نقشه‌ی یک موزه به شکل زیر است:
هر یک از نقاط پایینی یک در ورودی هستند و یک گنج در رأس بالا قرار دارد. دو نقطه که با پاره‌خط به هم وصل هستند، به هم راه مستقیم دارند. ایلیچ می‌تواند از یک در ورودی وارد شده و با حرکت در موزه به گنج برسد. برای سرعت دادن به کار، ایلیچ از هر نقطه حداکثر یک بار عبور می‌کند. به چند طریق می‌توان در نقاط شکل دوربین قرار داد، طوری که ایلیچ از هر مسیری که به گنج برسد، توسط دقیقاً یک دوربین دیده شود؟
- ۶۷۷
- ۲۶
- ۶۴
- ۶۲۶
- ۱۰۲۴
پاسخ
گزینه‌ی ۱ درست است.
اگر $f_n$ پاسخ برای درختی به ارتفاع $n$ رأس باشد، با حالت‌بندی بر روی این که ریشه دوربین دارد یا نه، داریم: $$f_n=1+f_{n-1} \times f_{n-1}$$ از آن‌جایی که $f_1=1$، پاسخ مسئله برابر $f_5=677$ است.
ابزار صفحه
کلیه‌ی حقوق این سایت متعلق به کمیته‌ی ملی المپیاد کامپیوتر ایران است.
