ماراتن ترکیبیات ممتاز

[mojtabaaa1373]

این کتاب که همهی کتاب خونه ها دارن احتیاجی به سرچ نداره اما بازم متشکر.

 

[mahanmath]

سوال 15
At a tourist camp, each person has at least

and at most

friends among the other persons at the camp. Show that one can hand outa t-shirt to every person such that
the t-shirts have (at most)

different colors, and any person has

friends whose t-shirts all have pairwisely different colors.

نمیدونم از کی‌ تا حالا سوال آخر روسیه بدیهی‌ شده ؟

من خودم این سوال با یه راهنمایی و یه قضیه حل کردم و به نظر خودم خیلی‌ سخت بود . پس اگه می‌شه لطف کنید جزئیات اثبات خودتونو بگید
ممنون .

 

[mojtabaaa1373]

ببخشید یکم دیر شد کار پیش اومد
اول عذر می خواهم این سوالی که تو سپهر نوشته بودن اینجوری بود:
می خواست هر دو نفر که با هم دوست هستند حداقل در 20 رنگ متفاوت باشند
اثبات:
استقرا بزنید این طور که به هر کی ده تا رنگ بدید
پایه ی استقرا n<=101
با حداکثر 1010 رنگ میتوان حکم را ثابت کرد
زیرا ما تنها میخواهیم هر فرد وهر یک از دوستانش در حداقل 20 رنگ اختلاف داشته باشند.

 

[erfankh]

این کتاب که همهی کتاب خونه ها دارن احتیاجی به سرچ نداره اما بازم متشکر

والا من تا اون جایی که می دونم کتابش تاسال 1993 هست
اینی که من می گم واسه سال های بعدش تا سال 2009 است

 

[mojtabaaa1373]

راستی اون سوال روسیه اون قدر هم سخت نبود که گفته میشد.
راه حل معمولی داشتش.
سوال بعد:
یه جدول n*n داریم که جومونگ سمت چپ بالاش وایساده و میخواد به سمت راست پایین بیاد k تا سرباز توی جدول طوری وایسادن که بهترین حالت واسه کشتن جومونگ باشه اگه بدونیم یه راهی واسه پیروزی جومونگ وجود دارد و جومونگ یه ماشین زمان داشته باشه که بتونه فقط به اندازه یک خونه زمان رو به عقب برگردونه جومونگ حداقل چند خونه رو باید طی کنه؟

 

[mojtabaaa1373]

سوال آسونی بود چرا کسی هیچی نمی نویسه؟؟؟؟

سوال 17
یه گلادیاتور توی یه میدون داریم که متقارنه و n تا در داره اگه وارد هر کدومشون بشی از یه در درمیای بیرون (همیشه اگه از یه در وارد شی در خروجی یکسانه.)به جز یک در که در نجات نام داره ثابت کنید گلادیاتور میتونه نجات پیدا کنه.

 

[erfankh]

سوال جومونگ شاید بشه k حالا نمی دونم درسته یا نه

 

[mojtabaaa1373]

این کتاب که همهی کتاب خونه ها دارن احتیاجی به سرچ نداره اما بازم متشکر

والا من تا اون جایی که می دونم کتابش تاسال 1993 هست
اینی که من می گم واسه سال های بعدش تا سال 2009 است

ما که هر چی گشتیم نیافتیمش اگه یافتی لینکشو بذارید.

 

[mojtabaaa1373]

سوال جومونگ اشتباه بود درستش کردم excuseme.

 

[rezashiri]

این کتاب که همهی کتاب خونه ها دارن احتیاجی به سرچ نداره اما بازم متشکر

والا من تا اون جایی که می دونم کتابش تاسال 1993 هست
اینی که من می گم واسه سال های بعدش تا سال 2009 است

ما که هر چی گشتیم نیافتیمش اگه یافتی لینکشو بذارید.

چون برای اون سوال نظریه اعداد راهنمایی کردید اینم پاداشتون:

http://www.math.toronto.edu/oz/turgor/archives.php

 

[mojtabaaa1373]

این کتاب که همهی کتاب خونه ها دارن احتیاجی به سرچ نداره اما بازم متشکر

والا من تا اون جایی که می دونم کتابش تاسال 1993 هست
اینی که من می گم واسه سال های بعدش تا سال 2009 است

ما که هر چی گشتیم نیافتیمش اگه یافتی لینکشو بذارید.

چون برای اون سوال نظریه اعداد راهنمایی کردید اینم پاداشتون:

http://www.math.toronto.edu/oz/turgor/archives.php

متشکر پاداش خوبی بود.

 

[erfankh]

سوال جومونگ
شاید بشه حداکثر
2n+2k-1
حداقل
2n-1
شاید هم دوباره اشتباه کرده باشم

 

[mojtabaaa1373]

چرا کسی سوال گلادیاتورو نمی حله؟؟؟

 

[counterexample]

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

 

[mimilad]

خوب ببين در خروجي 2 تا از در ها ميتونه يكسان باشه يانه ؟ ؟ ؟ ؟

 

[mojtabaaa1373]

خوب ببين در خروجي 2 تا از در ها ميتونه يكسان باشه يانه ؟ ؟ ؟ ؟

آره می تونه.

 

[mimilad]

خوب الان چون امتحاناتمون شروع شده ( زياد وقت فكر كردن رو اين سوال را نداشتم )

ولي اگه اشتباه نكنم كافيه يه استراتژي به گلادياتور بديم تا از اين استراتژي پيروي كنه مثلا اين كه در ابتدا از يك در دلخواه وارد شه و از هر در ديگه اي كه خارج شد وارد در سمتچپش بشه و باز از هر دري خارج شد وارد در سمت راستش بشه . حالا اگه گلادياتور از اين استراتژي پيروي كنه حتما ميتونه نجات پيدا كنه .

فكر كنم اين سوال رو هم بشه با استقراي پيچيده هم حل كرد . . ..

 

[mojtabaaa1373]

استراتژیش زیاد سخت نیست اما اینجوری که شما میگینم نیست تمام حالت ها رو چک کنین.

 

[mimilad]

اهان راست ميگي اشكال استراتژي اي رو كه دادم فهميدم حالا يه استراتژي ديگه كه فكر كنم اين عملي است :

يه تابع تعريف ميكنيم واسه استراتژي فرض ميكنيم گلادياتور اول تو خونه ي n باشه و از هر خانه اي كه بيرون امد بره تو خونه ي n-1 و بعد از هر خانه اي كه در اومد بره تو خونه ي n +1 ودر دفعه ي از هر خانه اي كه در امود بره تو خونه يn-2 وبعد از هر جايي كه در اومد بره تو خانه n +2 و تابع رو به همين ترتيب ادامه ميدهيم ميدانيم كه همواره پس از تعدادي عمل به خانه يجديدي خواهيم رفت و هيچگاه همواره در يك تناوب و تكرار خانه ها باقي نخواهيم ماند و از اين نتيجه ميشود كه همواره ميتوان به حالت رسيد كه دراين حالت گلادياتور نجات پيدا خواهد كرد .

 

[mimilad]

يه اشكالي راه حل بالام داره منظورم از n+1 اينه كه از هر خانه اي كه بيرون اومد بره تو خونه ي جلوييش بقيه هم منظورم هين طوري بود .