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

nima-1376 · 1393/1/12

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

اگه 2 تا مجاور پر شوند هیچ وقت با هم خالی نمبشن!
حالا بقیش با استقرا و اندکی تعمیم حکم حل میشه!!!

mahdi math · 1393/1/13

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

سوال بعدی(با اجازه اساتید):
سوال:فرض کنید r یک عدد طبیعی و داریم:

$1\leq r\leq n$

تمام زیر مجموعه های r عضوی

$x=\left \{ 1,2,3,...,n \right \}$

را درنظر بگیرید.هر کدام از این زیر مجموعه ها یک کوچکترین عضو دارد. اگر

$F(n,r)$

واسطه ی حسابی بین این کوچکترین عضوها باشد ثابت کنید:

$F(n,r)=\frac{n+1}{r+1}$

(المپیاد جهانی 1981)
راهنمایی که شاید بدردتون بخوره(تناظر یک به یک)

nima-1376 · 1393/1/13

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

راهنمایی از اتحاد چوشی چی استفاده کنید!

math1998 · 1393/1/15

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

دوگانه شماری
سوال1.در شهر ادمی را تنها گوئیم که کمتر از 10 اشنا داشته باشد و ادمی را عجیب گوئیم که همه ی اشنایان او افرادی تنها باشند.نشان دهید تعداد ادمای تنها در این شهر از تعداد ادم های عجیب کمتر نیست.

AHZolfaghari · 1393/1/15

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

mahdisamimi گفت

بوضوح می توان فهمید که این کوچک ترین ها یکی از اعداد 1,2,3,....,n-r+1 هستند.حالا باید بگیم مثلا k چند بار اومده.
اگه تو یه مجموعه k کوچک ترین عضو باشه اونوقت بقیه اعضا از بین اعداد k+1 , .... , n هستند پس میشه انتخاب r-1 از n-k
پس مجموع تمامی این کوچک ترین ها میشه :

$\sum_{k=1}^{n-r+1} k \binom{n-k}{r-1}$

که باید بر تعداد این زیرمجموعه ها تقسیم شه یعنی

$\binom{n}{r}$

پس باید ثابت کنیم

$\sum_{k=1}^{n-r+1} k \binom{n-k}{r-1}$

تقسیم بر

$\binom{n}{r}$

میشه همون خواسته مساله که اینم با چوشی چی حل میشه
چون r-1 تو پایین همه عبارت ها هست میشه حلش کرد

mahdi math · 1393/1/15

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

math1998 گفت

آیا فردی میتواند هم تنها و هم عجیب باشد؟
در غیز این صورت باید تعداد افراد تنها بزرگتر یا مساوی 10 باشد:224:

n_maths · 1393/1/15

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

روی دایره ای تعدادی نقطه آبی و قرمز وجود دارد.میتوان یک نقطه قرمز اضافه کرد و رنگ هردو همسایه اش را با رنگ دیگر عوض کرد،یا میتوان یک نقطه قرمز حذف کرد و رنگ هر دو همسایه اش زا با رنگ دیگر عوش کرد.ثابت کنید اگر در ابتدا فقط دو نقظه قرمز روی دایره داشته باشیم دنباله اس از حرکات مجاز وجود ندارد تا با انجام آنها به وضعیتی برسیم که روی دایره فقط دو نقطه آبی وجود داشته باشد (تورنمنت شهر ها1980)

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

روی دایره ای تعدادی نقطه آبی و قرمز وجود دارد.میتوان یک نقطه قرمز اضافه کرد و رنگ هردو همسایه اش را با رنگ دیگر عوض کرد،یا میتوان یک نقطه قرمز حذف کرد و رنگ هر دو همسایه اش زا با رنگ دیگر عوش کرد.ثابت کنید اگر در ابتدا فقط دو نقظه قرمز روی دایره داشته باشیم دنباله اس از حرکات مجاز وجود ندارد تا با انجام آنها به وضعیتی برسیم که روی دایره فقط دو نقطه آبی وجود داشته باشد (تورنمنت شهر ها1980)

mohy1376 · 1393/1/15

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

nima-1376 گفت

میشه اتحاد رو بگی؟

AHZolfaghari · 1393/1/16

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

mohy1376 گفت

$\sum_{i=r}^{n}\binom{i}{r} = \binom{n+1}{r}$

ash1374 · 1393/6/2

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

با 55 مربع 2 در 2 یک مربع 10 در 10 را پوشانده ایم. ثابت کنید حداقل 1 مربع 2 در 2 وجود دارد که با حذف آن همچنان مربع بزرگ پوشیده باقی خواهد ماند.

باشد که استقبال کنند...

mahmoud20ni · 1393/6/4

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

مربع ها را به 9 پک تقسیم بندی میکنیم به این صورت که پک i ام مربوط به مربع هایی است که خانه های ان ها در سطر i ام و i+1 ام قرار میگیرد . به وضوح در یکی از پک ها حداقل 7 مربع قرار میگیرد . (فرض میکنیم این 7 مربع مربوط به پک اول باشند) حال مربع های پک اول را به 9 دسته تقسیم میکنیم به طوری که دسته i ام مربوط به مربع هایی از پک اول است که خانه هایی از ستون i ام و i+1 ام را میپوشانند . اولا در پک اول اگر دو مربع مربوط به یک دسته بودند که مسئله حله پس هیچ دو تایی در یک دسته نیستند .همچنین در پک اول اگر 3گروه دسته های 1و2 و3 _ 4و5و6 _7و8و9 را در نظر بگیریم در هر یک از گروه ها حداقل یک دسته بدون مربع باید وجود داشته باشد پس در پک اول باید حداکثر 6 مربع وجود داشته باشد که تناقضه .

ash1374 · 1393/6/8

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

سوال بعد: 100 مهره در یک دسته داریم. در هر مرحله مهره های یک دسته را به دو دسته تقسیم می کنیم. ثابت کنید در یک لحظه ی خاص، می توان 30 دسته را در نظر گرفت که جمعاً 60 مهره درون آن ها باشد.

mahmoud20ni · 1393/6/9

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

زمانی را درنظر میگیرم که تعداد دسته ها به 60 تا رسیده است (یعنی پس از 59 حرکت) در این حالت اگر k تعداد دسته های دارای تک مهره باشد خواهیم داشت :

$k+2(60-k)\leq 100 \Rightarrow k\geqslant 20$

اکنون 20 تا از دسته های تک مهره را کنار میگذاریم و ان ها را گروه A نامگذاری میکنیم و از 40 دسته ی باقیمانده را در نظر میگیریم(گروه B)که در مجموع شامل 80 مهره میباشند فرض میکنیم تعداد مهره های قرار گرفته در این 40 دسته به صورت

$1\leqslant n\leqslant n_2\leqslant ...\leqslant n_40$

باشد . اکنون 20 دسته از گروه 20 با بیشترین تعداد مهره را در نظر میگیریم (گروه C ) و 20 دسته ی دیگر گروه B را گروه D نامگذاری میکنیم . اکنون تعداد مهره های گروه C به صورت

$40\leqslant n_21+n_22+...+n_40\leqslant 60$

می باشد اگر

$50\leqslant n_21+n_22+...+n_40$

نیز برقرار باشد که مسئله حل است چرا که به این 20 دسته گروه C با اضافه کردن حداکثر 10 دسته از گروه A میتوان حکم را نتیجه گرفت . پس حالت

$40\leqslant n_21+n_22+...+n_40< 50$

باید بررسی شود. در این حالت اولا تعداد مهره های قرار گرفته در دسته های گروه D حداکثر برابر 2 میباشد (چرا؟) و همچنین مجموع مهره های گروه D حداقل برابر 30 میباشد که این دو نتیجه میدهد که حداقل 10 تا از دسته های گروه D دارای 2 مهره میباشند(گروه E) حال با به راحتی با تعدادی از دسته های گروه A , E و تمامی دسته های گروه C میتوان حداکثر 30 دسته با مجموع 60 مهره داشت که معادل همان حکم مسئله میباشد .

ash1374 · 1393/6/12

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

$n$

نقطه در صفحه داریم. نشان دهید تعداد جفت نقاطی که فاصله ی آن ها برابر واحد است حداکثر از مرتبه ی

$n^{\frac{3}{2}}$

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

$n^{\frac{4}{3}}$

؟؟؟ حدسی باز وجود دارد که می گوید برای هر

$\epsilon >0$

0"> تعداد فواصل واحد از مرتبه ی

$n^{1+\epsilon }$

کمتر است.

لطفا هر کس سوال رو حل کرد سوال بعدی رو هم خودش بگذاره و ماراتن رو خودتون به دست بگیرید.

sepidfekr · 1393/8/20

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

ash1374 گفت

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

math1998 · 1393/8/21

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

sepidfekr گفت

خطی در صفحه مانند

$l$

(خط اصلی) در نظ بگیرید روی این خط حداقل از یک رنگ بی نهایت نقطه داریم فرض کنید رنگ ابی!!! از هر نقطه ی ابی خطی به خط اصلی عمود کنید فرض کنید این خط ها

$d_{1},d_{2},d_{3},....$

باشن یه خط موازی خط اصلی تو صفحه مانند

$p$

در نظر بگیرید محل تقاطع این خط با خط های

$d_{1},d_{2},d_{3},....$

را به ترتیب

$s_{1},s_{2},s_{3},....$

بنامید (نقاط جدید)
اگر در نقاط جدید حداقل 2 تا ابی باشن که حله وگرنه
1)یکی از نقاط ابی و بقیه قرمزن که میتونیم یه خط دیگه موازی خط اصلی در نظر بگیریم اونم اگه حداکثر یه نقطه ابی داشته باشه پس تونستیم یه مستطیل قرمز بسازیم!!!
2)تمام نقاط این خط قرمز باشن که اینم مثل حالت قبله!!!

سوال بعدی:همین سوال رو واسه هر n رنگ تعمیم بدید!!!

sepidfekr · 1393/8/22

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

math1998 گفت

از استدلال حالت دوتایی استفاده میکنیم فقط بی نهایت تا خط موازی میکشیم

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

سوال بعد:
در یک تورنمنت تک حذفی با n بازیکن حداقل به چند بازی احتیاج است تا برنده معلوم شود؟؟؟

ali eini · 1393/8/23

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

n را به صورت جمع 1و2 مینویسیم میدانیم 2ها تبدیل به یک و 1 ها بدون تغییراند دو باره این عمل را برای عدد به دست امده انجام میدهیم.
جواب تعداد بازی ها برابر است با

$\left \lfloor x/2 \right \rfloor=m \left \lfloor m/2 \right \rfloor=1$

.....

$\left \lfloor n/2 \right \rfloor=x$

x+.....+m+1

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

از اقای sepidfekr میخواهم سوال بعدی رو بزارن

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

اوه شرمنده جواب ها به صورت

$\left \lfloor \frac{n}{2} \right \rfloor=x \rightarrow \left \lceil \frac{n}{2} \right \rceil=m\rightarrow \left \lfloor \frac{m}{2} \right \rfloor=x_{1}...........\rightarrow x+x_{1}+.....+x_{i}+1$

m-saghaei · 1393/8/23

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

ali eini گفت

n را به صورت جمع 1و2 مینویسیم میدانیم 2ها تبدیل به یک و 1 ها بدون تغییراند دو باره این عمل را برای عدد به دست امده انجام میدهیم.
جواب تعداد بازی ها برابر است با

$\left \lfloor x/2 \right \rfloor=m \left \lfloor m/2 \right \rfloor=1$

.....

$\left \lfloor n/2 \right \rfloor=x$

x+.....+m+1

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

از اقای sepidfekr میخواهم سوال بعدی رو بزارن

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

اوه شرمنده جواب ها به صورت

$\left \lfloor \frac{n}{2} \right \rfloor=x \rightarrow \left \lceil \frac{n}{2} \right \rceil=m\rightarrow \left \lfloor \frac{m}{2} \right \rfloor=x_{1}...........\rightarrow x+x_{1}+.....+x_{i}+1$

دقیقا منظور از n و x و m چیه؟

sepidfekr · 1393/8/23

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

ali eini گفت

شما باید یه جواب بر حسب n به دست بیارید البته این بر حسب n هستش ولی یکم تغییرات لازم داره

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

New Member

New Member

New Member

New Member

Well-Known Member

New Member

New Member

Well-Known Member

Well-Known Member

New Member

New Member

New Member

New Member

New Member

New Member

New Member

New Member

New Member

New Member

New Member