سوال روز ترکیبیات

[Goharshady]

سلام
با توجه به موفقیت (!) ماراتن ترکیبیات تصمیم گرفتم سوال روز ترکیبیات راه بیندازم. هر روز یک سوال مطرح می شود و سوال باید تا پایان همان روز حل شود. کسی که سوال را مطرح می کند باید قبلا آن را حل کرده باشد و از حل خودش مطمئن باشد زیرا اگر کسی جواب ندهد ، باید خود طراح پاسخ سوال را بگذارد. همه ی قوانین ماراتن ترکیبیات اینجا هم هست ، با این تفاوت که به جای شماره تاریخ می زنیم.
در پست بعدی اولین سوال رو مطرح می کنم.

 

[Goharshady]

سوال بیست و ششم اسفند

سلام

سوال چهارشنبه بیست و ششم اسفندماه 88: (منبع :09 CentroAmerican Oly)

2009 جعبه با شماره های 1 تا 2009 داریم که بعضی از آنها حاوی تعدادی سنگ هستند. دو شخص A و B به نوبت بازی می کنند. A شروع می کند. یک حرکت مورد قبول به این صورت است که تعدادی سنگ از جعبه ی i برداریم و آنها را در جعبه ی i+1 بگذاریم. اگر i=2009 باشد ، سنگهای انتخاب شده از بازی خارج می شوند. کسی که آخرین سنگ را از بازی خارج کند برنده است.
الف) اگر 2009 سنگ در جعبه ی شماره ی 2 باشد و بقیه جعبه ها خالی باشند، برای یکی از بازیکنها استراتژی برد بیابید.
ب) اگر در هر جعبه دقیقا یک سنگ باشد ، برای یکی از بازیکنها استراتژی برد بیابید.

امیدوارم قبل از بیست و ششم اسفند حل بشه!

 

[Olympiad]

الف)
نفر اول تعدادي سنگ داخل جعبه ي سوم ميريزد در اين مرحله نفر دوم بقيه ي سنگهاي موجود در جعبه ي دوم را در داخل جعبه ي سوم ميريزد . همين روند ادامه پيدا ميكند تا جعبه ي 2008 ام، در اين مرحله نفر اول تعدادي سنگ در جعبه ي 2009 ام ميريزد و بعد نفر دوم اين سنگ ريزه هاي موجود در جعبه ي 2009 ام را از بازي خارج ميكند ، بنابر اين نفر دوم استراتژي برد دارد.

 

[Goharshady]

×××متاسفانه صحیح نیست×××

 

[Goharshady]

Re: سوال بیست و ششم اسفند

2009 جعبه با شماره های 1 تا 2009 داریم که بعضی از آنها حاوی تعدادی سنگ هستند. دو شخص A و B به نوبت بازی می کنند. A شروع می کند. یک حرکت مورد قبول به این صورت است که تعدادی سنگ از جعبه ی i برداریم و آنها را در جعبه ی i+1 بگذاریم. اگر i=2009 باشد ، سنگهای انتخاب شده از بازی خارج می شوند. کسی که آخرین سنگ را از بازی خارج کند برنده است.

ب) اگر در هر جعبه دقیقا یک سنگ باشد ، برای یکی از بازیکنها استراتژی برد بیابید.

جواب قسمت ب:
نفر اول استراتژی برد دارد به این صورت:
ابتدا مهره ی 1 را به 2 می برد. نفر دوم یا تعدادی مهره از خانه ای زوج به خانه ای فرد می برد یا بالعکس. این 3 حالت را در نظر می گیریم:

• اگر از زوج به فردی برد که قبلا 1 مهره داشته ، همه ی مهره هایی که در آن خانه ی فرد هستند به غیر از آن یکی را به زوج بعدی می بریم.
• اگر از زوج به فردی برد که قبلا مهره ای نداشته ، همه ی مهره هایی که در آن خانه ی فرد هستند را به زوج بعدی می بریم.
• اگر از فرد به زوج برد ، فرد دیگری را به زوج می بریم. (اولویت با 2009 است!!)

خودتان تحقیق کنید که چرا جواب می دهد.
تو مث لینکس تقریبا 10 تا راه حل برای این نوشته بودند ولی من راه خودم رو ترجیح می دهم.!

 

[Goharshady]

سوال بیست و هفت اسفند

سوال بيست و هفتم اسفند 88: (منبع: المپياد رياضي گرجستان _ انتخابي تيم ملي_ 2005)

سي دانش آموز در المپياد رياضي گرجستان (انتخابي تيم ملي) شرکت کردند. 8 سوال به آنها داده شد تا حل کنند. اين قوانين بر امتحان حاکم بود:
الف) هر مسئله k امتياز دارد اگر و تنها اگر توسط دقيقا k دانش آموز حل نشده باشد.
ب) هر دانش آموز از هر مسئله يا نمره ي کامل مي گيرد يا صفر!

اصغر (!) کمترين امتياز را گرفت. بيشترين (Maximal) نمره اي که اصغر ممکن است گرفته باشد را بيابيد.

 

[Goharshady]

[center:f1cc8bab15]سوال بیست و ششم اسفند[/center:f1cc8bab15]

الف)
نفر اول تعدادي سنگ داخل جعبه ي سوم ميريزد در اين مرحله نفر دوم بقيه ي سنگهاي موجود در جعبه ي دوم را در داخل جعبه ي سوم ميريزد . همين روند ادامه پيدا ميكند تا جعبه ي 2008 ام، در اين مرحله نفر اول تعدادي سنگ در جعبه ي 2009 ام ميريزد و بعد نفر دوم اين سنگ ريزه هاي موجود در جعبه ي 2009 ام را از بازي خارج ميكند ، بنابر اين نفر دوم استراتژي برد دارد.

من باز هم اشتباه همیشگی خودم را کردم!!
هیچ وقت نباید بدون فکر کردن کافی چیزی را تایید کنم!!
متاسفانه این راه حل اشتباه است! چون ممکن است نفر اول همه ی سنگها را جا به جا کند!

راه حل صحیح:
اگر نفر اول k سنگ را از i به i+1 برد ، نفر دوم هم همان k سنگ را از i+1 به i+2 می برد.

از همه مخصوصا آقا حسام معذرت می خواهم!

 

[aakkaakk]

لطفا مهلت را تمدید کنید!

 

[Goharshady]

OK
تمدید شد!
آخرین مهلت پاسخگویی : پایان روز شنبه 29 اسفند ماه

 

[mohammad2004]

تو سوال آخر اگه سوال i ام رو

نفر حل کرده باشن ، مجموع امتیازای همه میشه :

حالا امتیاز نفر آخر وقتی حداکثر میشه که امتیاز همه مساوی باشه و مجموع امتیازا بیشترین مقدار ممکن باشه. برای این کار هر نفر باید دقیقا 4 سوال حل کرده باشه و هر سوال باید دقیقا توسط 15 نفر حل شده باشه که میشه این کارو انجام داد به این صورت : سوال 1 تا 4 رو هر کدوم از نفرات 1 تا 15 حل کرده باشن و سوال 5 تا 8 رو هر کدوم از نفرات 16 تا 30 حل کرده باشن. اینطوری امتیاز نفر آخر میشه 120

 

[Goharshady]

حالا امتیاز نفر آخر وقتی حداکثر میشه که امتیاز همه مساوی باشه و مجموع امتیازا بیشترین مقدار ممکن باشه.

اینو باید ثابت کنید هر چند که بدیهی به نظر می رسه

 

[mohammad2004]

خوب واسه اثبات اینم اگر مجموع یه سری عدد ثابت باشه کوچکترینشون (چون از همه کوچیکتره ) از میانگین کلشون کمتر مساویه و حالت تساوی فقط وقتیه که همه عددا برابر باشن

 

[Goharshady]

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

 

[Goharshady]

سوال دوم فروردین

سلام
سال نو مبارک، در این سال تلاش و همت و کارتان را مضاعف کنید تا بیشتر مسئله حل کنیم.

سوال دوشنبه دوم فروردین 1389:
دو نفر با هم بازی می کنند. در ابتدا دو عدد روی تخته می نویسند که مجموع آنها از 128 کمتر است. هر نفر در نوبت خود می تواند از هر کدام از اعداد به هر اندازه که می خواهد کم کند. استراتژی برد با کیست؟ فرض کنید نفر بازنده در صورتی امتیاز بگیرد که دیرتر ببازد ، نفر بازنده حداکثر چند حرکت می تواند انجام دهد؟

 

[SABB]

اگه منظور از بازنده کسی است که نتواند حرکتی انجام دهد، نفر اول استراتژی برد دارد.
او ابتدا با برداشتن مقداری از عدد بزرگتر آن دو عدد را مساوی می کند و سپس قرینه ای بازی می کند.
***
فکر کنم اگه یکی از عددها 64 و اون یکی 63 باشه نفر دوم میتونه 63 تا حرکت کنه.

 

[Goharshady]

درسته!(البته فقط قسمتی که گفته بودید کی برنده می شه)
ولی لطفا حالتی را که دو عدد برابر باشند هم بررسی کنید.

ضمنا جواب شما درباره ی بیشترین حرکتهای ممکن غلط است!

 

[Goharshady]

این بازی در حقیقت نیم است>>>>توضیح بیشتر

 

[Goharshady]

سوال سه شنبه 17 فروردین 1389:
کلاسی 32 نفره را به 33 گروه 3 نفره ی متفاوت تقسیم کرده ایم. ثابت کنید دو گروه وجود دارند که دقیقا یک عضو مشترک دارند.

 

[shoki]

شرمنده که دو باره ارسالم رو پاک کردم ... نمی دونم چرا این قدر ترکیبیاتم می لنگه ....

اگر دو گروه الف و ب داراری اشتراک باشند اشتراگشون دقیقا توی 2 تا عضو هست . اون وقت می شه اثبات کرد که اگر a,b,c اعضای الف باشند و b,c,d اعضای ب باشند آنگاه اگر گروه ج با یک کدومشون مثلا الف دارای اشتراک باشد آنگاه یا داریم ج : b,c,e یا ج : a,b,d . که اگر اولی درست باشد آنگاه می توان به راحتی اثبات کرد که هر مجمو عه ی دیگری که بخواهد با یکی از آن ها اشتراک داشته باشد دقیقا در b,c با ان ها اشتراک دارد . و اگر دومی درست باشد دوباره به راحتی اثبات می شود که اگر گروه د با یکی از آن ها در اشتراک با شد آنگاه د : c,d,a . باقیش به راحتی حله ... چون گروه ها به چند دسته تقسیم می شند و سه نوع دسته هم داریم :
یکی اونی که زیر مجموعه های 3 عضوی یک مجموعه ی 4 عضوییه . و دیگری اونی که m تا مجموعه ی 3 عضوی داره که همشون توی 2 تا عضو مشترکند و در سومین عضو متفاوتند . و در نهایت اون مجموعه هایی که با هیچی اشتراک ندارند . حالا کافیه یه بار تعداد گروه ها و یه بار تعداد افراد رو بشماریم تا به تناقض برسیم ...

 

[Goharshady]

سوال چهارشنبه 18 فروردین 1389:
ثابت کنید حاصل جمع هیچ دو مربع کامل فردی ، مربع کامل نمی شود.