شاززز

شاززز

اینجا وبسایت آزاد المپیاد کامپیوتره! ;)
واسه ی همه ی سطوح از تازه کارها تا طلای جهانی!

طبقه بندی موضوعی
بایگانی

سوال شب 3

چهارشنبه, ۱۹ دی ۱۳۹۷، ۰۹:۵۰ ب.ظ

سلام ! دونقطه دی

 

مثل دیروز اول راه شب گذشته رو می گیم ( اگر به سوال به مقدار کافی فکر نکردین، نخونین که براتون لوث نشه !=) ) :

 

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

حالا در کل 2زیرمجموعه داریم. هر کدوم از زیرمجموعه ها مثل S رو متناظر با یک n+1 تایی مرتب (a0, a1 , ... , an) می کنیم, که ai برابر sigma (Sji هست.

ai حداقل 0 و حداکثر M * M i = M i + 1 هست, پس حداکثر M i + 1 + 1 <= M n + 2 حالت دارد ( M > 1 ). در نتیجه تعداد n + 1 تایی های معتبر از M n*n + 3*n + 2 بیستر نیست.

پس کافیه 2M > M n*n + 3*n + 2 تا طبق اصل لانه کبوتری 2 تا زیرمجموعه درست پیدا بشن. تابع 2نمایی هست ولی تابع M n*n + 3*n + 2 چندجمله ای, پس پیدا می شه M که نا مساوی گفته شده برقرار بشه !

 

خب , بالاخره می رسیم به سوال امشب دونقطه دی :

 

خانه های یک جدول مربعی n x n رو با اعداد صحیح پر کرده ایم , به طوری که اختلاف عدد هر دو خانه ی مجاور ضلعی , از 1 بیشتر نشود.

الف ) اثبات کنین عددی وحود داره که حداقل کف n/2 بار در جدول ظاهر شده.

ب ) اثبات کنین عددی وحود داره که حداقل n بار در جدول ظاهر شده.

 

نویسنده: مهرشاد =) (راه سوال دیشب هم از میکائیل )

 
  • ۹۷/۱۰/۱۹
  • شااززز منگولیا

نظرات  (۱)

بازگشت شکوهمندان مهرشاد رو با تمام شاززز منگولیا شادباش میگم :))

ارسال نظر

ارسال نظر آزاد است، اما اگر قبلا در بیان ثبت نام کرده اید می توانید ابتدا وارد شوید.
شما میتوانید از این تگهای html استفاده کنید:
<b> یا <strong>، <em> یا <i>، <u>، <strike> یا <s>، <sup>، <sub>، <blockquote>، <code>، <pre>، <hr>، <br>، <p>، <a href="" title="">، <span style="">، <div align="">
تجدید کد امنیتی