◄◄ اتــاق تــجــزیــه و تــرکــیــبــات ►►

[m_honarmand_j]

سلام
صفحه کاغذ شطرنجی بی پایانی را با 9 رنگ مختلف رنگ کرده ایم . هر خانه یک رنگ دارد و در ضمن از همه ی رنگ ها استفاده شده است . دو رنگ را مجاور می نامیم هرگاه دوخانه که با یک ضلع مشترک پیدا شود که با این دو رنگ ، رنگ شده باشند . حداقل تعداد زوج رنگ های مجاور چند تاست؟

پاسخ 8 می شود . سعی کنید در حالت کلی ثابت کنید اگر صفحه شطرنجی را با K رنگ رنگ کنیم حداقل K-1 زوج رنگ (یکسان)مجاور هم می شوند .

[m_honarmand_j]

سلام
یال های یک گراف کامل را که 2*n+1 راس دارد ، با سه رنگ مختلف رنگ کرده ایم. ثابت کنید ، می توان یکی از رنگ ها و n+1 راس را طوری انتخاب کرد که ، از هر یک از این راس ها به هر راس دیگر از آن ها ، بتوان ار طریق یال هایی حرکت کرد که دارای رنگ انتخابی ما باشند .

سلام
استقرای روی n . مجموعه ی X شامل n راس را انتخاب می کنیم که با یال های (مثلا با رنگ اول) به هم مربوط اند . اکنون یکی از آن ها را کنار می گذاریم و از بقیه راس ها ، باز هم n راس را انتخاب می کنیم که با یک رنگ به هم مربوط باشند . ( مجموعه ی Y) .
حالت اول . این رنگ ، همان رنگ اول است . در این صورت ، دو انتخاب از n راس ، نباید متقاطع باشند و راس باقی مانده ی A ، به این 2n راس تنها با یال های به رنگ دوم و سوم ، به هم مربوط اند . ولی در این صورت تعداد یال های یکی از این دو رنگ ، دست کم برابر با n ؛ و n راس متناظر ، همراه با A ، n+1 راس مورد نظر را تشکیل می دهند .
حالت دوم . رنگ اخیر ، رنگ دوم ( یا سوم ) است . دراین حالت ، همه ی 2n+1 راس را به دو دسته تقسیم می کنیم : دسته ی اول شامل سه راس که در یکی از دو مجموعه ی X یا Y باشند ؛ دسته ی دوم ، شامل بقیه ی راس ها . به سادگی دیده می شود ، به جز حالت بی معنی که ممکن است پیش بیاید ، هر یک از این دسته ها به دو بخش چنان تقسیم می شود که ، راس های بخش های مختلف دسته ، تنها با یال های به رنگ سوم (و یا دوم) می توانند به هم مربوط شده باشند ؛ در غیر این صورت ، مجموعه ی شامل n+1 راس ( که مورد نظر ماست) ، بلا فاصله ظاهر می شود . در یکی از این دسته ها ، دست کم n+1 راس وجود دارد که تنها با یال های به رنگ سوم به هم مربوط اند : همان چیزی که لازم داریم .

[m_honarmand_j]

سلام
راس های یک گراف محدود با دورنگ مختلف رنگ شده اند . در هر ثانیه ، هر نقطه تغییر رنگ می دهد و به رنگی در می آید که در همسایگی آن بیشتر است . ثابت کنید ، برای هر نقطه لحظه ای فرا می رسد که ، بعد از آن ، یا تغییر رنگ نمی دهد و یا در هر ثانیه ، تغییر رنگ می دهد .

سلام
این مسئله یکی از مسائل واقعا جالب در مبحث گراف بود که دیدم . من که از حل این مسئله لذت بردم .امید وارم شماهم خوشتون بیاد .
فرض کنید که این طور نباشد . در نتیجه راسی وجود دارد که گاهی متناوبا رنگش عوض می شود و گاهی رنگش ثابت می ماند . فرض کنید که این راس زوج همسایه دارد که متناوبا رنگشان عوض می شود . در این صورت یا از هر رنگ در همسایه های آن به تعداد مساوی قرار دارد و یا تعداد یک رنگ از دیگری بیشتر است . در حالت اول همیشه باید رنگ راس مفروض ثابت بماند و در حالت دوم همیشه باید رنگ راس مفروض عوض شود و این خلاف فرض ماست . به سادگی دیده می شود اگر تعداد همسایه های راس ما فرد با شد و همگی متناوبا عوض شوند باز هم خواسته ی ما بر آورده نمی شود . همین طور حالتی که همسایه از داشته باشد که رنگش ثابت باشد نیز رد می شود (یکم پیچیده تر از حالت های قبل) در نتیجه باید راسی در همسایگی راس اول v1 مانند v2 وجود داشته باشد که آن هم مانند v1 تغییر رنگ دهد یعنی گاهی اوقات ثابت و گاهی متناوب . اگر v2 همسایه ی دیگری از این گونه نداشته باشد پس تغییر رنگ آن وابسته به راس v1 می شود و باز خواسته برآورده نمی شود . در نتیجه این راس نیز باید همسایه ای مانند v3 داشته باشد که تغییر رنگ آن نیز همانند v2 گاهی متغییر و گاهی ثابت باشد . و آن راس نیز باید همسایه ی دیگری داشته باشد ... . اگر ما در مرحله ای به راسی تکراری برسیم (یک دور تشکیل شود) می بینیم که تغییر رنگ همه ی راس ها وابسته به هم در نتیجه خواسته ی ما بر آورده نمی شود . چون گراف ما متناهی است پس نمی تواند این رویه تا بینهایت ادامه داشته باشد و چون تعداد دور ها در گراف متناهی است سر انجام ما باید در یکی از این دور ها بی افتیم و یا به یک برگ برسیم که در هر دو صورت نمی توان خواسته ی خود را بر آورده کنیم در نتیجه فرض ما اشتباه بوده و چنین راسی نداریم .

[m_honarmand_j]

سلام
فرض کنید یک میلیارد ( کمتر هم می شه ) ستاره در آسمان وجود دارد . ثابت کنید در بین آن ها حداقل 79 فاصله ی متفاوت وجود دارد .

[m_honarmand_j]

سلام
یک دنباله به طول 1000 داریم که در آن هزار عدد آمده اند .(لزوما متفاوت نیستند) در هر مرحله زیر هر عدد تعداد باری که آن عدد در دنباله ظاهر شده است را می نویسیم . و دوباره روی دنباله ی به دست آمده عمل بالارا انجام می دهیم . ثابت کنید به مر حله ای می رسیم که بعد از آن دنباله تکرار می شود .

[m_honarmand_j]

سلام
یک اژدها 100 سر دارد و یک شوالیه می تواند با هر ضربه ی شمشیر خود 15 یا 17 یا 21 یا 5 سر اژ دها را قطع کند و برای این حالت به ترتیب 24 و 2 و 15 و 17 سر جدید از بدن اژدها رشد می کند . اگر تمام سرهای اژدها قطع شود اژدها خواهد مرد . آیا ممکن است اژدها بمیرد؟

[m_honarmand_j]

سلام
خوب اینجوری بهتره ولی جواب سوال هنوز غلطه!

سلام
من قبلا با دو رنگ مسئله رو حل کردم ولی هرچی فکر کردم یادم نیومد چه جوری ولی با سه رنگ می شه . با سه رنگ 1و2و3 جدول و رنگ می کنیم . سطر پایین از سمت چپ شروع می کنیم و به ترتیب به سمت راست میرویم و به ترتیب رنگ های 1و2و3 و در خانه ها قرار می دهیم . در سطر بالا همین کار را از رنگ 2 شروع می کنیم و در سطر بالای آن از رنگ 3 شروع می کنیم . مشاهره می شود که در هر گام از خانه ی 1 به خانه ای بارنگ 2 و از رنگ 2 به خانه ای به رنگ3 و از 3 به 1 می رویم . چون 22 خانه به رنگ 2 و 21 خانه از 1 و21خانه از داریم 3 پس یک خانه به رنگ 2 باقی می ماند .

[m_honarmand_j]

سلام
یک اژدها 100 سر دارد و یک شوالیه می تواند با هر ضربه ی شمشیر خود 15 یا 17 یا 21 یا 5 سر اژ دها را قطع کند و برای این حالت به ترتیب 24 و 2 و 15 و 17 سر جدید از بدن اژدها رشد می کند . اگر تمام سرهای اژدها قطع شود اژدها خواهد مرد . آیا ممکن است اژدها بمیرد؟

سلام
خیر .مشاهده می شود که با اعمال گفته شده باقی مانده تعداد سر های اژدها به 3 همیشه ثابت می ماند . در اول این باقی مانده برابر 1 است پس هیچ گاه اژدها نمی میرد .

[m_honarmand_j]

سلام
یک دنباله به طول 1000 داریم که در آن هزار عدد آمده اند .(لزوما متفاوت نیستند) در هر مرحله زیر هر عدد تعداد باری که آن عدد در دنباله ظاهر شده است را می نویسیم . و دوباره روی دنباله ی به دست آمده عمل بالارا انجام می دهیم . ثابت کنید به مر حله ای می رسیم که بعد از آن دنباله تکرار می شود .

سلام
از اکسترمال استفاده کنید و ثابت کنید هر ستون از مرحله ی دوم به بعد حداقل دوبرابر می شود . و یک مرز بالایی برای اعداد در نظر بگیرید . ثابت می شود همه ی دنباله ها بعد از حداکثر 11 مرحله متناوب می شوند.

[m_honarmand_j]

سلام
فرض کنید یک میلیارد ( کمتر هم می شه ) ستاره در آسمان وجود دارد . ثابت کنید در بین آن ها حداقل 79 فاصله ی متفاوت وجود دارد .

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