تاریخچه ی:
رنگ آمیزی و همخوانیII
تفاوت با نگارش: 1
| | ||V{maketoc}|| | | ||V{maketoc}|| |
| - | ||__~~navy:@#13::: این مطلب از بخش آموزش وب‌سایت المپیاد یی رشد،انتخاب شده که با فرمت pdf نیز در [http://olympiad.roshd.ir|وب‌سایت المپیاد رشد]موجود می‌باشد. برای مشاهده این موضوعات در وب‌سایت المپیاد، به آدرس [http://olympiad.roshd.ir/computercontentlist.html|فهرست مطالب کامپیوتر] مراجعه کنید. همچنین می‌توانید با کلیک ((مطالب علمی سایت المپیاد رشد|اینجا)) ، با ویژگی‌های بخش آموزش این وب‌سایت آشنا شوید.:: #@~~__|| |
+ | ||__~~navy:@#13::: این مطلب از بخش آموزش وب‌سایت المپیاد کمپیو رشد،انتخاب شده که با فرمت pdf نیز در [http://olympiad.roshd.ir|وب‌سایت المپیاد رشد]موجود می‌باشد. برای مشاهده این موضوعات در وب‌سایت المپیاد، به آدرس [http://olympiad.roshd.ir/computercontentlist.html|فهرست مطالب کامپیوتر] مراجعه کنید. همچنین می‌توانید با کلیک ((مطالب علمی سایت المپیاد رشد|اینجا)) ، با ویژگی‌های بخش آموزش این وب‌سایت آشنا شوید.:: #@~~__|| |
| | ^@#16: | | ^@#16: |
| | !!مثال | | !!مثال |
| | اگر یک جدول {TEX()} {m\times n} {TEX}را با بلوک‌هایی مانند شکل (1) پرکرده باشیم ثابت کنید {TEX()} {8|mn} {TEX} ({TEX()} {mn} {TEX}بر 8 بخش‌پذیر است) | | اگر یک جدول {TEX()} {m\times n} {TEX}را با بلوک‌هایی مانند شکل (1) پرکرده باشیم ثابت کنید {TEX()} {8|mn} {TEX} ({TEX()} {mn} {TEX}بر 8 بخش‌پذیر است) |
| | ::{picture=img/daneshnameh_up/6/6d/com0041u.jpg}:: | | ::{picture=img/daneshnameh_up/6/6d/com0041u.jpg}:: |
| | __اثبات__ | | __اثبات__ |
| - | فرض کنید که در پرکردن جدول از k تا بلوک استفاده کرده باشیم لذا تعداد خانه‌های جدول {TEX()} {4k} {TEX}خواهد بود و لذا {TEX()} {mn=4k} {TEX}. حال اگر خانه‌های جدول را شطرنجی رنگ کنیم، چون به واسطة بالا لااقل یکی از {TEX()} {m} {TEX} و {TEX()} {n} {TEX} زوج است تعداد خانه‌های سیاه و سفید با هم برابرند (چرا؟) از طرفی اگر یک بلوک مانند شکل (1) را در صفحه قرار دهیم خانه‌های 1،2،4 باهم، همرنگ و خانة 3 از رنگ مخالف خواهد بود لذا در کل دو دسته بلوک داریم: |
+ | فرض کنید که در پرکردن جدول از k تا بلوک استفاده کرده باشیم لذا تعداد خانه‌های جدول {TEX()} {4k} {TEX}خواهد بود و لذا {TEX()} {mn=4k} {TEX}. حال اگر خانه‌های جدول را شطرنجی رنگ کنیم، چون به واسطه بالا لااقل یکی از {TEX()} {m} {TEX} و {TEX()} {n} {TEX} زوج است تعداد خانه‌های سیاه و سفید با هم برابرند (چرا؟) از طرفی اگر یک بلوک مانند شکل (1) را در صفحه قرار دهیم خانه‌های 1،2،4 باهم، همرنگ و خانه 3 از رنگ مخالف خواهد بود لذا در کل دو دسته بلوک داریم: |
| | الف.آنهایی که سه خانه سفید و یک خانه سیاه دارند و تعداد آنها را {TEX()} {a} {TEX} فرض می‌کنیم. | | الف.آنهایی که سه خانه سفید و یک خانه سیاه دارند و تعداد آنها را {TEX()} {a} {TEX} فرض می‌کنیم. |
| | ب.آنهایی که سه خانه سیاه و یک خانه سفید دارند و تعداد آنها را با {TEX()} {b} {TEX} فرض می‌کنیم. | | ب.آنهایی که سه خانه سیاه و یک خانه سفید دارند و تعداد آنها را با {TEX()} {b} {TEX} فرض می‌کنیم. |
| | بنابراین داریم که{TEX()} { k = a + b } {TEX} وعلاوه بر این | | بنابراین داریم که{TEX()} { k = a + b } {TEX} وعلاوه بر این |
| | @@{TEX()} {=3\times a+b} {TEX} تعداد خانه‌های سفید جدول@@ | | @@{TEX()} {=3\times a+b} {TEX} تعداد خانه‌های سفید جدول@@ |
| | @@{TEX()} {=3\times b+a} {TEX} تعداد خانه‌های سیاه جدول@@ | | @@{TEX()} {=3\times b+a} {TEX} تعداد خانه‌های سیاه جدول@@ |
| | بنابراین{TEX()} { 3a+b = 3b+a } {TEX} و لذا {TEX()} { a = b } {TEX} پس {TEX()} { k = 2a } {TEX} و لذا{TEX()} { mn = 8a } {TEX} پس {TEX()} {mn} {TEX}بر 8 بخش‌پذیر است. | | بنابراین{TEX()} { 3a+b = 3b+a } {TEX} و لذا {TEX()} { a = b } {TEX} پس {TEX()} { k = 2a } {TEX} و لذا{TEX()} { mn = 8a } {TEX} پس {TEX()} {mn} {TEX}بر 8 بخش‌پذیر است. |
| | --- | | --- |
| | !!مثال | | !!مثال |
| | {TEX()} {a_n,\cdots ,a_2,a_1} {TEX} عددهایی صحیح می‌باشند و اعداد{TEX()} {b_n,\cdots ,b_2,b_1} {TEX}یک جایگشت از آن اعداد است. اگر {TEX()} {n} {TEX}فرد باشد ثابت کنید عدد زیر زوج است: | | {TEX()} {a_n,\cdots ,a_2,a_1} {TEX} عددهایی صحیح می‌باشند و اعداد{TEX()} {b_n,\cdots ,b_2,b_1} {TEX}یک جایگشت از آن اعداد است. اگر {TEX()} {n} {TEX}فرد باشد ثابت کنید عدد زیر زوج است: |
| | @@{TEX()} {(a_1-b_1)(a_2-b_2)\cdots (a_n-b_n)} {TEX}@@ | | @@{TEX()} {(a_1-b_1)(a_2-b_2)\cdots (a_n-b_n)} {TEX}@@ |
| | __حل __ | | __حل __ |
| | __ برهان خلف:__ اگر {TEX()} {(a_1-b_1)(a_2-b_2)\cdots (a_n-b_n)} {TEX}فرد باشد آنگاه هر یک از {TEX()} {n} {TEX}عدد {TEX()} {a_n-b_n,\cdots , a_2-b_2, a_1-b_1} {TEX}باید فرد باشد. پس چون جمع فرد تا عدد فرد، فرد می‌باشد پس باید عدد {TEX()} {\sum_{i=1}^n (a_i-b_i)} {TEX} فرد باشد ولی {TEX()} {\sum_{i=1}^n a_i=\sum_{i=1}^n b_i} {TEX}. بنابراین{TEX()} {\sum_{i=1}^n (a_i-b_i)=0} {TEX} و به تناقض می‌رسیم. بنابراین عدد {TEX()} {(a_1-b_1)(a_2-b_2)\cdots (a_n-b_n)} {TEX} زوج است. | | __ برهان خلف:__ اگر {TEX()} {(a_1-b_1)(a_2-b_2)\cdots (a_n-b_n)} {TEX}فرد باشد آنگاه هر یک از {TEX()} {n} {TEX}عدد {TEX()} {a_n-b_n,\cdots , a_2-b_2, a_1-b_1} {TEX}باید فرد باشد. پس چون جمع فرد تا عدد فرد، فرد می‌باشد پس باید عدد {TEX()} {\sum_{i=1}^n (a_i-b_i)} {TEX} فرد باشد ولی {TEX()} {\sum_{i=1}^n a_i=\sum_{i=1}^n b_i} {TEX}. بنابراین{TEX()} {\sum_{i=1}^n (a_i-b_i)=0} {TEX} و به تناقض می‌رسیم. بنابراین عدد {TEX()} {(a_1-b_1)(a_2-b_2)\cdots (a_n-b_n)} {TEX} زوج است. |
| | --- | | --- |
| | #@ | | #@ |
| | @#16: | | @#16: |
| | !!مثال | | !!مثال |
| | روی محیط دایره‌ای {TEX()} {n} {TEX}عدد صفر و یک به دلخواه قرار داده‌ایم و لااقل یکی از این {TEX()} {n} {TEX}عدد صفر و یکی دیگر یک می‌باشد. سپس در هر مرحله این کار را انجام می‌دهیم: بین هر دو رقم مساوی صفر می‌گذاریم و بین هر دو رقم مختلف یک قرار می‌دهیم و بعد از آن رقم‌های نخستین را پاک می‌کنیم. دوباره در مورد رقم‌های موجود همین عمل را ادامه می‌دهیم و الی آخر . اگر {TEX()} {n} {TEX}فرد باشد، ثابت کنید بعد از انجام تعدادی از این اعمال نمی‌توان به {TEX()} {n} {TEX}عدد صفر رسید. | | روی محیط دایره‌ای {TEX()} {n} {TEX}عدد صفر و یک به دلخواه قرار داده‌ایم و لااقل یکی از این {TEX()} {n} {TEX}عدد صفر و یکی دیگر یک می‌باشد. سپس در هر مرحله این کار را انجام می‌دهیم: بین هر دو رقم مساوی صفر می‌گذاریم و بین هر دو رقم مختلف یک قرار می‌دهیم و بعد از آن رقم‌های نخستین را پاک می‌کنیم. دوباره در مورد رقم‌های موجود همین عمل را ادامه می‌دهیم و الی آخر . اگر {TEX()} {n} {TEX}فرد باشد، ثابت کنید بعد از انجام تعدادی از این اعمال نمی‌توان به {TEX()} {n} {TEX}عدد صفر رسید. |
| | __حل __ | | __حل __ |
| | __ برهان خلف :__ فرض کنید پس از انجام چند عمل مورد نظر تنها عدد صفر باقی مانده باشد. اولین باری که این وضع اتفاق افتاده را در نظر بگیرید. باید در مرحله قبل تمام رقم‌های روی دایره یکسان و غیر صفر باشند. بنابراین باید تمام رقم‌های روی دایره، یک بوده باشند. بنابراین در مرحله قبل از ان نیز هر دو عدد متوالی روی دایره مختلف بوده‌اند. بنابراین در این مرحله باید تعداد رقم‌های صفر و یک برابر باشد و تعداد کل آنها زوج باشد ولی تعداد کل اعداد فرد می‌باشد پس به تناقض می‌رسیم. | | __ برهان خلف :__ فرض کنید پس از انجام چند عمل مورد نظر تنها عدد صفر باقی مانده باشد. اولین باری که این وضع اتفاق افتاده را در نظر بگیرید. باید در مرحله قبل تمام رقم‌های روی دایره یکسان و غیر صفر باشند. بنابراین باید تمام رقم‌های روی دایره، یک بوده باشند. بنابراین در مرحله قبل از ان نیز هر دو عدد متوالی روی دایره مختلف بوده‌اند. بنابراین در این مرحله باید تعداد رقم‌های صفر و یک برابر باشد و تعداد کل آنها زوج باشد ولی تعداد کل اعداد فرد می‌باشد پس به تناقض می‌رسیم. |
| | --- | | --- |
| | !!مثال | | !!مثال |
| | در یک مهمانی {TEX()} {n} {TEX}نفر حضور دارند و هر نفر با تعدادی از مهمان‌ها دست داده است ثابت کنید تعداد افرادی که با تعداد فردی دست داده‌اند زوج است. | | در یک مهمانی {TEX()} {n} {TEX}نفر حضور دارند و هر نفر با تعدادی از مهمان‌ها دست داده است ثابت کنید تعداد افرادی که با تعداد فردی دست داده‌اند زوج است. |
| | __حل __ | | __حل __ |
| | در هر دست دادن دو نفر با هم دست داده‌اند پس تعداد کل دست‌دادن‌ها زوج است. حال اگر دست‌دادن کسانی که با تعداد زوجی دست داده‌اند را از آن کم کنیم نتیجه می‌شود تعداد دست‌دادن‌های کسانی که، تعداد فردی دست داده‌اند زوج است پس چون مجموع چند عدد فرد زوج شده است باید تعداد آنها زوج باشد. و حکم ثابت می‌شود. | | در هر دست دادن دو نفر با هم دست داده‌اند پس تعداد کل دست‌دادن‌ها زوج است. حال اگر دست‌دادن کسانی که با تعداد زوجی دست داده‌اند را از آن کم کنیم نتیجه می‌شود تعداد دست‌دادن‌های کسانی که، تعداد فردی دست داده‌اند زوج است پس چون مجموع چند عدد فرد زوج شده است باید تعداد آنها زوج باشد. و حکم ثابت می‌شود. |
| | --- | | --- |
| | !!مثال | | !!مثال |
| | #@ | | #@ |
| | @#16: | | @#16: |
| - | موشی با خوردن مکعب‌های {TEX()} {1\times 1\times 1} {TEX}در یک قطعه پنیر {TEX()} {3\times 3\times 3} {TEX} راه خود را باز می‌کند و می‌خواهد با تونل‌زدن در این مکعب تمام 27 مکعب{TEX()} {1\times 1\times 1} {TEX}را بخورد. اگر موش کارش را از یک گوشه مکعب شروع کند و هیچ‌گاه به مکعبی که قبلاً خورده است نرود آیا موش می‌تواند کارش را در مرکز مکعب تمام کند. (موش پس از خوردن یک مکعب می‌تواند یکی از مکعب‌های مجاور را بخورد.) |
+ | موشی با خوردن مکعب‌های {TEX()} {1\times 1\times 1} {TEX}در یک قطعه پنیر {TEX()} {3\times 3\times 3} {TEX} راه خود را باز می‌کند و می‌خواهد با تونل‌زدن در این مکعب تمام 27 مکعب{TEX()} {1\times 1\times 1} {TEX}را بخورد. اگر موش کارش را از یک گوشه مکعب شروع کند و هیچ‌گاه به مکعبی که قبلاً خورده است نرود آیا موش می‌تواند کارش را در مرکز ((مکعب)) تمام کند. (موش پس از خوردن یک مکعب می‌تواند یکی از مکعب‌های مجاور را بخورد.) |
| | __حل __ | | __حل __ |
| | در حل این گونه مسائل به سراغ رنگ‌آمیزی می‌رویم. در اینجا اگر 27 مکعب {TEX()} {1\times 1\times 1} {TEX}را یکی در میان سیاه و سفید کنید (یعنی مکعب را مشابه صفحه شطرنج ولی در حالت سه‌بعدی رنگ کنید) موش باید از یک خانه شروع کند و از هر خانه سیاه به یک خانه سفید برود و برعکس در ضمن در انتها باید در خانه سیاه (رنگ خانه مکعب وسطی) برود ولی چون تعداد خانه‌های سفید از خانه‌های سیاه بیشتر است این کار امکان ندارد. (توجه کنید که رنگ خانه‌های گوشه‌ای سفید است.) | | در حل این گونه مسائل به سراغ رنگ‌آمیزی می‌رویم. در اینجا اگر 27 مکعب {TEX()} {1\times 1\times 1} {TEX}را یکی در میان سیاه و سفید کنید (یعنی مکعب را مشابه صفحه شطرنج ولی در حالت سه‌بعدی رنگ کنید) موش باید از یک خانه شروع کند و از هر خانه سیاه به یک خانه سفید برود و برعکس در ضمن در انتها باید در خانه سیاه (رنگ خانه مکعب وسطی) برود ولی چون تعداد خانه‌های سفید از خانه‌های سیاه بیشتر است این کار امکان ندارد. (توجه کنید که رنگ خانه‌های گوشه‌ای سفید است.) |
| | --- | | --- |
| | !!مثال | | !!مثال |
| | یک صفحه شطرنجی {TEX()} {n\times n} {TEX}را که در آن {TEX()} {n} {TEX}عددی زوج است در نظر بگیرید و در هرخانه آن عددی صحیح قرار دارد. دو عمل زیر را روی این صفحه تعریف می‌کنیم: | | یک صفحه شطرنجی {TEX()} {n\times n} {TEX}را که در آن {TEX()} {n} {TEX}عددی زوج است در نظر بگیرید و در هرخانه آن عددی صحیح قرار دارد. دو عمل زیر را روی این صفحه تعریف می‌کنیم: |
| | •به تمام خانه‌های یک سطر یا یک ستون یا یکی از دو قطر عدد دلخواه {TEX()} {k} {TEX}را می‌افزاییم ({TEX()} {k} {TEX}عددی صحیح است و می‌تواند منفی هم باشد). | | •به تمام خانه‌های یک سطر یا یک ستون یا یکی از دو قطر عدد دلخواه {TEX()} {k} {TEX}را می‌افزاییم ({TEX()} {k} {TEX}عددی صحیح است و می‌تواند منفی هم باشد). |
| | •یکی از خانه‌های غیر حاشیه‌ای را انتخاب می‌کنیم و مجموع مربعات اعداد روی هشت همسایه آن را به آن می‌افزاییم و سپس تمام اعداد روی این هشت خانه را به صفر تبدیل می کنیم. | | •یکی از خانه‌های غیر حاشیه‌ای را انتخاب می‌کنیم و مجموع مربعات اعداد روی هشت همسایه آن را به آن می‌افزاییم و سپس تمام اعداد روی این هشت خانه را به صفر تبدیل می کنیم. |
| - | حال جدولی را در نظر بگیرید که در آن عدد خانه‌ای که در سطر {TEX()} {i} {TEX}ام و ستون {TEX()} {j} {TEX}ام قرار دارد برابر {TEX()} { i + j } {TEX} است با این استثناء که در خانه (1 , 1)، عدد 1 قرار دارد. ثابت کنید که با هیچ دنباله‌ای از اعمال بالا نمی‌توان تمامی اعداد جدول را صفر کرد. |
+ | حال جدولی را در نظر بگیرید که در آن عدد خانه‌ای که در سطر {TEX()} {i} {TEX}ام و ستون {TEX()} {j} {TEX}ام قرار دارد برابر {TEX()} { i + j } {TEX} است با این استثناء که در خانه (1 , 1)، عدد 1 قرار دارد. ثابت کنید که با هیچ ((دنباله‌ها|دنباله))ای از اعمال بالا نمی‌توان تمامی اعداد جدول را صفر کرد. |
| | __حل __ | | __حل __ |
| | ثابت می‌کنیم همواره مجموع اعداد داخل خانه‌های جدول فرد می‌باشد و بنابراین نمی‌توان به جدولی رسید که تمام اعداد آن صفر باشد: | | ثابت می‌کنیم همواره مجموع اعداد داخل خانه‌های جدول فرد می‌باشد و بنابراین نمی‌توان به جدولی رسید که تمام اعداد آن صفر باشد: |
| | @@{TEX()} {S=\sum_{i=1}^n \sum_{j=1}^n (i+j)-1 =\sum_{i=1}^n \Biggg(ni+\frac{n(n+1)}{2} \Biggg) -1=\frac{n^2(n+1)}{2}+{n^2(n+1)}{2}-1} {TEX}@@ | | @@{TEX()} {S=\sum_{i=1}^n \sum_{j=1}^n (i+j)-1 =\sum_{i=1}^n \Biggg(ni+\frac{n(n+1)}{2} \Biggg) -1=\frac{n^2(n+1)}{2}+{n^2(n+1)}{2}-1} {TEX}@@ |
| | پس در ابتدا مجموع درایه‌های جدول فرد می‌باشد. | | پس در ابتدا مجموع درایه‌های جدول فرد می‌باشد. |
| | حال فرض کنید مجموع درایه‌های جدول در ابتدا {TEX()} {S} {TEX}بوده و بعد از یکی از دو حرکت{TEX()} {S^\prime} {TEX}شده است ثابت می‌کنیم باقی مانده {TEX()} {S} {TEX}و {TEX()} {S^\prime } {TEX}بر دو مساوی است. زیرا اگر حرکت ما حرکت اول باشد چون {TEX()} {n} {TEX}زوج است داریم | | حال فرض کنید مجموع درایه‌های جدول در ابتدا {TEX()} {S} {TEX}بوده و بعد از یکی از دو حرکت{TEX()} {S^\prime} {TEX}شده است ثابت می‌کنیم باقی مانده {TEX()} {S} {TEX}و {TEX()} {S^\prime } {TEX}بر دو مساوی است. زیرا اگر حرکت ما حرکت اول باشد چون {TEX()} {n} {TEX}زوج است داریم |
| | #@ | | #@ |
| | @#16: | | @#16: |
| | @@{TEX()} {S^\prime =S+kn \ \Rightarrow \ S^\prime \equiv S \quad (mod \ 2)} {TEX}@@ | | @@{TEX()} {S^\prime =S+kn \ \Rightarrow \ S^\prime \equiv S \quad (mod \ 2)} {TEX}@@ |
| | حال فرض کنید حرکت دوم روی درایه {TEX()} {a_9} {TEX}انجام شده است و همسایه‌های {TEX()} {a_9} {TEX}را {TEX()} {a_1} {TEX}تا {TEX()} {a_8} {TEX}بگیرید (شکل زیر)، در این صورت: | | حال فرض کنید حرکت دوم روی درایه {TEX()} {a_9} {TEX}انجام شده است و همسایه‌های {TEX()} {a_9} {TEX}را {TEX()} {a_1} {TEX}تا {TEX()} {a_8} {TEX}بگیرید (شکل زیر)، در این صورت: |
| | ::{picture=img/daneshnameh_up/5/5e/com0041v.jpg}:: | | ::{picture=img/daneshnameh_up/5/5e/com0041v.jpg}:: |
| | @@{TEX()} {S^\prime =S- \Big(a_1+a_2+\cdots +a_8 \Big)+\Big( a_1^2+a_2^2+\cdots +a_8^2 \Big) =S-\sum_{i=1}^8 a_i(a_i-1)} {TEX}@@ | | @@{TEX()} {S^\prime =S- \Big(a_1+a_2+\cdots +a_8 \Big)+\Big( a_1^2+a_2^2+\cdots +a_8^2 \Big) =S-\sum_{i=1}^8 a_i(a_i-1)} {TEX}@@ |
| | و می‌دانیم{TEX()} {a_i(a_i-1)} {TEX} بر 2 بخش‌پذیر است پس {TEX()} {S\equiv S^\prime \quad (mod \ 2)} {TEX} . | | و می‌دانیم{TEX()} {a_i(a_i-1)} {TEX} بر 2 بخش‌پذیر است پس {TEX()} {S\equiv S^\prime \quad (mod \ 2)} {TEX} . |
| | --- | | --- |
| | !!مثال | | !!مثال |
| | __ الف__در جدول {TEX()} {4\times 4} {TEX}علامت‌های « + » و « - » را طبق شکل زیر قرار داده‌ایم. می‌توانیم علامت همه خانه‌هایی را که در یک سطر یا یک ستون یا به روی خط راستی موازی یک قطر ( و در حالت خاص یکی از خانه‌های گوشه‌ای) قرار دارند به طور همزمان عوض کنیم ثابت کنید اگر این عمل را هر چند بار انجام دهیم به جدولی نمی‌رسیم که همه علامت‌های آن مثبت باشد. | | __ الف__در جدول {TEX()} {4\times 4} {TEX}علامت‌های « + » و « - » را طبق شکل زیر قرار داده‌ایم. می‌توانیم علامت همه خانه‌هایی را که در یک سطر یا یک ستون یا به روی خط راستی موازی یک قطر ( و در حالت خاص یکی از خانه‌های گوشه‌ای) قرار دارند به طور همزمان عوض کنیم ثابت کنید اگر این عمل را هر چند بار انجام دهیم به جدولی نمی‌رسیم که همه علامت‌های آن مثبت باشد. |
| - | __نکتة اصلی__ |
+ | __نکته اصلی__ |
| | در هر بار تعداد منفی‌ها از نظر زوج و فرد بودن تغییر نمی‌کند. | | در هر بار تعداد منفی‌ها از نظر زوج و فرد بودن تغییر نمی‌کند. |
| | ::{picture=img/daneshnameh_up/9/91/com0041w.jpg}:: | | ::{picture=img/daneshnameh_up/9/91/com0041w.jpg}:: |
| - | __ب__ در همة خانه‌های صفحه شطرنجی{TEX()} {8\times 8} {TEX}علامت مثبت گذاشته‌ایم به استثنای یکی از خانه‌ها (و البته به جز خانه‌های گوشه‌ای که در آن علامت منفی قرار داده‌ایم) در هر عمل می‌توانیم به طور همزمان علامت همه خانه‌های یک سطر یا یک ستون یا خانه‌های روی یک خط راست موازی قطر را تغییر دهیم (و در حالت خاص هر کدام از خانه‌های گوشه‌ای را). ثابت کنید اگر هر چند بار به این ترتیب علامت‌ها را تغییر دهیم به جدولی نمی‌رسیم که همه علامت‌های آن مثبت باشد. |
+ | __ب__ در همه خانه‌های صفحه شطرنجی{TEX()} {8\times 8} {TEX}علامت مثبت گذاشته‌ایم به استثنای یکی از خانه‌ها (و البته به جز خانه‌های گوشه‌ای که در آن علامت منفی قرار داده‌ایم) در هر عمل می‌توانیم به طور همزمان علامت همه خانه‌های یک سطر یا یک ستون یا خانه‌های روی یک خط راست موازی قطر را تغییر دهیم (و در حالت خاص هر کدام از خانه‌های گوشه‌ای را). ثابت کنید اگر هر چند بار به این ترتیب علامت‌ها را تغییر دهیم به جدولی نمی‌رسیم که همه علامت‌های آن مثبت باشد. |
| | __حل__ | | __حل__ |
| | __ الف__ هر سطر یا ستون یا قطر مربع تعداد زوجی از 8 خانه علامت‌دار در شکل روبرو را قطع می‌کند بنابراین تعداد منفی‌های واقع در این خانه‌ها را نمی‌توان از زوج به فرد یا از فرد به زوج تغییر داد. | | __ الف__ هر سطر یا ستون یا قطر مربع تعداد زوجی از 8 خانه علامت‌دار در شکل روبرو را قطع می‌کند بنابراین تعداد منفی‌های واقع در این خانه‌ها را نمی‌توان از زوج به فرد یا از فرد به زوج تغییر داد. |
| | ::{picture=img/daneshnameh_up/7/7c/com0041x.jpg}:: | | ::{picture=img/daneshnameh_up/7/7c/com0041x.jpg}:: |
| | __ب__ از مربع {TEX()} {8\times 8} {TEX}می‌توان یک مربع {TEX()} {4\times 4} {TEX}را طوری جدا کرد که علامت منفی در آن شبیه حالت (الف) قرار گرفته باشد یعنی در یکی از خانه‌های علامت‌دار قرار بگیرد و در نتیجه چنین کاری ممکن نیست. | | __ب__ از مربع {TEX()} {8\times 8} {TEX}می‌توان یک مربع {TEX()} {4\times 4} {TEX}را طوری جدا کرد که علامت منفی در آن شبیه حالت (الف) قرار گرفته باشد یعنی در یکی از خانه‌های علامت‌دار قرار بگیرد و در نتیجه چنین کاری ممکن نیست. |
| | --- | | --- |
| | #@ | | #@ |
| | @#16: | | @#16: |
| | !!مثال | | !!مثال |
| - | __ الف__ در رأس {TEX()} {A_1} {TEX}از دوازده ضلعی منتظم {TEX()} {A_1A_2\cdots A_{12}} {TEX} علامت منفی و در بقیة رئوس علامت مثبت گذاشته‌ایم. در هر عمل به طور همزمان علامت شش رأس مجاور را عوض می‌کنیم. ثابت کنید نمی‌توان با تکرار چندبار این عمل، به جایی رسید که علامت همه رأس‌ها مثبت باشد. |
+ | __ الف__ در رأس {TEX()} {A_1} {TEX}از دوازده ضلعی منتظم {TEX()} {A_1A_2\cdots A_{12}} {TEX} علامت منفی و در بقیه رئوس علامت مثبت گذاشته‌ایم. در هر عمل به طور همزمان علامت شش رأس مجاور را عوض می‌کنیم. ثابت کنید نمی‌توان با تکرار چندبار این عمل، به جایی رسید که علامت همه رأس‌ها مثبت باشد. |
| | __ب.__ همین حکم را برای حالتی که به جای شش رأس متوالی علامت‌های چهار رأس متوالی چند ضلعی را عوض کنیم ثابت کنید. | | __ب.__ همین حکم را برای حالتی که به جای شش رأس متوالی علامت‌های چهار رأس متوالی چند ضلعی را عوض کنیم ثابت کنید. |
| | __ج.__ همین حکم را برای موردی ثابت کنید که تصمیم بگیریم به طور همزمان علامت‌های سه رأس متوالی چند ضلعی را عوض کنیم. | | __ج.__ همین حکم را برای موردی ثابت کنید که تصمیم بگیریم به طور همزمان علامت‌های سه رأس متوالی چند ضلعی را عوض کنیم. |
| | __حل__ | | __حل__ |
| | __الف__ 12 رأس دوازده ضلعی را به 6 جفت رأس زیر تقسیم می‌کنیم: | | __الف__ 12 رأس دوازده ضلعی را به 6 جفت رأس زیر تقسیم می‌کنیم: |
| | @@{TEX()} { A_6 A_{12},\cdots , A_2 A_8 , A_1 A_7} {TEX}@@ | | @@{TEX()} { A_6 A_{12},\cdots , A_2 A_8 , A_1 A_7} {TEX}@@ |
| | در هر عمل در هر زوج تنها یکی از رأس‌ها تغییر علامت می‌دهد. بنابراین در جفت‌های{TEX()} { A_6 A_{12} , \cdots , A_2 A_8} {TEX} بعد از عمل{TEX()} { (2k – 1)} {TEX} ام علامت‌های مختلف و بعد از عمل {TEX()} {(2k)} {TEX} ام علامت‌های یکسان وجود خواهد داشت ولی در جفت{TEX()} { A_1 A_7 } {TEX} ،همه چیز برعکس است. به این ترتیب حالتی پیش نمی‌آید که همه علامت‌ها مثبت باشد. | | در هر عمل در هر زوج تنها یکی از رأس‌ها تغییر علامت می‌دهد. بنابراین در جفت‌های{TEX()} { A_6 A_{12} , \cdots , A_2 A_8} {TEX} بعد از عمل{TEX()} { (2k – 1)} {TEX} ام علامت‌های مختلف و بعد از عمل {TEX()} {(2k)} {TEX} ام علامت‌های یکسان وجود خواهد داشت ولی در جفت{TEX()} { A_1 A_7 } {TEX} ،همه چیز برعکس است. به این ترتیب حالتی پیش نمی‌آید که همه علامت‌ها مثبت باشد. |
| | __ب.__ چهار گروه و در هر گروه سه رأس را در نظر می‌گیریم {TEX()} { A_1 A_5 A_9 } {TEX} ، {TEX()} { A_2 A_6 A_{10} } {TEX} ، {TEX()} { A_3 A_7 A_{11} } {TEX} ، {TEX()} { A_4 A_8 A_{12}} {TEX} و مثل حالت قبل استدلال می‌کنیم (فرد یا زوج بودن تعداد منفی‌های هر گروه در هر عمل تغییر می‌کند). | | __ب.__ چهار گروه و در هر گروه سه رأس را در نظر می‌گیریم {TEX()} { A_1 A_5 A_9 } {TEX} ، {TEX()} { A_2 A_6 A_{10} } {TEX} ، {TEX()} { A_3 A_7 A_{11} } {TEX} ، {TEX()} { A_4 A_8 A_{12}} {TEX} و مثل حالت قبل استدلال می‌کنیم (فرد یا زوج بودن تعداد منفی‌های هر گروه در هر عمل تغییر می‌کند). |
| | __ج.__ رأس‌ها را به سه گروه {TEX()} { A_1 A_4 A_7 A_{10} } {TEX} و{TEX()} { A_2 A_5 A_8 A_{11}} {TEX} و{TEX()} { A_3 A_6 A_9 A_{12} } {TEX} تقسیم کرده و به همان روش استدلال می‌کنیم. | | __ج.__ رأس‌ها را به سه گروه {TEX()} { A_1 A_4 A_7 A_{10} } {TEX} و{TEX()} { A_2 A_5 A_8 A_{11}} {TEX} و{TEX()} { A_3 A_6 A_9 A_{12} } {TEX} تقسیم کرده و به همان روش استدلال می‌کنیم. |
| | --- | | --- |
| | !!مثال | | !!مثال |
| | #@ | | #@ |
| | @#16: | | @#16: |
| | {TEX()} {n} {TEX}سکه در یک ردیف در کنار هم قرار دارند. بعضی از این سکه‌ها به رو و بعضی به پشت قرار گرفته‌اند. در هر حرکت می‌توانیم یکی از این {TEX()} {n} {TEX}سکه را انتخاب کنیم و آن سکه و سکه‌های مجاور سمت راست و سمت چپ آن را همزمان برگردانیم (از رو به پشت و از پشت به رو). توجه کنید که در صورتی که سکه انتخاب شده یکی از دو سکه انتهایی باشد ، دو سکه و در غیر این صورت سه سکه برگردانده می‌شود. | | {TEX()} {n} {TEX}سکه در یک ردیف در کنار هم قرار دارند. بعضی از این سکه‌ها به رو و بعضی به پشت قرار گرفته‌اند. در هر حرکت می‌توانیم یکی از این {TEX()} {n} {TEX}سکه را انتخاب کنیم و آن سکه و سکه‌های مجاور سمت راست و سمت چپ آن را همزمان برگردانیم (از رو به پشت و از پشت به رو). توجه کنید که در صورتی که سکه انتخاب شده یکی از دو سکه انتهایی باشد ، دو سکه و در غیر این صورت سه سکه برگردانده می‌شود. |
| | __الف__ ثابت کنید اگر{TEX()} { n = 3k } {TEX}یا {TEX()} { n = 3k + 1} {TEX} باشد به هر ترتیبی که سکه‌ها قرار گرفته باشند با استفاده از چنین حرکت‌هایی می‌توانیم همه سکه‌ها را به رو برگردانیم. | | __الف__ ثابت کنید اگر{TEX()} { n = 3k } {TEX}یا {TEX()} { n = 3k + 1} {TEX} باشد به هر ترتیبی که سکه‌ها قرار گرفته باشند با استفاده از چنین حرکت‌هایی می‌توانیم همه سکه‌ها را به رو برگردانیم. |
| | __ب__ ثابت کنید که برای هر {TEX()} {n} {TEX}که به صورت{TEX()} { 3k + 2} {TEX} باشد وضعیت اولیه‌ای وجود دارد که برای آن با استفاده از این حرکت‌ها نمی‌توان این کار را انجام داد (یعنی همه سکه‌ها را به رو برگرداند). | | __ب__ ثابت کنید که برای هر {TEX()} {n} {TEX}که به صورت{TEX()} { 3k + 2} {TEX} باشد وضعیت اولیه‌ای وجود دارد که برای آن با استفاده از این حرکت‌ها نمی‌توان این کار را انجام داد (یعنی همه سکه‌ها را به رو برگرداند). |
| | __حل __ | | __حل __ |
| - | __ الف.__ ابتدا ثابت می‌کنیم که برای هر {TEX()} {n} {TEX}می‌توان با اعمال بالا سکه را به حالتی تبدیل کرد که همه{TEX()} { n - 1 } {TEX}سکه اول (از چپ) به رو و سکه آخر به پشت باشد یا همة {TEX()} {n} {TEX}سکه به رو باشند. |
+ | __ الف.__ ابتدا ثابت می‌کنیم که برای هر {TEX()} {n} {TEX}می‌توان با اعمال بالا سکه را به حالتی تبدیل کرد که همه{TEX()} { n - 1 } {TEX}سکه اول (از چپ) به رو و سکه آخر به پشت باشد یا همه {TEX()} {n} {TEX}سکه به رو باشند. |
| | برای این کار کافی است اولین سکه‌ای که به پشت است در نظر بگیرید و سکه سمت راست آن را انتخاب کنید و عمل برگردان را انجام دهید. به این ترتیب تمام سکه‌ها به جز سکه آخر به رو برگردانده می‌شوند. | | برای این کار کافی است اولین سکه‌ای که به پشت است در نظر بگیرید و سکه سمت راست آن را انتخاب کنید و عمل برگردان را انجام دهید. به این ترتیب تمام سکه‌ها به جز سکه آخر به رو برگردانده می‌شوند. |
| | با استقراء روی {TEX()} {k} {TEX}برای{TEX()} { n = 3k } {TEX} حکم را ثابت می‌کنیم. به این ترتیب که آرایشی را که در بالا گفته شده را بدون اینکه سکه آخر را انتخاب کنیم به حالتی که تمام سکه‌ها به رو برگردانده شده‌اند تبدیل می‌کنیم. | | با استقراء روی {TEX()} {k} {TEX}برای{TEX()} { n = 3k } {TEX} حکم را ثابت می‌کنیم. به این ترتیب که آرایشی را که در بالا گفته شده را بدون اینکه سکه آخر را انتخاب کنیم به حالتی که تمام سکه‌ها به رو برگردانده شده‌اند تبدیل می‌کنیم. |
| | برای{TEX()} { n = 3 } {TEX} که واضح است ابتدا سکه دوم و سپس سکه اول را انتخاب می‌کنیم. برای {TEX()} { n = 3k + 3} {TEX} ابتدا سکه{TEX()} { 3k + 2} {TEX} و سپس سکه{TEX()} { 3k + 1 } {TEX}را برمی‌گردانیم. حال سه سکه آخر به رو هستند و فقط سکه {TEX()} {3k} {TEX}ام به پشت است. حال طبق فرض استقرا این سکه‌ها را برمی‌گردانیم و چون هیچ‌گاه سکه {TEX()} {3k} {TEX}ام را انتخاب نمی‌کنیم پس سه سکه آخری به پشت باقی می‌مانند و حکم به ازای{TEX()} { n = 3k } {TEX}اثبات می‌شود. | | برای{TEX()} { n = 3 } {TEX} که واضح است ابتدا سکه دوم و سپس سکه اول را انتخاب می‌کنیم. برای {TEX()} { n = 3k + 3} {TEX} ابتدا سکه{TEX()} { 3k + 2} {TEX} و سپس سکه{TEX()} { 3k + 1 } {TEX}را برمی‌گردانیم. حال سه سکه آخر به رو هستند و فقط سکه {TEX()} {3k} {TEX}ام به پشت است. حال طبق فرض استقرا این سکه‌ها را برمی‌گردانیم و چون هیچ‌گاه سکه {TEX()} {3k} {TEX}ام را انتخاب نمی‌کنیم پس سه سکه آخری به پشت باقی می‌مانند و حکم به ازای{TEX()} { n = 3k } {TEX}اثبات می‌شود. |
| | برای {TEX()} { n =3k + 1} {TEX} ابتدا سکه {TEX()} {3k + 1} {TEX} ام را برمی‌گردانیم و سپس {TEX()} {3k} {TEX}سکه باقی می‌ماند که سکه {TEX()} {3k} {TEX}ام به پشت و بقیه به رو می‌باشند. حال مانند قسمت قبل عمل می‌کنیم. | | برای {TEX()} { n =3k + 1} {TEX} ابتدا سکه {TEX()} {3k + 1} {TEX} ام را برمی‌گردانیم و سپس {TEX()} {3k} {TEX}سکه باقی می‌ماند که سکه {TEX()} {3k} {TEX}ام به پشت و بقیه به رو می‌باشند. حال مانند قسمت قبل عمل می‌کنیم. |
| | __ب.__ در این قسمت حالتی که تمام سکه‌ها به جز سکه آخری به پشت هستند جواب مسأله است، زیرا اگر به سکه‌ها به تناوب شماره 0 و 1 و 2 بدهیم (مطابق شکل)، در این صورت هربار که یک سکه دارای شماره صفر برگردد یک سکه شماره یک نیز برمی‌گردد و بالعکس ولی تعداد دفعاتی که سکه‌های با شماره یک برمی‌گردند باید فرد باشد و تعداد دفعاتی که سکه‌های با شماره صفر برمی‌گردند باید زوج باشد پس این کار امکان ندارد. | | __ب.__ در این قسمت حالتی که تمام سکه‌ها به جز سکه آخری به پشت هستند جواب مسأله است، زیرا اگر به سکه‌ها به تناوب شماره 0 و 1 و 2 بدهیم (مطابق شکل)، در این صورت هربار که یک سکه دارای شماره صفر برگردد یک سکه شماره یک نیز برمی‌گردد و بالعکس ولی تعداد دفعاتی که سکه‌های با شماره یک برمی‌گردند باید فرد باشد و تعداد دفعاتی که سکه‌های با شماره صفر برمی‌گردند باید زوج باشد پس این کار امکان ندارد. |
| | ::{picture=img/daneshnameh_up/8/8d/com0041y.jpg}:: | | ::{picture=img/daneshnameh_up/8/8d/com0041y.jpg}:: |
| | --- | | --- |
| | #@ | | #@ |
| | @#16: | | @#16: |
| | !!مثال | | !!مثال |
| | تعداد ماتریس‌های {TEX()} {m\times n} {TEX}با درایه‌های 1 و 1- را پیدا کنید که حاصل‌ضرب عناصر هر سطر آن برابر با 1- و حاصل‌ضرب عناصر هر ستون آن نیز برابر 1- شود. ادعای خود را ثابت کنید. | | تعداد ماتریس‌های {TEX()} {m\times n} {TEX}با درایه‌های 1 و 1- را پیدا کنید که حاصل‌ضرب عناصر هر سطر آن برابر با 1- و حاصل‌ضرب عناصر هر ستون آن نیز برابر 1- شود. ادعای خود را ثابت کنید. |
| | __حل__ | | __حل__ |
| | اولاً باید {TEX()} {m\equiv n \quad (mod \ 2)} {TEX} زیرا در غیر این صورت هیچ ماتریسی با مشخصات بالا وجود ندارد، چون حاصل‌ضرب درایه‌های ماتریس مورد نظر از یک طرف {TEX()} {(-1)^m} {TEX} و از طرف دیگر{TEX()} {(-1)^n} {TEX}می‌باشد. حال ثابت می‌کنیم اگر {TEX()} {m\equiv n \quad (mod \ 2)} {TEX} آنگاه تعداد این ماتریس‌ها{TEX()} {2^{(m-1)(n-1)} {TEX} می‌باشد. برای این کار نشان می‌دهیم که یک تناظر یک به یک بین این ماتریس‌ها و ماتریس‌های {TEX()} {(m-1)\times (n-1)} {TEX} که با درایه‌های 1 و 1- پر شده‌اند وجود دراد. | | اولاً باید {TEX()} {m\equiv n \quad (mod \ 2)} {TEX} زیرا در غیر این صورت هیچ ماتریسی با مشخصات بالا وجود ندارد، چون حاصل‌ضرب درایه‌های ماتریس مورد نظر از یک طرف {TEX()} {(-1)^m} {TEX} و از طرف دیگر{TEX()} {(-1)^n} {TEX}می‌باشد. حال ثابت می‌کنیم اگر {TEX()} {m\equiv n \quad (mod \ 2)} {TEX} آنگاه تعداد این ماتریس‌ها{TEX()} {2^{(m-1)(n-1)} {TEX} می‌باشد. برای این کار نشان می‌دهیم که یک تناظر یک به یک بین این ماتریس‌ها و ماتریس‌های {TEX()} {(m-1)\times (n-1)} {TEX} که با درایه‌های 1 و 1- پر شده‌اند وجود دراد. |
| | به ازای هر ماتریس {TEX()} {(m-1)\times (n-1)} {TEX} یک ماتریس با این خصوصیت وجود دارد زیرا می‌توان درایه‌های سطر {TEX()} {m} {TEX}ام را به گونه‌ای انتخاب کرد که حاصل‌ضرب درایه‌های هر{TEX()} {(n-1)} {TEX} ستون 1- شود و به طور مشابه درایه‌های ستون {TEX()} {n} {TEX}ام را می‌توان به گونه‌ای انتخاب کرد که حاصل‌ضرب درایه‌های هر{TEX()} {(m-1)} {TEX}سطر آن 1- شود. | | به ازای هر ماتریس {TEX()} {(m-1)\times (n-1)} {TEX} یک ماتریس با این خصوصیت وجود دارد زیرا می‌توان درایه‌های سطر {TEX()} {m} {TEX}ام را به گونه‌ای انتخاب کرد که حاصل‌ضرب درایه‌های هر{TEX()} {(n-1)} {TEX} ستون 1- شود و به طور مشابه درایه‌های ستون {TEX()} {n} {TEX}ام را می‌توان به گونه‌ای انتخاب کرد که حاصل‌ضرب درایه‌های هر{TEX()} {(m-1)} {TEX}سطر آن 1- شود. |
| - | اگر {TEX()} {M} {TEX}حاصل‌ضرب درایه‌های ماتریس اول و {TEX()} {A} {TEX}و {TEX()} {B} {TEX}به ترتیب حاصل‌ضرب درایه‌های فعلی سطر {TEX()} {m} {TEX}ام و ستون {TEX()} {n} {TEX}ام باشند داریم {TEX()} {M=\frac{(-1)^{m-1}}{B}=\frac{(-1)^{n-1}}{A}} {TEX} و چون {TEX()} {m\equiv n \quad (mod \ 2)} {TEX} بنابراین{TEX()} { A = B } {TEX} و بنابراین درایه{TEX()} {(m , n) } {TEX} را می‌توان به گونه‌ای انتخاب کرد که حاصل‌ضرب ستون و سطر آخر 1- شود. توجه کنید که این ماتریس به طور یکتا از روی ماتریس اول به دست می‌آید. به طور مشابه به ازای هر کدام از این ماتریس‌ها از حذف سطر و ستون آخر یک ماتریس {TEX()} {(m-1)\times (n-1)} {TEX}به دست می‌آید و حکم اثبات می‌شود. |
+ | اگر {TEX()} {M} {TEX}حاصل‌ضرب درایه‌های ماتریس اول و {TEX()} {A} {TEX}و {TEX()} {B} {TEX}به ترتیب حاصل‌ضرب درایه‌های فعلی سطر {TEX()} {m} {TEX}ام و ستون {TEX()} {n} {TEX}ام باشند داریم {TEX()} {M=\frac{(-1)^{m-1}}{B}=\frac{(-1)^{n-1}}{A}} {TEX} و چون {TEX()} {m\equiv n \quad (mod \ 2)} {TEX} بنابراین{TEX()} { A = B } {TEX} و بنابراین درایه{TEX()} {(m , n) } {TEX} را می‌توان به گونه‌ای انتخاب کرد که حاصل‌ضرب ستون و سطر آخر 1- شود. توجه کنید که این ماتریس به طور یکتا از روی ماتریس اول به دست می‌آید. به طور مشابه به ازای هر کدام از این ماتریس‌ها از حذف سطر و ستون آخر یک ((ماتریس)) {TEX()} {(m-1)\times (n-1)} {TEX}به دست می‌آید و حکم اثبات می‌شود. |
| | --- | | --- |
| | !!مثال | | !!مثال |
| | یک مهره در صفحه {TEX()} {8\times 8} {TEX}را می‌توان یک خانه به طرف بالا، یک خانه به طرف راست و یا یک خانه در جهت قطری به سمت چپ و پایین حرکت داد (مطابق شکل). مهره را در پایین‌ترین خانه گوشه چپ صفحه قرار داده‌ایم. آیا این مهره می‌تواند از تمام خانه‌های صفحه عبور کند به نحوی که در هر خانه درست یک بار قرار گیرد؟ | | یک مهره در صفحه {TEX()} {8\times 8} {TEX}را می‌توان یک خانه به طرف بالا، یک خانه به طرف راست و یا یک خانه در جهت قطری به سمت چپ و پایین حرکت داد (مطابق شکل). مهره را در پایین‌ترین خانه گوشه چپ صفحه قرار داده‌ایم. آیا این مهره می‌تواند از تمام خانه‌های صفحه عبور کند به نحوی که در هر خانه درست یک بار قرار گیرد؟ |
| | ::{picture=img/daneshnameh_up/9/97/com0041z.jpg}:: | | ::{picture=img/daneshnameh_up/9/97/com0041z.jpg}:: |
| | __حل __ | | __حل __ |
| | #@ | | #@ |
| | @#16: | | @#16: |
| | خیر. این بار صفحه را به سه رنگ مطابق شکل، رنگ‌آمیزی می‌کنیم. (می‌توانید بگویید در حالت کلی در این رنگ‌آمیزی رنگ خانه{TEX()} { (i , j) } {TEX} چیست؟) | | خیر. این بار صفحه را به سه رنگ مطابق شکل، رنگ‌آمیزی می‌کنیم. (می‌توانید بگویید در حالت کلی در این رنگ‌آمیزی رنگ خانه{TEX()} { (i , j) } {TEX} چیست؟) |
| | ::{picture=img/daneshnameh_up/c/ca/com0041za.jpg}:: | | ::{picture=img/daneshnameh_up/c/ca/com0041za.jpg}:: |
| | چون باید مهره از یک خانه با رنگ صفر شروع کند مجموعاً 64 خانه را طی می‌کند پس باید 22 خانه به رنگ 1 داشته باشیم زیرا این مهره به هر صورت که حرکت کند رنگ خانه‌هایی که طی می‌کند به تناوب صفر، یک، دو خواهد بود. (چرا؟) ولی به راحتی دیده می‌شود که در رنگ‌آمیزی ما، 21 خانه به رنگ صفر وجود دارد پس این کار ممکن نمی‌باشد. | | چون باید مهره از یک خانه با رنگ صفر شروع کند مجموعاً 64 خانه را طی می‌کند پس باید 22 خانه به رنگ 1 داشته باشیم زیرا این مهره به هر صورت که حرکت کند رنگ خانه‌هایی که طی می‌کند به تناوب صفر، یک، دو خواهد بود. (چرا؟) ولی به راحتی دیده می‌شود که در رنگ‌آمیزی ما، 21 خانه به رنگ صفر وجود دارد پس این کار ممکن نمی‌باشد. |
| | --- | | --- |
| | !!مثال | | !!مثال |
| | یک دایره را به {TEX()} {n} {TEX}قطاع تقسیم کرده‌ایم و در هر قطاع یک مهره گذاشته‌ایم در هر حرکت دو مهره را به قطاع‌های مجاور منتقل می‌کنیم مشروط به اینکه یکی از دو انتقال در جهت حرکت عقربه‌های ساعت و دیگری در خلاف آن باشد. در صورتی که {TEX()} {n} {TEX}زوج باشد آیا می‌توان با تکرار این عمل همه مهره‌ها را در یک قطاع گردآورد؟ | | یک دایره را به {TEX()} {n} {TEX}قطاع تقسیم کرده‌ایم و در هر قطاع یک مهره گذاشته‌ایم در هر حرکت دو مهره را به قطاع‌های مجاور منتقل می‌کنیم مشروط به اینکه یکی از دو انتقال در جهت حرکت عقربه‌های ساعت و دیگری در خلاف آن باشد. در صورتی که {TEX()} {n} {TEX}زوج باشد آیا می‌توان با تکرار این عمل همه مهره‌ها را در یک قطاع گردآورد؟ |
| | __حل __ | | __حل __ |
| - | به هر یک از این {TEX()} {n} {TEX}قطاع به ترتیب یک شماره از صفر تا {TEX()} {n-1} {TEX} را نسبت می‌دهیم. حال به هر آرایش عدد {TEX()} {k} {TEX}را نسبت می‌دهیم که برابر است با مجموع شمارة خانه‌های این {TEX()} {n} {TEX}مهره.
در یک انتقال یک واحد به {TEX()} {k} {TEX} (به هنگ {TEX()} {n} {TEX}) اضافه و در انتقال دیگر یک واحد (به هنگ {TEX()} {n} {TEX}) کم می‌شود. بنابراین باقیماندة {TEX()} {k} {TEX}بر {TEX()} {n} {TEX}در هر حرکت ثابت می‌ماند از طرف دیگر در شروع کار {TEX()} {k} {TEX}برابر است با مجموع اعداد صفر تا {TEX()} {n-1} {TEX} و اگر {TEX()} {n} {TEX}زوج باشند این عدد بر {TEX()} {n} {TEX}بخش‌پذیر نیست. (چرا؟) ولی اگر همه مهره‌ها در نهایت در یک قطاع باشند باید باقیمانده {TEX()} {k} {TEX}بر {TEX()} {n} {TEX}برابر صفر گردد و این خلاف این است که در هر حرکت باقیمانده {TEX()} {k} {TEX}بر {TEX()} {n} {TEX}تغییری نمی‌کند. (منظور از {TEX()} {k} {TEX}به هنگ {TEX()} {n} {TEX}باقیمانده {TEX()} {k} {TEX}بر {TEX()} {n} {TEX}است .) |
+ | به هر یک از این {TEX()} {n} {TEX}قطاع به ترتیب یک شماره از صفر تا {TEX()} {n-1} {TEX} را نسبت می‌دهیم. حال به هر آرایش عدد {TEX()} {k} {TEX}را نسبت می‌دهیم که برابر است با مجموع شماره خانه‌های این {TEX()} {n} {TEX}مهره.
در یک انتقال یک واحد به {TEX()} {k} {TEX} (به هنگ {TEX()} {n} {TEX}) اضافه و در انتقال دیگر یک واحد (به هنگ {TEX()} {n} {TEX}) کم می‌شود. بنابراین باقیمانده {TEX()} {k} {TEX}بر {TEX()} {n} {TEX}در هر حرکت ثابت می‌ماند از طرف دیگر در شروع کار {TEX()} {k} {TEX}برابر است با مجموع اعداد صفر تا {TEX()} {n-1} {TEX} و اگر {TEX()} {n} {TEX}زوج باشند این عدد بر {TEX()} {n} {TEX}بخش‌پذیر نیست. (چرا؟) ولی اگر همه مهره‌ها در نهایت در یک قطاع باشند باید باقیمانده {TEX()} {k} {TEX}بر {TEX()} {n} {TEX}برابر صفر گردد و این خلاف این است که در هر حرکت باقیمانده {TEX()} {k} {TEX}بر {TEX()} {n} {TEX}تغییری نمی‌کند. (منظور از {TEX()} {k} {TEX}به هنگ {TEX()} {n} {TEX}باقیمانده {TEX()} {k} {TEX}بر {TEX()} {n} {TEX}است .) |
| | --- | | --- |
| | !!مثال | | !!مثال |
| | هر یک از اضلاع مثلث متساوی‌الاضلاعی را به {TEX()} {k} {TEX}بخش برابر تقسیم کرده‌ایم. از هر نقطه تقسیم خط‌های راستی موازی ضلع‌ها کشیده‌ایم. به این ترتیب مثلث مفروض به {TEX()} {k^2} {TEX}مثلث کوچکتر تقسیم می‌شود. دنباله مثلث‌هایی را یک «زنجیر» می‌نامیم که در آن هیچ مثلثی دوبار تکرار نشده باشد و در ضمن هر مثلث با مثلث قبلی خود در یک ضلع مشترک باشد حداکثر تعداد مثلث‌های یک زنجیر چقدر است؟ | | هر یک از اضلاع مثلث متساوی‌الاضلاعی را به {TEX()} {k} {TEX}بخش برابر تقسیم کرده‌ایم. از هر نقطه تقسیم خط‌های راستی موازی ضلع‌ها کشیده‌ایم. به این ترتیب مثلث مفروض به {TEX()} {k^2} {TEX}مثلث کوچکتر تقسیم می‌شود. دنباله مثلث‌هایی را یک «زنجیر» می‌نامیم که در آن هیچ مثلثی دوبار تکرار نشده باشد و در ضمن هر مثلث با مثلث قبلی خود در یک ضلع مشترک باشد حداکثر تعداد مثلث‌های یک زنجیر چقدر است؟ |
| | __حل __ | | __حل __ |
| | مثلث‌ها را به گونه‌ای سیاه و سفید می‌کنیم که هیچ دو مثلث مجاوری هم رنگ نباشند. تعداد مثلث‌های سیاه{TEX()} {\frac{1}{2} \Big(k^2+k \Big)} {TEX} و تعداد مثلث‌های سفید{TEX()} {\frac{1}{2} \Big( k^2-k \Big)} {TEX} است و در هر زنجیره، رنگ مثلث‌ها باید یک در میان سیاه و سفید باشد بنابراین یک زنجیره حداکثر شامل{TEX()} {k^2-k+1} {TEX} مثلث است. (یک زنجیره با این طول به ازای هر {TEX()} {k} {TEX}بیابید.) | | مثلث‌ها را به گونه‌ای سیاه و سفید می‌کنیم که هیچ دو مثلث مجاوری هم رنگ نباشند. تعداد مثلث‌های سیاه{TEX()} {\frac{1}{2} \Big(k^2+k \Big)} {TEX} و تعداد مثلث‌های سفید{TEX()} {\frac{1}{2} \Big( k^2-k \Big)} {TEX} است و در هر زنجیره، رنگ مثلث‌ها باید یک در میان سیاه و سفید باشد بنابراین یک زنجیره حداکثر شامل{TEX()} {k^2-k+1} {TEX} مثلث است. (یک زنجیره با این طول به ازای هر {TEX()} {k} {TEX}بیابید.) |
| | --- | | --- |
| | ! پیوند های خارجی | | ! پیوند های خارجی |
| | [http://Olympiad.roshd.ir/computer/content/pdf/0143.pdf] | | [http://Olympiad.roshd.ir/computer/content/pdf/0143.pdf] |
| - | |
+ | ---
!همچنین ببینید
*((رنگ آمیزی و همخوانیI ))
*((اصل اکسترمال )) |
| | #@^ | | #@^ |
