یک دسته‌ی $n$ تایی سنگریزه موجود است. دو بازیکن بازی زیر را روی سنگریزه‌ها انجام می‌دهند:
در هر نوبت بازیکنی که نوبت حرکت با اوست، یکی از دسته‌ها را انتخاب و آن را به طور دل‌خواه به دو دسته‌ی غیر تهی تقسیم می‌کند. بازیکنی که نتواند حرکتی انجام دهد، بازنده‌ی بازی است.
الف) تمام $n$ هایی را به‌دست آورید که برای آن‌ٰها نفر دوم بتواند طوری بازی کند همیشه برنده شود. ادعای خود را اثبات کنید.
ب) شرط بازی را به این صورت تغییر می‌دهیم که در هر نوبت، بازیکن باید طوری یک دسته را به دو دسته‌ی غیر تهی تقسیم کند که حداقل یکی از این دو دسته، تعداد زوجی سنگریزه داشته باشد. در این صورت هم تمام $n$هایی را به دست آورید که برای آن‌ها نفر دوم بتواند طوری بازی کند که همیشه برنده شود. ادعای خود را اثبات کنید.
پاسخ
الف) در پایان بازی $n$ دسته‌ی ۱ تایی از سنگریزه‌ها باقی خواهد ماند. پس با توجه به این که در هر مرحله از بازی یکی به تعداد دسته‌ها افزوده می‌شود، بدون توجه به نحوه‌ی بازی افراد، بازی $n-1$ مرحله خواهد داشت. پس اگر $n$ زوج باشد، نفر اول و اگر فرد باشد، نفر دوم برنده خواهد شد.
ب) با توجه به این که تعداد دسته‌های شامل تعداد فردی سنگریزه هرگز افزایش نمی‌یابد، اگر $n$ زوج باشد، در آخر بازی $\frac{n}{2}$ دسته‌ی دوتایی و اگر فرد باشد، $\frac{n-1}{2}$ دسته‌ی دوتایی و ۱ دسته‌ی یک عضوی باقی می‌ماند. با این توضیح با فرض این‌که سنگریزه‌ها در بسته‌های دوتایی و حداکثر یک دسته‌ی تک عضوی قرار دارند، بازی عینا به بازی قسمت الف با $\lfloor \frac{n+1}{2} \rfloor$ سنگریزه تبدیل می‌شود. بنابراین اگر $n=4k$ یا $n=4k-1$ باشد، نفر اول و اگر $n=4k+1$ و $n=4k+2$ نفر دوم برنده خواهد شد.