مساله‌های استقرا سری۲

۲- در یک ردیف n تا لامپ داریم که در آغاز همگی خاموش هستند. کلید هر لامپ در کنار آن هست ولی برخی از این کلیدها تنها گاهی کار می‌کنند.
کلید نخستین لامپ همیشه کار می‌کند و هر گاه بخواهیم لامپ نخست را روشن یا خاموش می‌کند.
کلید دومین لامپ می‌تواند آن را روشن یا خاموش کند اگر و تنها اگر لامپ نخست خاموش باشد و در غیر این صورت هیچ کاری نمی‌کند.
به ازای هر p طبیعی که از 2 بزرگ‌تر باشد، کلید p ام لامپ p ام را می‌تواند روشن یا خاموش کند اگر و تنها اگر لامپ p-1 ام خاموش باشد و همه‌ی لامپ‌های 1 تا p-2 روشن باشند و در غیر این صورت هیچ کاری نمی‌کند.
ثابت کنید روشی هست که بتوانیم همه‌ی لامپ‌ها را روشن کنیم.

۳- در یک دوره مسابقه‌ی ورزشی که n ورزشکار (n دست کم 2 است.) شرکت دارند، هر دو تیم درست یک بار با هم رقابت کرده‌اند و نتیجه‌ی هر رقابت نیز تنها برد یک ورزشکار و باخت دیگری است. (در این دوره از مسلبقات نتیجه‌ی هیچ رقابتی تساوی نیست.)
الف) ثابت کنید می‌توان دنباله‌ای مانند (a₁, a₂, a₃, ..., a_n) از ورزشکارها یافت، جوری که به ازای هر k طبیعی کوجک‌تر از n حتما a_k از a_k+1 برده باشد.
ب) ثابت کنید ورزشکاری مثلا به نام a هست که هر ورزشکار دیگری مثلا به نام b را شکست داده است یا اگر از او باخته است، حتما ورزشکار دیگری مانند c را شکست داده است که c ورزشکار b را شکست داده است.
پ) گیریم که در این دوره از مسابقه‌ها ورزشکاری به نام s داشته باشیم که برای هر ورزشکار دیگری به نام u (از همین ورزشکاران این دوره) بنوان دنباله‌ای به طول m (m می‌تواند صفر باشد.) مانند (a₁, a₂, a₃, ..., a_m) یافت به گونه‌ای که s از a₁ برده باشد و برای هر i طبیعی کوچک‌تر از m ورزشکار a_i از ورزشکار a_i+1 برده باشد و a_m نیز از u برده باشد.
ثابت کنید همه‌ی ورزشکارها را می‌توان در دنباله‌ای مانند دنباله‌های بخش الف چید به گونه‌ای که حتما نخستین ورزشکار همین s باشد.
ت) از همه‌ی دنباله‌های ممکن در بخش الف، نخستین ورزشکار دنباله یعنی a₁ها را در یک مجموعه به نام A بریزید. ثابت کنید در همه‌ی دنباله‌های ممکن در بخش الف، هر یک از عضوهای مجموعه‌ی A حتما پیش از ورزشکارانی ظاهر می‌شوند که در A نیستند.

۴- تعداد سرباز در یک ردیف ایستاده‌اند. برخی از آن‌ها در صف رو به سمت چپ هستند و برخی رو به سمت راست. از این پس هر ثانیه که بگذرد، هر دو سربازی که رو به روی هم باشند و یکدیگر را ببیند، عقبگرد می‌کنند. ثابت کنید پس از مدت زمانی حتما این گروه سرباز بی‌حرکت خواهند ماند.

۵- دو مجموعه‌ی متناهی و جدا از هم به نام‌های A و B هر دو زیرمجموعه‌ای از عددهای صحیح هستند و می‌دانیم اگر u عضوی از اجتماع این دو مجموعه باشد آن گاه u+1 عضو A است یا u-2 عضو B است. ثابت کنید تعداد عضوهای A دو برابر تعداد عضوهای B است.

۶- یک صفحه‌ی شطرنج 4n+1 در 4n+1 داریم. ثابت کنید می‌توان مسیری پیدا کرد که مهره‌ی اسب شطرنج این مسیر را با حرکت‌های مجاز بپیماید و از همه‌ی خانه‌ها بگذرد و نیز از هر خانه تنها یک بار بگذرد.