ماراتن ترکیبیات(پیشرفته)

[MGH000]

پاسخ : ماراتن ترکیبیات(پیشرفته)

فرد A استراتژی برد دارد.
برای n=1 که واضح است. حال فرض میکنیم برای جدول 2n*2n فرد A استراتژی برد داشته باشد.برای (2n+2)*(2n+2) جدول 2n*2n مرکز را طبق فرض استقرا با دومینو ها میتواند فرش کند.8n-4 خانه در حاشیه میماند.A گوشه بالا سمت چپ یک خانه را رنگ میکند.B یک دومینو(مثلا افقی)قرار میدهد.حال A یک خانه دقیقا مجاور خانه ی تازه دومینو قرار داده شده در آن را رنگ میکند و B ب طور یکتا یک دومینو قرار میدهد و A ب همین ترتیب ادامه میدهد.درنتیجه چون تعداد خانه های مانده زوج است و A ب طوری رنگ میکند ک B مجبور ب گذاشتن یکتای دومینو ها و فرش کردن جدول شود،پس میتواند بازی را ببرد

---- دو نوشته به هم متصل شده است ----

سوال بعد:
اگر روی رئوس یک n ضلعی منتظم (n-1) عدد 0 و یک عدد 1 قرار دهیم و در هر مرحله ب رئوس یک k ضلعی منتظم متشکل از رئوس n ضلعی،یک واحد بیفزاییم آیا میتوان همه ی اعداد را با هم برابر کرد؟(با تکرار این کار)

 

[ali eini]

پاسخ : ماراتن ترکیبیات(پیشرفته)

فرد A استراتژی برد دارد.
برای n=1 که واضح است. حال فرض میکنیم برای جدول 2n*2n فرد A استراتژی برد داشته باشد.برای (2n+2)*(2n+2) جدول 2n*2n مرکز را طبق فرض استقرا با دومینو ها میتواند فرش کند.8n-4 خانه در حاشیه میماند.A گوشه بالا سمت چپ یک خانه را رنگ میکند.B یک دومینو(مثلا افقی)قرار میدهد.حال A یک خانه دقیقا مجاور خانه ی تازه دومینو قرار داده شده در آن را رنگ میکند و B ب طور یکتا یک دومینو قرار میدهد و A ب همین ترتیب ادامه میدهد.درنتیجه چون تعداد خانه های مانده زوج است و A ب طوری رنگ میکند ک B مجبور ب گذاشتن یکتای دومینو ها و فرش کردن جدول شود،پس میتواند بازی را ببرد

---- دو نوشته به هم متصل شده است ----

سوال بعد:
اگر روی رئوس یک n ضلعی منتظم (n-1) عدد 0 و یک عدد 1 قرار دهیم و در هر مرحله ب رئوس یک k ضلعی منتظم متشکل از رئوس n ضلعی،یک واحد بیفزاییم آیا میتوان همه ی اعداد را با هم برابر کرد؟(با تکرار این کار)

مستطیل 4 ضلعی منتظمه؟

 

[math1998]

پاسخ : ماراتن ترکیبیات(پیشرفته)

فرد A استراتژی برد دارد.
برای n=1 که واضح است. حال فرض میکنیم برای جدول 2n*2n فرد A استراتژی برد داشته باشد.برای (2n+2)*(2n+2) جدول 2n*2n مرکز را طبق فرض استقرا با دومینو ها میتواند فرش کند.8n-4 خانه در حاشیه میماند.A گوشه بالا سمت چپ یک خانه را رنگ میکند.B یک دومینو(مثلا افقی)قرار میدهد.حال A یک خانه دقیقا مجاور خانه ی تازه دومینو قرار داده شده در آن را رنگ میکند و B ب طور یکتا یک دومینو قرار میدهد و A ب همین ترتیب ادامه میدهد.درنتیجه چون تعداد خانه های مانده زوج است و A ب طوری رنگ میکند ک B مجبور ب گذاشتن یکتای دومینو ها و فرش کردن جدول شود،پس میتواند بازی را ببرد

---- دو نوشته به هم متصل شده است ----

سوال بعد:
اگر روی رئوس یک n ضلعی منتظم (n-1) عدد 0 و یک عدد 1 قرار دهیم و در هر مرحله ب رئوس یک k ضلعی منتظم متشکل از رئوس n ضلعی،یک واحد بیفزاییم آیا میتوان همه ی اعداد را با هم برابر کرد؟(با تکرار این کار)

خیر مرکز این شکل رو در نظر بگیرید هر بار که به یک راس یه واحد اضافه میکنیم اونو با یه بردار از مرکز به راس نشون بدیم طبق خواص بردارا واضحه که تو هر مرحله مجموع بردارا 0 است و در اخر هم 0 است اما در حالت اولیه مجموعشون 1 است پس هیچی دیگه !!!

 

[m-saghaei]

پاسخ : ماراتن ترکیبیات(پیشرفته)

سوال بعد:
در یک گردهمایی 1985 نفر شرکت کردن.در هر زیرمجموعه از 3 شرکت کننده حداقل دو شرکت کننده وجود دارن که به یک زبان صحبت میکنن.اگر هر نفر حداکثر به 5 زبان صحبت کند آنگاه ثابت کنید حداقل 200 نفر به یک زبان صحبت میکنن.

 

[sa1378]

پاسخ : ماراتن ترکیبیات(پیشرفته)

سوال بعد:
در یک گردهمایی 1985 نفر شرکت کردن.در هر زیرمجموعه از 3 شرکت کننده حداقل دو شرکت کننده وجود دارن که به یک زبان صحبت میکنن.اگر هر نفر حداکثر به 5 زبان صحبت کند آنگاه ثابت کنید حداقل 200 نفر به یک زبان صحبت میکنن.

میایم دونفر رو میگیریم بهشون میگیم نقی و تقی که زبان مشترک ندارن باهم
خب اینا چون زبان مشترک ندارن و هرکدوم حداکثر 5 تا زبان بلدن جمعا روی هم حداکثر 10 تا زبان بلدن
1983 نفر دیگه موندن...
اگه نقی و تقی رو با یه نفر دیگه بگیریم(که میشن سه نفر) اون یه نفر دیگه ، حتما به یه زبانی از این 10 زبانی که داشتیم باید بتونه صحبت کنه(چون نقی و تقی که زبان مشترک ندارن و طبق فرض هم بین هر 3 نفر باید یه زبان مشترک باشه)
پس 1983 نفر داریم با 10 تا زبان که طبق لانه کبوتری حداقل 199 تاشون به یه زبان صحبت میکنن که به علاوه ی نقی یا تقی(که زبانش با اونا مشترکه) بشه میشه 2000:3:


حالا ما اولش فرض کردیم دو نفر هستن که زبان مشترک ندارن ، فرض میکنیم در حالت دیگه همه افراد با هم زبان مشترک دارن در این صورت یه نفر میگیریم به اسم ضربعلی...
1984 نفر دیگه میمونن و 5 تا زبان هم ضربعلی بلده...طبق لانه کبوتری یه زبان بالای 200 هست(دیگه خودتون تقسیم کنین)

 

[sa1378]

پاسخ : ماراتن ترکیبیات(پیشرفته)

n گلوله با وزن های مختلف داریم...یه ترازوی دو کفه هم داریم...دیگه هیچی نداریم
ثابت کنین با حداکثر

بار وزن کردن میتوان دو گلوله سنگین تر را پیدا کرد...

 

[sepidfekr]

پاسخ : ماراتن ترکیبیات(پیشرفته)

n گلوله با وزن های مختلف داریم...یه ترازوی دو کفه هم داریم...دیگه هیچی نداریم
ثابت کنین با حداکثر

بار وزن کردن میتوان دو گلوله سنگین تر را پیدا کرد...

من که نتونستم اگه کسی تونسته حل کنه جواب بده اگه نه سوال بعدی رو بزارم!!!

 

[mojtabaaa1373]

پاسخ : ماراتن ترکیبیات(پیشرفته)

n گلوله با وزن های مختلف داریم...یه ترازوی دو کفه هم داریم...دیگه هیچی نداریم
ثابت کنین با حداکثر

بار وزن کردن میتوان دو گلوله سنگین تر را پیدا کرد...

برای راحتی فرض کنید تعداد گلوله ها توانی از دو است مثلا $2^m$ حال $m$ سطر را اینگونه ایجاد می کنیم : در سطر اول تمام گلوله ها را از چپ به راست دو تا دوتا جدا کرده و در سطر اول میگذاریم در سطر دوم از بین گروه های دوتایی سطر اول بزرگترین هر گروه را با یک بار وزن کردن به دست آورده و به ترتیب گروه ها از چپ به راست مرتب میکنیم و در سطر دوم میگذاریم و در سطر دوم میگذاریم و دوباره از چپ به راست به گروه های دوتایی تقسیم میکنیم و به همین ترتیب تا سطر $m$ به وضوح در سطر $m$ تنها یک گلوله باقی مانده که به وضوح سنگین ترین است،تا این مرحله ما $2^m$ تا وزن کردن انجام داده ایم حال برای به دست آوردن گلوله سنگین تر دوم این گونه عمل میکنیم : به وضوح اگر گلوله سنگین تر دوم با گلوله ای به جز سنگین ترین گلوله مقایسه شود سنگین تر خواهد بود بنابراین گلوله سنگین تر دوم باید یکی از گلوله هایی باشد که با سنگین ترین گلوله مقایسه شده و سنگین ترین بین این گلوله ها ، از طرفی تعداد این گلوله ها
$m-1 $تا است ، با شروع از یک گلوله از این $m$ تا و مقایسه آن با یکی دیگر از آنها و مقایسه گلوله سنگین تر با یکی دیگر از گلوله های باقی مانده و ادامه این روند گلوله سنگین تر دوم هم به دست آمد. و تعداد این مراحل m-2$ $ تا است زیرا تعداد گلوله ها که باید در این مرحله مقایسه میشدند $m-1 $ تا بود.
حال داریم در کل $ 2^m+m$وزن کردن انجام دادیم.

---- دو نوشته به هم متصل شده است ----

فقط یه سوال, از فرد-منتظم بودنش چه استفاده ای شده؟؟؟؟

سوال بعدی: مربع واحد abcd به 12^10 تا مربع کوچکتر (نه لزوما مساوی) تقسیم شده. ثابت کنید جمع محیط تمام مربع هایی که با قطر ac نقطه مشترک دارن از 1500 بیشتر نیست.

این سواله چقدر قشنگه ^_^
ابتدا ثابت میکنیم حداکثر تعداد مربع های با طول ضلع حداقل $1/m$ که با قطر اصلی برخورد دارند برابر است با 4m:
ناحیه $A$ را اینگونه مشخص میکنیم:
دو خط موازی به فاصله $\frac{\sqrt{2}}{m}$ در دو سوی قطر اصلی میکشیم و ناحیه ایجاد شده در بین این دو خط و داخل مربع را به عنوان ناحیه $A$ در نظر می گیریم.
هر مربع با طول ضلع حداقل $1/m$ که با قطر اصلی نقطه مشترک دارد حداقل در ناحیه ای به مساحت $\frac{1}{m^2}$ با ناحیه $A$ اشتراک دارد و از طرفی مساحت ناحیه $A$ از $4/m$ کمتر است بنا براین حداکثر تعداد مربع های با طول ضلع حداقل $1/m$ که با قطر اصلی برخورد دارند برابر است با :$\frac{4/m}{1/m^{2}}=4m$
حال به اثبات حکم اصلی مسئله میپردازیم:
فرض کنید $a_1$ تا مربع با ضلع بین $1/2$ و $1$ داریم که با قطر اصلی اشتراک دارند $a_2$ تا به ضلع بین $1/2$ و $1/3$ و به همین ترتیب طبق مطلب گفته شده در بالا داریم :
$a_1+a_2+...+a_k\leq 4k$ بنابراین ماکسیمم عبارت $4(\frac{a_1}{1}+\frac{a_2}{2}+\frac{a_3}{3}+...+\frac{a_k}{k})$ که جمع محیط مربع های خواسته شده است از $4(\frac{4}{1}+\frac{4}{2}+\frac{4}{3}+...+\frac{4}{k})=16(\frac{1}{1}+\frac{1}{2}+\frac{1}{3}+...+\frac{1}{k})$ کمتر است و بنابراین از $16(1+\int_{1}^{k}\frac{1}{x}dx)=16(1+ln(k)-ln(1))$ کمتر است ، از طرفی داریم تعداد مربع ها $10^12$ تا است بنابراین در زمانی که عبارت $4(\frac{a_1}{1}+\frac{a_2}{2}+\frac{a_3}{3}+...+\frac{a_k}{k})$ ماکسیمم میشود مقدار k باید کمتر مساوی $\frac{10^12}{4}$ شود و بنابراین برای جمع محیط مربع های مذکور داریم: $16(1+ln(k)-ln(1))\leq 16(1+ln(10^12))=16(1+12ln(10))< 16(1+12*3)=592< 1500$

 

[mojtabaaa1373]

پاسخ : ماراتن ترکیبیات(پیشرفته)

فرض کنید تعدادی نقطه در صفحه 2 بعدی داریم که به دو رنگ آبی و قرمز رنگ آمیزی شده اند ، ثابت کنید یک خط وجود دارد که حداقل از دو نقطه از این نقاط میگذرد و تمام نقاط روی خط همرنگند.