سوال شب 3

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

 

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

 

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

حالا در کل 2^M زیرمجموعه داریم. هر کدوم از زیرمجموعه ها مثل S رو متناظر با یک n+1 تایی مرتب (a₀, a₁ , ... , a_n) می کنیم, که a_i برابر sigma (S_j) ⁱ هست.

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

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

 

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

 

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

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

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

 

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