المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره ی تابستان:دوره ی ۱۹:تئوری:سوال ۱۲

سوال ۱۲

یک گراف به صورت دور ‎۱۰۰‎ راسی داریم که راس‌های آن به ترتیب از ‎۱‎ تا ‎۱۰۰‎ شماره گذاری شده‌اند. در ابتدای بازی یک مهره روی راس شماره ‎۱‎ قرار دارد. در هر حرکت به احتمال ‎$\frac{1}{2}$‎ مهره را از طریق یال سمت چپ و به احتمال ‎$\frac{1}{2}$‎ از طریق یال سمت راست به راس مجاور منتقل می‌کنیم. بازی درست در لحظه‌ای که مهره حداقل یک بار روی هر راس قرار گرفته باشد، متوقف می‌شود. به وضوح با پایان بازی مهره دقیقا از ‎۹۹‎ یال حداقل یک بار عبور کرده است و از دقیقا یک یال عبور نکرده است. احتمال آن که یال باقی‌مانده بین دو راس ‎۵۰‎ و ‎۵۱‎ باشد چند برابر احتمال آن است که یال باقی‌مانده بین دو راس ‎۱‎ و ‎۲‎ باشد؟ دلیل خود را ذکر کنید.


ابزار صفحه