منو
 کاربر Online
696 کاربر online

رنگ آمیزی و همخوانیII

چاپ
علوم ریاضی > علو م رایانه



این مطلب از بخش آموزش وب‌سایت المپیاد کامپیوتر رشد،انتخاب شده که با فرمت pdf نیز در وب‌سایت المپیاد رشدموجود می‌باشد. برای مشاهده این موضوعات در وب‌سایت المپیاد، به آدرس فهرست مطالب کامپیوتر مراجعه کنید. همچنین می‌توانید با کلیک اینجا‌ ، با ویژگی‌های بخش آموزش این وب‌سایت آشنا شوید.


مثال

اگر یک جدول را با بلوک‌هایی مانند شکل (1) پرکرده باشیم ثابت کنید (بر 8 بخش‌پذیر است)
img/daneshnameh_up/6/6d/com0041u.jpg

اثبات
فرض کنید که در پرکردن جدول از k تا بلوک استفاده کرده باشیم لذا تعداد خانه‌های جدول خواهد بود و لذا . حال اگر خانه‌های جدول را شطرنجی رنگ کنیم، چون به واسطه بالا لااقل یکی از و زوج است تعداد خانه‌های سیاه و سفید با هم برابرند (چرا؟) از طرفی اگر یک بلوک مانند شکل (1) را در صفحه قرار دهیم خانه‌های 1،2،4 باهم، همرنگ و خانه 3 از رنگ مخالف خواهد بود لذا در کل دو دسته بلوک داریم:
الف.آنهایی که سه خانه سفید و یک خانه سیاه دارند و تعداد آنها را فرض می‌کنیم.
‌ب.آنهایی که سه خانه سیاه و یک خانه سفید دارند و تعداد آنها را با فرض می‌کنیم.
بنابراین داریم که وعلاوه بر این
تعداد خانه‌های سفید جدول

تعداد خانه‌های سیاه جدول

بنابراین و لذا پس و لذا پس بر 8 بخش‌پذیر است.

مثال

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

حل
برهان خلف: اگر فرد باشد آنگاه هر یک از عدد باید فرد باشد. پس چون جمع فرد تا عدد فرد، فرد می‌باشد پس باید عدد فرد باشد ولی . بنابراین و به تناقض می‌رسیم. بنابراین عدد زوج است.



مثال

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

مثال

در یک مهمانی نفر حضور دارند و هر نفر با تعدادی از مهمان‌ها دست داده‌ است ثابت کنید تعداد افرادی که با تعداد فردی دست داده‌اند زوج است.
حل
در هر دست دادن دو نفر با هم دست داده‌اند پس تعداد کل دست‌دادن‌ها زوج است. حال اگر دست‌دادن کسانی که با تعداد زوجی دست داده‌اند را از آن کم کنیم نتیجه می‌شود تعداد دست‌دادن‌های کسانی که، تعداد فردی دست داده‌اند زوج است پس چون مجموع چند عدد فرد زوج شده است باید تعداد آنها زوج باشد. و حکم ثابت می‌شود.

مثال



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

مثال

یک صفحه شطرنجی را که در آن عددی زوج است در نظر بگیرید و در هرخانه آن عددی صحیح قرار دارد. دو عمل زیر را روی این صفحه تعریف می‌کنیم:
•به تمام خانه‌های یک سطر یا یک ستون یا یکی از دو قطر عدد دلخواه را می‌افزاییم (عددی صحیح است و می‌تواند منفی هم باشد).
•یکی از خانه‌های غیر حاشیه‌ای را انتخاب می‌کنیم و مجموع مربعات اعداد روی هشت همسایه آن را به آن می‌افزاییم و سپس تمام اعداد روی این هشت ‌خانه را به صفر تبدیل می کنیم.
حال جدولی را در نظر بگیرید که در آن عدد خانه‌ای که در سطر ام و ستون ام قرار دارد برابر است با این استثناء که در خانه (1 , 1)، عدد 1 قرار دارد. ثابت کنید که با هیچ دنباله‌ای از اعمال بالا نمی‌توان تمامی اعداد جدول را صفر کرد.
حل
ثابت می‌کنیم همواره مجموع اعداد داخل خانه‌های جدول فرد می‌باشد و بنابراین نمی‌توان به جدولی رسید که تمام اعداد آن صفر باشد:

پس در ابتدا مجموع درایه‌های جدول فرد می‌باشد.
حال فرض کنید مجموع درایه‌های جدول در ابتدا بوده و بعد از یکی از دو حرکتشده است ثابت می‌کنیم باقی مانده و بر دو مساوی است. زیرا اگر حرکت ما حرکت اول باشد چون زوج است داریم



حال فرض کنید حرکت دوم روی درایه انجام شده است و همسایه‌های را تا بگیرید (شکل زیر)، در این صورت:
img/daneshnameh_up/5/5e/com0041v.jpg


و می‌دانیم بر 2 بخش‌پذیر است پس .

مثال

الفدر جدول علامت‌های « + » و « - » را طبق شکل زیر قرار داده‌ایم. می‌توانیم علامت همه خانه‌هایی را که در یک سطر یا یک ستون یا به روی خط راستی موازی یک قطر ( و در حالت خاص یکی از خانه‌های گوشه‌ای) قرار دارند به طور همزمان عوض کنیم ثابت کنید اگر این عمل را هر چند بار انجام دهیم به جدولی نمی‌رسیم که همه علامت‌های آن مثبت باشد.
نکته اصلی
در هر بار تعداد منفی‌ها از نظر زوج و فرد بودن تغییر نمی‌کند.
img/daneshnameh_up/9/91/com0041w.jpg

ب در همه خانه‌های صفحه شطرنجیعلامت مثبت گذاشته‌ایم به استثنای یکی از خانه‌ها (و البته به جز خانه‌های گوشه‌ای که در آن علامت منفی قرار داده‌ایم) در هر عمل می‌توانیم به طور همزمان علامت همه خانه‌های یک سطر یا یک ستون یا خانه‌های روی یک خط راست موازی قطر را تغییر دهیم (و در حالت خاص هر کدام از خانه‌های گوشه‌ای را). ثابت کنید اگر هر چند بار به این ترتیب علامت‌ها را تغییر دهیم به جدولی نمی‌رسیم که همه علامت‌های آن مثبت باشد.
حل
الف هر سطر یا ستون یا قطر مربع تعداد زوجی از 8 خانه علامت‌دار در شکل روبرو را قطع می‌کند بنابراین تعداد منفی‌های واقع در این خانه‌ها را نمی‌توان از زوج به فرد یا از فرد به زوج تغییر داد.
img/daneshnameh_up/7/7c/com0041x.jpg

ب از مربع می‌توان یک مربع را طوری جدا کرد که علامت منفی در آن شبیه حالت (الف) قرار گرفته باشد یعنی در یکی از خانه‌های علامت‌دار قرار بگیرد و در نتیجه چنین کاری ممکن نیست.



مثال

الف در رأس از دوازده ضلعی منتظم علامت منفی و در بقیه رئوس علامت‌ مثبت گذاشته‌ایم. در هر عمل به طور هم‌زمان علامت شش رأس مجاور را عوض می‌کنیم. ثابت کنید نمی‌توان با تکرار چندبار این عمل، به جایی رسید که علامت همه رأس‌ها مثبت باشد.
ب. همین حکم را برای حالتی که به جای شش رأس متوالی علامت‌های چهار رأس متوالی چند ضلعی را عوض کنیم ثابت کنید.
ج. همین حکم را برای موردی ثابت کنید که تصمیم بگیریم به طور همزمان علامت‌های سه رأس متوالی چند ضلعی را عوض کنیم.
حل
الف 12 رأس دوازده ضلعی را به 6 جفت رأس زیر تقسیم می‌کنیم:

در هر عمل در هر زوج تنها یکی از رأس‌ها تغییر علامت می‌دهد. بنابراین در جفت‌های بعد از عمل ام علامت‌های مختلف و بعد از عمل ام علامت‌های یکسان وجود خواهد داشت ولی در جفت ،همه چیز برعکس است. به این ترتیب حالتی پیش نمی‌آید که همه علامت‌ها مثبت باشد.
ب. چهار گروه و در هر گروه سه رأس را در نظر می‌گیریم ، ، ، و مثل حالت‌ قبل استدلال می‌کنیم (فرد یا زوج بودن تعداد منفی‌های هر گروه در هر عمل تغییر می‌کند).
ج. رأس‌ها را به سه گروه و و تقسیم کرده و به همان روش استدلال می‌کنیم.

مثال



سکه در یک ردیف در کنار هم قرار دارند. بعضی از این سکه‌ها به رو و بعضی به پشت قرار گرفته‌اند. در هر حرکت می‌توانیم یکی از این سکه را انتخاب کنیم و آن سکه و سکه‌های مجاور سمت راست و سمت چپ آن را همزمان برگردانیم (از رو به پشت و از پشت به رو). توجه کنید که در صورتی که سکه انتخاب شده یکی از دو سکه‌ انتهایی باشد ، دو سکه و در غیر این صورت سه سکه برگردانده می‌شود.
الف ثابت کنید اگریا باشد به هر ترتیبی که سکه‌ها قرار گرفته باشند با استفاده از چنین حرکت‌هایی می‌توانیم همه سکه‌ها را به رو برگردانیم.
ب ثابت کنید که برای هر که به صورت باشد وضعیت اولیه‌ای وجود دارد که برای آن با استفاده از این حرکت‌ها نمی‌توان این کار را انجام داد (یعنی همه سکه‌ها را به رو برگرداند).
حل
الف. ابتدا ثابت می‌کنیم که برای هر می‌توان با اعمال بالا سکه را به حالتی تبدیل کرد که همهسکه اول (از چپ) به رو و سکه آخر به پشت باشد یا همه سکه به رو باشند.
برای این کار کافی است اولین سکه‌ای که به پشت است در نظر بگیرید و سکه سمت راست آن را انتخاب کنید و عمل برگردان را انجام دهید. به این ترتیب تمام سکه‌ها به جز سکه آخر به رو برگردانده می‌شوند.
با استقراء روی برای حکم را ثابت می‌کنیم. به این ترتیب که آرایشی را که در بالا گفته شده را بدون اینکه سکه آخر را انتخاب کنیم به حالتی که تمام سکه‌ها به رو برگردانده شده‌اند تبدیل می‌کنیم.
برای که واضح است ابتدا سکه دوم و سپس سکه اول را انتخاب می‌کنیم. برای ابتدا سکه و سپس سکهرا برمی‌گردانیم. حال سه سکه آخر به رو هستند و فقط سکه ام به پشت است. حال طبق فرض استقرا این سکه‌ها را برمی‌گردانیم و چون هیچ‌گاه سکه ام را انتخاب نمی‌کنیم پس سه سکه آخری به پشت باقی می‌مانند و حکم به ازایاثبات می‌شود.
برای ابتدا سکه ام را برمی‌گردانیم و سپس سکه باقی می‌ماند که سکه ام به پشت و بقیه به رو می‌باشند. حال مانند قسمت قبل عمل می‌کنیم.
ب. در این قسمت حالتی که تمام سکه‌ها به جز سکه آخری به پشت هستند جواب مسأله است، زیرا اگر به سکه‌ها به تناوب شماره 0 و 1 و 2 بدهیم (مطابق شکل)، در این صورت هربار که یک سکه دارای شماره صفر برگردد یک سکه شماره یک نیز برمی‌گردد و بالعکس ولی تعداد دفعاتی که سکه‌های با شماره یک برمی‌گردند باید فرد باشد و تعداد دفعاتی که سکه‌های با شماره صفر برمی‌گردند باید زوج باشد پس این کار امکان ندارد.
img/daneshnameh_up/8/8d/com0041y.jpg




مثال

تعداد ماتریس‌های با درایه‌های 1 و 1- را پیدا کنید که حاصل‌ضرب عناصر هر سطر آن برابر با 1- و حاصل‌ضرب عناصر هر ستون آن نیز برابر 1- شود. ادعای خود را ثابت کنید.
حل
اولاً باید زیرا در غیر این صورت هیچ ماتریسی با مشخصات بالا وجود ندارد، چون حاصل‌ضرب درایه‌های ماتریس مورد نظر از یک طرف و از طرف دیگرمی‌باشد. حال ثابت می‌کنیم اگر آنگاه تعداد این ماتریس‌ها می‌باشد. برای این کار نشان می‌دهیم که یک تناظر یک به یک بین این ماتریس‌ها و ماتریس‌های که با درایه‌های 1 و 1- پر شده‌اند وجود دراد.
به ازای هر ماتریس یک ماتریس با این خصوصیت وجود دارد زیرا می‌توان درایه‌های سطر ام را به گونه‌ای انتخاب کرد که حاصل‌ضرب درایه‌های هر ستون 1- ‌شود و به طور مشابه درایه‌های ستون ام را می‌توان به گونه‌ای انتخاب کرد که حاصل‌ضرب درایه‌های هرسطر آن 1- شود.
اگر حاصل‌ضرب درایه‌های ماتریس اول و و به ترتیب حاصل‌ضرب درایه‌های فعلی سطر ام و ستون ام باشند داریم و چون بنابراین و بنابراین درایه را می‌توان به گونه‌ای انتخاب کرد که حاصل‌ضرب ستون و سطر آخر 1- شود. توجه کنید که این ماتریس به طور یکتا از روی ماتریس اول به دست می‌آید. به طور مشابه به ازای هر کدام از این ماتریس‌ها از حذف سطر و ستون آخر یک ماتریس به دست می‌آید و حکم اثبات می‌شود.

مثال

یک مهره در صفحه را می‌توان یک خانه به طرف بالا، یک خانه به طرف راست و یا یک خانه در جهت قطری به سمت چپ و پایین حرکت داد (مطابق شکل). مهره را در پایین‌ترین خانه گوشه چپ صفحه قرار داده‌ایم. آیا این مهره می‌تواند از تمام خانه‌های صفحه عبور کند به نحوی که در هر خانه درست یک بار قرار گیرد؟
img/daneshnameh_up/9/97/com0041z.jpg

حل


خیر. این بار صفحه را به سه رنگ مطابق شکل، رنگ‌آمیزی می‌کنیم. (می‌توانید بگویید در حالت کلی در این رنگ‌آمیزی رنگ خانه چیست؟)
img/daneshnameh_up/c/ca/com0041za.jpg

چون باید مهره از یک خانه با رنگ صفر شروع کند مجموعاً 64 خانه را طی می‌کند پس باید 22 خانه به رنگ 1 داشته باشیم زیرا این مهره به هر صورت که حرکت کند رنگ خانه‌هایی که طی می‌کند به تناوب صفر، یک، دو خواهد بود. (چرا؟) ولی به راحتی دیده می‌شود که در رنگ‌آمیزی ما، 21 خانه به رنگ صفر وجود دارد پس این کار ممکن نمی‌باشد.

مثال

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

مثال

هر یک از اضلاع مثلث متساوی‌الاضلاعی را به بخش برابر تقسیم کرده‌ایم. از هر نقطه تقسیم خط‌های راستی موازی ضلع‌ها کشیده‌ایم. به این ترتیب مثلث مفروض به مثلث کوچکتر تقسیم می‌شود. دنباله مثلث‌هایی را یک «زنجیر» می‌نامیم که در آن هیچ مثلثی دوبار تکرار نشده باشد و در ضمن هر مثلث با مثلث قبلی خود در یک ضلع مشترک باشد حداکثر تعداد مثلث‌های یک زنجیر چقدر است؟
حل
مثلث‌ها را به گونه‌ای سیاه و سفید می‌کنیم که هیچ دو مثلث مجاوری هم رنگ نباشند. تعداد مثلث‌های سیاه و تعداد مثلث‌های سفید است و در هر زنجیره، رنگ‌ مثلث‌ها باید یک در میان سیاه و سفید باشد بنابراین یک زنجیره حداکثر شامل مثلث است. (یک زنجیره با این طول به ازای هر بیابید.)

پیوند های خارجی

http://Olympiad.roshd.ir/computer/content/pdf/0143.pdf

همچنین ببینید




تعداد بازدید ها: 16810


ارسال توضیح جدید
الزامی
big grin confused جالب cry eek evil فریاد اخم خبر lol عصبانی mr green خنثی سوال razz redface rolleyes غمگین smile surprised twisted چشمک arrow



از پیوند [http://www.foo.com] یا [http://www.foo.com|شرح] برای پیوندها.
برچسب های HTML در داخل توضیحات مجاز نیستند و تمام نوشته ها ی بین علامت های > و < حذف خواهند شد..