تعویض اتاق (۱۸ نمره)‌

یک هتل دارای $n$ اتاق است و در هر اتاق آن، دقیقاً یک نفر حضور دارد. در هر مرحله می‌توانیم دو اتاق را انتخاب کرده و افراد داخل آن‌ها را با هم جابه‌جا کنیم. در هر جابه‌جایی، هیچ کدام از دو نفر نباید به اتاقی برود که در یکی از مراحل قبلی در آن حضور داشته است. هدف این است که هر فرد، حضور در هر یک از $n$ اتاق هتل را تجربه کند. اگر این کار امکان‌پذیر باشد، می‌گوییم $n$ عددی «کامل» است. برای مثال، $2$ عددی کامل است؛ زیرا اگر $n=2$ باشد، با یک جابه‌جایی به هدفمان می‌رسیم. هم‌چنین می‌توان نشان داد که $3$ عدد کاملی نیست.

فرض کنید اعداد طبیعی $m$ و $n$ هردو کامل باشند. در این صورت ثابت کنید حاصل‌ضرب آن‌ها (یعنی عدد $mn$) نیز کامل است. برای گرفتن $5$ امتیاز از این سوال، کافی است نشان دهید که اگر $n$ عددی کامل باشد، آن‌گاه $2n$ نیز عددی کامل است.