Question

$n$ مجموعه‌ی ۳ عضوی از مجموعه اعداد {$۱,۲,...,n$} داده شده است. ثابت کنید می‌توان $\lfloor \frac n3 \rfloor$ تا از اعداد مجموعه‌ی {$۱,۲,...,n$} را رنگ کرد به طوری که هیچ‌کدام از $n$ زیر‌مجموعه‌ی سه عضوی ما پیدا نشود که هر سه عضوش رنگ شده باشند.

Answer 1

خوب بعد از یه مدت راه حل خوب و غیر جبریشو پیدا کردم بفرمایید:

سه تایی بد رو تعریف میکنیم برای رنگ امیزی خاصی سه تاش رنگ شده باشه

خوب رنگ امیزی رو در نظر بگیرید که سه تایی های بدش حداقل باشه (اگر صفر باشه که حله) بدون کم شدن از کلیت مسئله فرض کنید اینا

1 و 2 و 3 و...n/3 باشن

بدون کم شدن از کلیت مسئله فرض کنید 3 تایی بد 1 و 2 و 3 باشه مثلا

حالا 1 رو به ترتیب با

n/3,n/3+1,n/3+2,n/3+3,.....n

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

$$ n-n/3+1 $$

تا سه تایی پیدا کردیم حالا اون 1 و 2 و 3 و... n/3 رو بزارین کنار و برای اعداد باقیمانده این کارو بکنین یعنی دوباره بدون عوض شدن کلیت فرض کنین که رنگ امیزی که کمترین بد رو داشته باشه n/3+1, n/3+2 , ..... 2n/3

باشه بعد n/3+1 رو با 2n/3+1 , 2n/3+2 ,.... جایگزین کنید به دلیل قبلی n/3 تا دیگه سه تایی خراب میتونین کشف کنین

خوب پس رو هم ماتونستیم

$$ n-n/3+1+n/3=n+1 $$

تا سه تایی کشف کنیم در صورتی که کلن n تا سه تایی داشتیم

:)

آمار پرسش:

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

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

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

علائم ریاضی:

سوال ۷- مجموعه‌ی سه‌ تایی‌ های پایدار

1 پاسخ

پاسخ شما

پیش‌نمایش: