اصل لانه کبوتری : جعبه ها

Question

دو n کادر پشت سر هم با اعداد یک تا دو n شماره گذاری شده اند. در هر یک از دو جعبه n و دو n منهای یک، یک قطعه وجود دارد. او یکی از قطعات را از یک جعبه برمی دارد و در یک جعبه خالی با عدد کوچکتر می گذارد. کسی که نتواند به نوبه خود حرکتی انجام دهد بازنده است. ثابت کنید که بازیکن دوم همیشه می تواند به گونه ای بازی کند که برنده باشد

Comments

ببخشید سوال برایم گنگ می باشه، ممکنه بیشتر توضیح دهید.

Answer 1

میتوان برای فهم آسان‌تر متن سوال را اینگونه بیان کرد:

دو بازیکن و دو عدد $a=n$ و $b=2n-1$ داریم$(n\in\mathbb{N} \space | \space n>2)$.

در هر مرحله بازیکنان به نوبت یکی از اعداد $a$ و $b$ را انتخاب کرده و آن عدد را به عددی مثبت و کوچک‌تر از خود آن عدد انتخاب شده تبدیل میکنند بطوری که بعد از انجام این عملیات $a\neq b$.

به صورت رسمی‌تر در هر مرحله یکی از اعداد$a$ و $b$ را(فرضا $a$) به‌همراه $k(k\in\mathbb{N})$ انتخاب کرده بطوری‌که $k$ شروط زیر را رعایت کند:

$1.\space\space 1\leq k< a$

$2.\space\space a-k\neq b$

و سپس $k $ را از آن عدد انتخاب شده کم میکنیم.

بازیکنی که نتواند در نوبت خود عددی را تغییر دهد(اگر در نوبت او هیچ $k$ مناسبی که شروط رو رعایت کند وجود نداشته باشد) بازنده است.

اثبات کنید بازیکن دوم استراتژی برد دارد.