آمار پرسش:

• پرسیده شده: 2024-03-26 20:06:19 -0600
• مشاهده شده: 195 بار
• بروز شده: 2024-03-27 04:54:25 -0600

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

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

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

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

علائم ریاضی:

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

چالش ببعی : یک مربع n در n پر از سکه‌های طلا

2

سلام!

کنکوری و توفیقی به یک چالش دعوت شده‌اند که فردا برگزار می‌شود:

ابتدا ببعی کنکوری را به داخل اتاق می‌برد. در این اتاق یک جدول n در n وجود دارد که روی هر خانه از آن یک سکهٔ طلا وجود دارد. بعضی از سکه‌ها به پشت قرار دارند و بعضی دیگر به رو. حالا ببعی یکی از خانه‌های جدول را به کنکوری نشان می‌دهد. پس از آن کنکوری باید دقیقاً یکی از سکه‌های جدول را به انتخاب خودش پشت و رو کند و از اتاق بیرون برود.

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

اگر توفیقی درست حدس بزند ببعی همهٔ سکه‌های روی جدول را به آنها می‌دهد. حالا کنکوری و توفیقی خواب هستند و ببعی که هیچ دوست ندارد سکه‌هایش را به آنها بدهد صبح زود به فکر چاره است!

ببعی عاشق جدول‌های بزرگ است و از شما می‌خواهد که n بزرگ را برای او پیدا کنید که کنکوری و توفیقی نتوانند سکه‌هایش را بگیرند!

کمکش می‌کنید؟

2024-03-26 20:06:19 -0600

کنکوری 1683 ● 11 ● 25 ● 40

پاک‌کردن   ویرایش سوال

3

اثبات میکنیم که برای $n$ های فرد ببعی استراتژی برد دارد ....

گراف $Q_(n^2)$ را در نظر میگیریم کنکوری و توفیقی در صورتی برنده میشن راس های این گراف را با $n^2$ رنگ بتوان طوری رنگ کرد که هر راس با همه ی رنگ های دیگه (از جمله رنگ خودش ) مجاور باشه چرا چون با عوض کردن هر بیت باید بتونه به هر رنگ برسه که هر رنگ هم نشون دهنده ی جای اشاره شده توسط ببعی هست ولی این کار غیر ممکن است چون $2^(n^2)$ بر n بخش پذیر نیست طبق لانه 2 رنگ با اختلاف حداقل 1 واحد وجود دارن این تعداد رنگ رو a و رنگ دیگه رو b مینامیم $(a > b )$ از اون جایی که هر دو راس از یک رنگ همسایه مشترک ندارن

(در اون صورت همسایه مشترکشون اون هارو دوباره دیده پس رنگی وجود داره که ندیده ) نتیجه میگیریم به ازای هر رنگ a یک رنگ b هم وجود داره که تناقضه .

Edit : در حقیقت نه تنها n های فرد بلکه تمام n هایی که به شکل $2^k$ نیستن کنکوری و توفیقی میبازن

2024-03-27 04:50:48 -0600

الفبا 81 ● 1 ● 6 ● 12

پاک‌کردن   ویرایش پاسخ

نظرات

با استقرا راحت میشه ثابت کرد که برای n = 2^k کنکوری و توفیقی استراتژی برد دارن

2024-03-27 04:56:31 -0600 الفبا

زیبا بود 🗿

2024-03-27 08:27:53 -0600 سیده زینب متولی

آفرین. :))

2024-03-27 20:16:51 -0600 توفیقی

@الفبا برای حالت n=2^k، یه الگوریتم ساده و خوشگل برای استراتژی برد توفیقی و کنکوری هم وجود داره که اونم قشنگه.. (تقریبا تو یه خط می‌شه گفت چیکار کنند)... به اونم فکر کن.

2024-03-27 20:17:43 -0600 توفیقی

@توفیقی قشنگ بود. ولی یه خطی هم نیست :)

2024-03-29 08:17:01 -0600 فامیل دور