سوال مسابقات شریف

[asadh]

سلام
سوال زیر را جواب دهید. سوال مسابقات شریف است. حتما روی آن فکر کنید. سوال قشنگی است. جوابش را سه شنبه می گذارم.
k مهره روی یک میز در یک دسته قرار دارند. قانون بازی این گونه است که در هر حرکت از یک دسته که بیش از یک مهره دارد یک مهره دور انداخته شده و یک دسته که بیش از یک مهره دارد را ه دو بخش نا تهی تقسیم کرد. کوچکترین k بزرگ تر از1388 را طوری بیابید که پس از چند حرکت تنها دسته های سه تایی داشته باشیم.

 

[HADI88]

سلام دوس عزیز این سوال المپیاد صنعتی شریف بود که من حل کردم .

کوچکترین عدد بزرگتر از 1388 که در این شرط صدق می کند 1391 می باشد. با توجه به روش بازی 1 مهره را حذف می کنیم. 1390 مهره باقیمانده را به دودسته ی س تایی و 1387 تایی تقسیم می کنیم ، اکنون عمل بالا را برای 1387 انجام می دهیم. بعد از 347 مرتبه ، 348 دسته ی سه تایی داریم و 347 مهره هم حذف می شود .

1391=348×3+347

 

[asadh]

دوست عزیز
جوابت درست است اما تو از جواب راه حل داری اما باید فرض کرد جواب را نداریم و مسئله را حل کنیم.
از k یک مهره برمی داریم. می شود:k-1 سپس آن را به دودسته ی 3 و k-4 تبدیل می کنیم. از k-4 یک برمی داریم و می شود: k-5 دوباره آن را به دو قسمت 3 و k-8 تقسیم می کنیم. همین گونه ادامه می دهیم. دسته ها به ترتیب k-4 * k-8 * k-12 می شوند وتا k-4n ادامه دارند. می دانیم k-4n باید برابر با 3 باشد تا دسته ها سه تایی شوند. بنابراین k برابر با 4n+3 است. چون 1388 بر 4 بخش پذیر است پس 4n همان 1388 است و جمع آن با 3 برابر 1391 است.