سه نفر با شمارههای ۱، ۲ و ۳ دور دایره نشستهاند و با هم بازی میکنند. هر نفر دو کارت دارد که شمارهی افراد دیگر به جز خودش روی آنها نوشته شده است. بازی از فرد با شمارهی ۱ شروع میشود. هر نفر در نوبت خود، از میان کارتهایی که در حال حاضر در اختیار دارد، یک کارت را بهصورت تصادفی (با احتمال یکسان) انتخاب میکند و نوبت را به فردی که شمارهاش روی کارت منتخب آمده است میدهد و آن کارت را دور میاندازد. بازی زمانی پایان مییابد که فردی که نوبتش است، هیچ کارتی نداشته باشد. پس از پایان بازی، امید ریاضی تعداد کل کارتهای دور انداخته شده چهقدر است؟
راهنمایی
حالتهای مختلف تعداد مراحل بازی را به دست آورید.
راهنمایی
نشان دهید بازی در نوبت نفر اول پایان مییابد.
راهنمایی
بازی را میتوان به گرافی جهتدار مدل کرد. معادل هر فرد یک رأس و معادل هر مرحلهی ممکن یک یال جهتدار داریم (که نوبت از فرد شماره $i$ به فرد شماره $j$ میرسد). نشان دهید بازی یک گذر بسته خواهد بود.