اولین باره که به کاهو میای؟ راهنمای سایت رو حتما بخون!

ورود ثبت‌نام راهنما درباره‌ی کاهو
پرسش‌ها برچسب‌ها کاربر‌ها سوال بپرسید!

آمار پرسش:

  • پرسیده شده: 2014-06-09 02:08:37 -0500
  • مشاهده شده: 987 بار
  • بروز شده: 2014-06-10 06:35:25 -0500

پرسش‌های مشابه:

بازی که با مهره انجام می شود

استراتژی برد در بازی هگز چیست؟

آشپزباشی:‌ مرتب کردن پشته با برعکس کردن یک دنباله متوالی از ابتدای آن

تعداد مثلث های پوشاننده

مدرسه تابستانی المپیاد کامپیوتر چه خبره؟

آزمون عملی (مرحله سوم) المپیاد کامپیوتر چطور برگزار میشه و برای آمادگیش چیکار کنیم؟

بازی بر روی تخته

تبدیل جدول با چرخش‌های ساعتگرد مربع $2\times 2$

دنباله ی درجات گراف

مساله گلدباخ - نوشتن هر عدد زوج بزرگتر از ۲ به صورت مجموع دو عدد اول به صورت کد

نکاتی در مورد نوشتن پاسخ:

در این قسمت می‌تونی به یک پرسش پاسخ بدی. اگه می‌خوای در مورد پرسش بحث و اظهار نظر کنی از قسمت «ثبت نظر» استفاده کن.
پاسخت رو دقیق و کامل بنویس، از عکس استفاده کن و اگه لازمه به منابع (کتاب یا سایت) ارجاع بده.
اگه پرسش یا پاسخ‌ها مفید هستند حتما بهشون رای بده تا پرسش‌ها و پاسخ‌های خوب مشخص بشن.

استفاده از ویرایشگر:

توی قسمت پیش‌نمایش می‌تونی ببینی متنی که نوشتی چجوری روی سایت دیده میشه.
خیلی مهم: برای اینکه به خط بعد بری باید دوتا Enter بزنی.
می‌تونی از تگ‌های معمولی و ساده‌ی html هم استفاده کنی.
با دکمه‌هایی که بالای ویرایش‌گر قرار دارند کلی کار می‌شه کرد. از عکس‌گذاشتن بگیر تا لیست شماره‌دار. حتما امتحان‌شون کن.

علائم ریاضی:

برای نوشتن علائم ریاضی می‌تونی از Mathjax استفاده کنی. راهنمای Mathjax رو از سایت math.stackexchange بخون.
برای نوشتن عبارت ریاضی وسط جمله، اون عبارت رو بین دوتا $ قرار بده.
برای نوشتن عبارت ریاضی تو یه خط جدید اون رو بین دوتا $$ قرار بده.

حدس زدن کارت پنجم با انتخاب ترتیب دادن ۴ کارت

4

52 کارت بازی در اختیار داریم. یک نفر 5 تای آنها را به ما داده است. می خواهیم 4 تا از آنها رابه ترتیبی به نفر بعدی بدهیم تا او از روی ترتیب بفهمد کارت دیگر چه کارتی بوده است:

الف)ثابت کنید می توانیم این کار را بکنیم.

ب) استراتژی برد ارائه دهید

استراتژی-برد بازیها دوره-تابستانی کد-گذاری
2014-06-09 02:08:37 -0500
عقب مونده 189 ● 4 ● 8 ● 17
پاک‌کردن   ویرایش سوال
نظرات

فکر کنم یکی تکالیف دوره تابستون المپیاد ریاضی رو به شما فروخته!(لطفا تگ بازیها رو اضافه کنید)

2014-06-09 02:27:48 -0500 ابر لرد

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

2014-06-09 02:52:52 -0500 کد تراش

سوال ماله دوره ریاضی نیست مال کامپیوتر از آقای مصدق شنیدم سوال کاملا مفهومه از 52 کارت (ورق) 5 تاشو به من دادن من که قبلا با شما هماهنگ بودم چهارتاشو انتخاب می کنم و جایگشتشو به شما میدم شما به جایگشت نگاه می کنی می گی اون یکی کارت چی بوده

2014-06-09 03:07:57 -0500 عقب مونده

ولی تو دوره ریاضی هم بوده

2014-06-09 03:26:12 -0500 ابر لرد

من دیگه در اون مورد چیزی نمی دونم فقط می دونم حدود 10 ساعت به 3 تا سوال فکر کردم یکیشون این بود

2014-06-09 03:52:34 -0500 عقب مونده

2 پاسخ

3

من قبل از یک راه حل، روال فکر کردن خودم به این مساله رو مینویسم:

اول هر ۵۲ کارت رو به یک ترتیب دلخواه شماره ۱ تا ۵۲ میدیم. حالا قدری جای نفر بعدی فکر میکنیم:‌ با داشتن ۴ تا کارت چه چیزهایی میتونه استنباط کنه؟ (۱) ترتیب اون کارتها (۲) زوج یا فرد بودن اون کارتها.

با ترتیب شروع کنیم. ۴ تا کارت داده شده میتونستند به $4!=۲۴$ جایگشت مختلف به ما داده بشن. اما تعداد کارتهای باقیمانده که باید از بینشون انتخاب کنیم ۴۸ تاست. پس جایگشت به تنهایی جوابگو نیست. اما ما یک امکان دیگه هم داریم: نحوه انتخاب کارت پنجم. اگه بتونیم طوری به نفر بعدی بفهمونیم که کارت پنجم زوج هست یا فرد میشه امیدوار بود که ۴۸ تا کارت کاندید نصف بشه (یعنی ۲۴ تا) که دیگه بر اساس جایگشت بشه کارت پنجم رو شناخت.

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

یه مشکل دیگه هم بود: حتی مثلا اگر به نفر بعدی میفهموندیم کارت پنجم زوج هست، ممکن بود از بین ۴۸ تا کارت باقیمانده بیش از ۲۴ تا زوج باشند که دیگه حتی شماره جایگشت که فقط ۲۴ حالت رو مشخص میکنه هم دردی رو دوا نکنه. برای حل این مشکل میتونیم ۴۸ تا کارت باقیمانده رو دوباره بر اساس ترتیب کوچک به بزرگ قبلی از ۱ تا ۴۸ شماره گذاری کنیم.

حالا برای فهموندن زوجیت کارت پنجم میتونیم این کار رو بکنیم: اگر جمع عدد ۵ تا کارت زوج بود، کوچکترین کارت رو به عنوان کارت پنجم در نظر میگیریم:‌ چون کوچکترین کارت بوده شماره اش در ترتیب ۴۸ کارتی جدید با شماره قدیمش یکسان هست. چون جمع ۵ تا کارت زوج بوده پس زوجیت ۴ کارت باقیمانده با این کارت برابر هست، یعنی نفر بعدی میتونه بر اساس زوجیت مجموع ۴ تا کارت متوجه بشه که کارت پنجم باید شمارش زوج باشه یا فرد. اگر جمع ۵ تا کارت فرد بود اون موقعی کارتی که در ترتیب کوچک به بزرگ ۵ کارت دومی هست رو انتخاب میکنیم. زوجیت مجموع ۴ کارت باقیمانده با شماره قدیم این کارت متفاوت هست. اما چون یکی از ۴ کارت شماره کمتری داره و از ترتیب ۴۸ کارت حذف شده، شماره جدید کارت پنجم زوجیتی برابر مجموع ۴ کارت باقیمانده پیدا میکنه، هورا! تا اینجا به نفر بعدی فهموندیم کارت پنجم از بین ۴۸ کارت باقیمانده با شماره های جدید چه زوجیتی داره. پس فقط ۲۴ تا کارت باقی می مونن که دوباره به اونها از ۱ تا ۲۴ شماره میدیم (به ترتیب کوچک به بزرگ از شماره های اولیه) و کارت پنجم هم بین اونهاست.

حالا برای تعیین شماره یکی از اون ۲۴ کارت کافیه کل جایگشتهای ۱ تا ۴ رو به ترتیب (شبیه الفبایی) بنویسیم و به اونها از شماره ۱ تا ۲۴ شماره بدیم. مثلا ۱۲۳۴ میشه جایگشت اول، ۱۲۴۳ میشه دوم، ۱۳۲۴ میشه سوم، به همین ترتیب. حالا شماره جدید کارت پنجم رو در نظر میگیریم و ۴ کارت رو به ترتیب جایگشت با شماره مورد نظر به نفر بعد تحویل میدیم. این طوری نفر بعد متوجه جایگشت میشه، میتونه شماره جایگشت رو حساب کنه و بعدا کارت درست رو از بین ۲۴ کارت با زوجیت درست شناسایی کنه :-)

2014-06-09 13:09:59 -0500
کلاه قرمزی 3097 ● 21 ● 34 ● 57
پاک‌کردن   ویرایش پاسخ
نظرات

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

2014-06-09 13:19:57 -0500 عقب مونده

من دفعه اول که پاسخ خوندم درست متوجه نشدم ولی الان فهمیدم ایدتون خیلی زیبا بود مخصوصا وقتی که مجموع 5 کارت فرده

2014-06-09 13:33:17 -0500 عقب مونده
0

با تشکر از کلاه قرمزی جان

اینم راه حل خودمه:

52 کارت داریم که تقسیم بر چهار می شه 13 پس کارت های رو 13 تا 13 تا رنگ آمیزی می کنیم حالا هر رنگی که دوست داشتیم. و هر رنگ رو دوباره از 1 تا 13 شماره گذاری می کنیم. مثلا 1 قرمز، 2 قرمز،.... و 1 آبی، 2 آبی،... و به همین ترتیب جلو می ریم.

طبق اصل لانه کبوتری از 5 تا کارتی که با ما می دن حداقل 2 تاشون از یه رنگن. پس می شه یکی از اونا رو برداریم داریم اون یکی رو به عنوان اولین کارتمون از 4 کارتی که قراره به نفر بعدی بدیم انتخاب می کنیم.(اما کدوم). اون 3 تای دیگه می تونن به !3 حالت یعنی 6 حالت جایگشت داشته باشن خب تا الان بهش فهموندیم که کارتمون تو کدوم 13 تاس ولی با 6 جایگشت مختلف از سه کارت می تونیم چه بش بگیم؟ بهترین راه اینه که از اون 6 تا به عنوان فاصله ی بین دوتا کارتی که از یه رنگ بودن استفاده کنیم به چه صورت؟ 13 تا کارت رو توی یه جایگشت دوری قرار بدید. بدیهی که فاصله هیچ دو عضوی توی این جایگشت بیشتر از 6 نیست خب حالا کافی قبل از انجام بازی با نفر دوم اینجوری هماهنگ کرده باشه:

  1. کارتی که توی جایگاه اوله رنگ کارت منو نشون می ده

  2. به ازای هر کدوم از جایگشت های 3 تا کارت بعدی یک از این عدد ها رو در نظر بگیر(مثلا $123=1$ و $132=2$ به همین ترتیب. منظور از 1 و 2 و 3 بزرگی کارت هاست یعنی بزرگترین کارت 3 کارت با امتیاز وسط 2 و کوچکترین کارت 3)

  3. به ازای هر عدد به همون اندازه توی جایگشت دوری ساعت گرد(یا پادساعت گرد) بچرخ تا بفهمی شماره کارت من چیه.

حالا وقتی 5 تا کارت رو بهش دادن یکی از اون دوتا کارت هم رنگ رو با توجه به اینکه به دوستش گفته ساعت گرد بچرخه یا پادساعت گرد رو انتخاب می کنه اون یکی رو به عنوان اولین کارت و 3 تا کارت بعدی رو متناسب با فاصله ی دوتا کارت با جایگشت مناسب به طرف مقابل میده.

2014-06-10 06:35:25 -0500
عقب مونده 189 ● 4 ● 8 ● 17
پاک‌کردن   ویرایش پاسخ
نظرات

این سوال اقای زیارتی نیست؟ چون دقیقن همین جوابم داشت....

2014-06-14 01:04:30 -0500 گابی

پاسخ شما

فقط در صورتی که پاسخی برای این پرسش دارید، آن را اینجا بنویسید و برای بحث کردن از قسمت «ثبت‌ نظر» استفاده کنید. شما می‌توانید قبل از وارد شدن به سایت پاسخ خود را بنویسید. این پاسخ ذخیره می‌شود و زمانی که شما وارد سایت شدید یا ثبت‌نام کردید منتشر می‌شود.

پیش‌نمایش:

کلیه‌ی حقوق این سایت متعلق به کمیته‌ی ملی المپیاد کامپیوتر است.