Loading [MathJax]/jax/output/HTML-CSS/jax.js

المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره ی تابستان:دوره ی ۲۵:ترکیبیات:سوال ۲

بمب‌های مغولی

زمانی که مغول‌ها به ایران حمله کردند، ایران n اثر تاریخی با شماره‌های 1,2,,n داشت. قیمت اثر شماره d به این شکل مشخص می‌شد که اگر d مقسوم‌علیه n باشد، ارزش آن برابر φ(d)pφ(d) و در غیر این صورت ارزش آن ۰ است (φ تابع فی‌اویلر و 0<p<1 عددی ثابت است).

پس از تسلط مغول‌ها بر ایران، آن‌ها n بمب با شماره‌های 1,2,,n ساختند تا آثار تاریخی را نابود کنند. هر بمب به احتمال 1p عمل می‌کند و منفجر می‌شود. اگر بمب شماره‌ی i منفجر شود، تمام آثار تاریخی با شماره‌ی d که di و (d,i)=1 باشد تخریب می‌شوند. برای مثال اگر n=16 باشد و بمب شماره‌ی ۱۰ منفجر شود، آثار تاریخی شماره ۱۱ و ۱۳ تخریب می‌شوند.

پس از بیرون راندن مغول‌ها، ایرانیان مجموع میزان ارزش آثار تاریخی باقی‌مانده را حساب کردند و آن را ارزش ملی نامیدند. امید ریاضی ارزش ملی باقی‌مانده پس از جنگ چیست؟!


ابزار صفحه