تاریخچه ی:
اصل لانه کبوتری
تفاوت با نگارش: 2
| ||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()} {n+1} {TEX}قطعه الماس درون {TEX()} {n} {TEX}جعبه توزیع شوند آنگاه حداقل یک جعبه شامل بیش از یک الماس است. | | اگر{TEX()} {n+1} {TEX}قطعه الماس درون {TEX()} {n} {TEX}جعبه توزیع شوند آنگاه حداقل یک جعبه شامل بیش از یک الماس است. |
| البته این اصل به این صورت نیز بیان میگردد که: {TEX()} {n+1} {TEX} کبوتر که میخواهند در {TEX()} {n} {TEX}لانه بنشینند آنگاه حداقل یک لانه شامل بیش از یک کبوتر خواهد بود. | | البته این اصل به این صورت نیز بیان میگردد که: {TEX()} {n+1} {TEX} کبوتر که میخواهند در {TEX()} {n} {TEX}لانه بنشینند آنگاه حداقل یک لانه شامل بیش از یک کبوتر خواهد بود. |
- | این اصل ترکیبیاتی ساده اولین بار توسط دیریکله (1895 – 1805) در نظریة اعداد مورد استفاده قرار گرفت. این اصل بسیار ساده برخلاف انتظار، کابردهای بسیاری دارد و با استفاده از آن قضایای مهمی به اثبات میرسند. |
+ | این اصل ترکیبیاتی ساده اولین بار توسط دیریکله (1895 – 1805) در نظریه اعداد مورد استفاده قرار گرفت. این اصل بسیار ساده برخلاف انتظار، کابردهای بسیاری دارد و با استفاده از آن قضایای مهمی به اثبات میرسند. |
| فرانک رمزی یکی از کسانی بود که تعمیمهای وسیعی از این اصل ارائه کرد. امروزه مبحث «اعداد رمزی» یکی از بخشهای مهم در علم ترکیبیات است و بد نیست بدانید که پیشرفت در این شاخه به کندی صورت میگیرد و مسائل مبارزه طلب هر روز در آن بیشتر میشوند. | | فرانک رمزی یکی از کسانی بود که تعمیمهای وسیعی از این اصل ارائه کرد. امروزه مبحث «اعداد رمزی» یکی از بخشهای مهم در علم ترکیبیات است و بد نیست بدانید که پیشرفت در این شاخه به کندی صورت میگیرد و مسائل مبارزه طلب هر روز در آن بیشتر میشوند. |
| اغلب فهمیدن این موضوع که درکجا باید از اصل لانه کبوتری استفاده کرد کار سختی نیست، به عنوان مثال در مسائل وجودی مربوط به مجموعههای متناهی (و در بعضی موارد نامتناهی) این اصل میتواند کارساز باشد. کار مشکل در این بین پیداکردن الماسها و جعبهها (حجرهها) میباشد! | | اغلب فهمیدن این موضوع که درکجا باید از اصل لانه کبوتری استفاده کرد کار سختی نیست، به عنوان مثال در مسائل وجودی مربوط به مجموعههای متناهی (و در بعضی موارد نامتناهی) این اصل میتواند کارساز باشد. کار مشکل در این بین پیداکردن الماسها و جعبهها (حجرهها) میباشد! |
| برای آشنایی بد نیست به چند مسئله بدون حل در این موارد توجه کنید. | | برای آشنایی بد نیست به چند مسئله بدون حل در این موارد توجه کنید. |
| 1.در بین سه نفر حتماً دونفر با یک جنسیت وجود دارند. | | 1.در بین سه نفر حتماً دونفر با یک جنسیت وجود دارند. |
| 2.در بین 13 نفر حتماً دو نفر هستند که در یک ماه متولد شدهاند. | | 2.در بین 13 نفر حتماً دو نفر هستند که در یک ماه متولد شدهاند. |
| 3.هیچ شخصی بیشتر از 300000 تار مو در سر خود ندارند. پایتخت کشورمان ایران بیش از 300000 نفر جمعیت دارد، آیا میتوانید با اطمینان بگویید که دو نفر در این شهر هستند که تعداد موهای سرشان برابر است؟ | | 3.هیچ شخصی بیشتر از 300000 تار مو در سر خود ندارند. پایتخت کشورمان ایران بیش از 300000 نفر جمعیت دارد، آیا میتوانید با اطمینان بگویید که دو نفر در این شهر هستند که تعداد موهای سرشان برابر است؟ |
| #@ | | #@ |
| @#16: | | @#16: |
| 4.چند نفر لازم میدانید که مطمئن باشید که دو نفر آنها در یک روز هفته متولد شدهاند. | | 4.چند نفر لازم میدانید که مطمئن باشید که دو نفر آنها در یک روز هفته متولد شدهاند. |
| 5.اگر {TEX()} {qs+1} {TEX} الماس درون {TEX()} {s} {TEX}جعبه به دلخواه توزیع شوند. آنگاه حداقل یک جعبه شامل بیش از {TEX()} {q} {TEX}الماس است. | | 5.اگر {TEX()} {qs+1} {TEX} الماس درون {TEX()} {s} {TEX}جعبه به دلخواه توزیع شوند. آنگاه حداقل یک جعبه شامل بیش از {TEX()} {q} {TEX}الماس است. |
- | 6.خط {TEX()} {l} {TEX}در صفحة مثلث{TEX()} { ABC } {TEX} قرار دارد به طوری که از رئوس ((مثلث)) عبور نمیکند. نشان دهید خط l نمیتواند تمام اضلاع مثلث را قطع کند . |
+ | 6.خط {TEX()} {l} {TEX}در صفحه مثلث{TEX()} { ABC } {TEX} قرار دارد به طوری که از رئوس ((مثلث)) عبور نمیکند. نشان دهید خط l نمیتواند تمام اضلاع مثلث را قطع کند . |
| 7.یک صفحه از هیچ رأس از یک چهاروجهی منتظم نمیگذرد. این صفحه حداکثر چند ضلع از چهاروجهی را قطع میکند؟ | | 7.یک صفحه از هیچ رأس از یک چهاروجهی منتظم نمیگذرد. این صفحه حداکثر چند ضلع از چهاروجهی را قطع میکند؟ |
- | 8.یک صفحة هدف به شلیک مثلثی متساویالاضلاع به ضلع 2 است. الف.نشان دهید اگر 5 بار با تیر به آن بزنیم دو سوراخ روی آن است که فاصلة آنها کمتر یا مساوی 1 است. ب.اگر 17 بار با تیر به این هدف بزنیم کمترین فاصلة بین سوراخها حداکثر چقدر میتواند بزرگ باشد؟ 9.دورة تناوب نمایش اعشاری کسر {TEX()} {\frac{a}{b}} {TEX} که {TEX()} {a} {TEX}و {TEX()} {b} {TEX}نسبت به هم اولند. حداکثر برابر{TEX()} {(b-1)} {TEX}است. |
+ | 8.یک صفحه هدف به شلیک مثلثی متساویالاضلاع به ضلع 2 است. الف.نشان دهید اگر 5 بار با تیر به آن بزنیم دو سوراخ روی آن است که فاصله آنها کمتر یا مساوی 1 است. ب.اگر 17 بار با تیر به این هدف بزنیم کمترین فاصله بین سوراخها حداکثر چقدر میتواند بزرگ باشد؟ 9.دوره تناوب نمایش اعشاری کسر {TEX()} {\frac{a}{b}} {TEX} که {TEX()} {a} {TEX}و {TEX()} {b} {TEX}نسبت به هم اولند. حداکثر برابر{TEX()} {(b-1)} {TEX}است. |
| 10.یازده عدد اعشاری با نمایش نامتناهی داریم، نشان دهیدمیتوان دو تا از آنها مانند {TEX()} {a} {TEX}و {TEX()} {b} {TEX}پیدا کرد به طوری که نمایش {TEX()} {|a-b|} {TEX} متناهی باشد یا نامتناهی صفر داشته باشد. | | 10.یازده عدد اعشاری با نمایش نامتناهی داریم، نشان دهیدمیتوان دو تا از آنها مانند {TEX()} {a} {TEX}و {TEX()} {b} {TEX}پیدا کرد به طوری که نمایش {TEX()} {|a-b|} {TEX} متناهی باشد یا نامتناهی صفر داشته باشد. |
| 11.12 عدد دورقمی متمایز داریم، نشان دهید دو تا از آنها موجودند به طوری که تفاضلشان عددی به شکل {TEX()} {aa} {TEX}است. | | 11.12 عدد دورقمی متمایز داریم، نشان دهید دو تا از آنها موجودند به طوری که تفاضلشان عددی به شکل {TEX()} {aa} {TEX}است. |
| 12.اگر هیچکدام از اعداد{TEX()} { a + (n - 1) d , \cdots , a + d , a } {TEX} بر {TEX()} {n} {TEX}بخشپذیر نباشند آنگاه {TEX()} {d} {TEX}و {TEX()} {n} {TEX}نسبت به هم اولند (یعنی ب . م . م آنها یک است.) | | 12.اگر هیچکدام از اعداد{TEX()} { a + (n - 1) d , \cdots , a + d , a } {TEX} بر {TEX()} {n} {TEX}بخشپذیر نباشند آنگاه {TEX()} {d} {TEX}و {TEX()} {n} {TEX}نسبت به هم اولند (یعنی ب . م . م آنها یک است.) |
| مثالهای بعد پارهای کابردهای خاصتر از اصل لانه کبوتری را نشان میدهند. | | مثالهای بعد پارهای کابردهای خاصتر از اصل لانه کبوتری را نشان میدهند. |
| --- | | --- |
| !!مثال | | !!مثال |
| {TEX()} {n} {TEX}نفر در یک اتاق حاضر هستند. نشان دهید در بین آنها دو نفر وجود دارند که تعداد دوستانشان در این اتاق برابر است. | | {TEX()} {n} {TEX}نفر در یک اتاق حاضر هستند. نشان دهید در بین آنها دو نفر وجود دارند که تعداد دوستانشان در این اتاق برابر است. |
| __حل__ | | __حل__ |
- | {TEX()} {n} {TEX}جعبه با شمارههای{TEX()} {n-1,\cdots ,1,0} {TEX} در نظر میگیریم. اسم یک نفر را درون جعبة شمارة نه قرار میدهیم اگر او در بین افراد حاضر در اتاق نه دوست داشته باشد. بنابراین {TEX()} {n} {TEX}نفر و {TEX()} {n} {TEX}جعبه داریم، جعبههای شمارة 0 و {TEX()} {n-1} {TEX}همزمان نمیتوانند پرباشند زیرا اگر شخصی باشد که با {TEX()} {n-1} {TEX} نفر دوست باشد یعنی با همة افراد اتاق (غیر از خودش) دوست باشد دیگر شخصی با تعداد صفر دوست در اتاق وجود ندارد. پس {TEX()} {n} {TEX}نفر در {TEX()} {n-1} {TEX} جعبه قرار گرفتهاند، پس یک جعبه موجود است به طوری که شامل حداقل دو نفر است. پس دو نفر وجود دارند که تعداد دوستانشان با هم برابر است. |
+ | {TEX()} {n} {TEX}جعبه با شمارههای{TEX()} {n-1,\cdots ,1,0} {TEX} در نظر میگیریم. اسم یک نفر را درون جعبه شماره نه قرار میدهیم اگر او در بین افراد حاضر در اتاق نه دوست داشته باشد. بنابراین {TEX()} {n} {TEX}نفر و {TEX()} {n} {TEX}جعبه داریم، جعبههای شماره 0 و {TEX()} {n-1} {TEX}همزمان نمیتوانند پرباشند زیرا اگر شخصی باشد که با {TEX()} {n-1} {TEX} نفر دوست باشد یعنی با همه افراد اتاق (غیر از خودش) دوست باشد دیگر شخصی با تعداد صفر دوست در اتاق وجود ندارد. پس {TEX()} {n} {TEX}نفر در {TEX()} {n-1} {TEX} جعبه قرار گرفتهاند، پس یک جعبه موجود است به طوری که شامل حداقل دو نفر است. پس دو نفر وجود دارند که تعداد دوستانشان با هم برابر است. |
| --- | | --- |
| !!مثال | | !!مثال |
| یک تنیسباز 77 روز فرصت دارد تا خود را برای یک مسابقه مهم آماده کند او میخواهد در هر روز اقلاً یکبار به طور تمرینی با دوستش بازی کند ولی در طول این مدت دقیقاً 132 بازی تمرینی انجام دهد. نشان دهید با این فرضیات حتماً دنبالهای از روزهای متوالی وجود دارند که طی آنها دقیقاً 21 بازی انجام داده است. | | یک تنیسباز 77 روز فرصت دارد تا خود را برای یک مسابقه مهم آماده کند او میخواهد در هر روز اقلاً یکبار به طور تمرینی با دوستش بازی کند ولی در طول این مدت دقیقاً 132 بازی تمرینی انجام دهد. نشان دهید با این فرضیات حتماً دنبالهای از روزهای متوالی وجود دارند که طی آنها دقیقاً 21 بازی انجام داده است. |
| #@ | | #@ |
| @#16: | | @#16: |
| __حل__ | | __حل__ |
| فرض کنید {TEX()} {a_1} {TEX}تعداد بازیهایی باشد که تا روز {TEX()} {i} {TEX}ام انجام داده است. در این صورت | | فرض کنید {TEX()} {a_1} {TEX}تعداد بازیهایی باشد که تا روز {TEX()} {i} {TEX}ام انجام داده است. در این صورت |
| @@{TEX()} {1\le a_1 <\cdots <a_{77} \le 132} {TEX}@@ | | @@{TEX()} {1\le a_1 <\cdots <a_{77} \le 132} {TEX}@@ |
| در نتیجه | | در نتیجه |
| @@{TEX()} {22 \le a_1+21 <a_2+21 <\cdots <a_{77}+21 \le 153} {TEX}@@ | | @@{TEX()} {22 \le a_1+21 <a_2+21 <\cdots <a_{77}+21 \le 153} {TEX}@@ |
| بنابراین دو عدد از بین 154 عدد{TEX()} {a_n,\cdots ,a_1} {TEX} و{TEX()} {a_n+21,\cdots ,a_1+21} {TEX} برابرند. در نتیجه دو اندیس متمایز، {TEX()} {i} {TEX}و {TEX()} {j} {TEX}{TEX()} { (j > i) } {TEX}وجود دارند به طوری که{TEX()} { a_j = a_i + 21} {TEX} . پس این شطرنج باز در طول روزهای | | بنابراین دو عدد از بین 154 عدد{TEX()} {a_n,\cdots ,a_1} {TEX} و{TEX()} {a_n+21,\cdots ,a_1+21} {TEX} برابرند. در نتیجه دو اندیس متمایز، {TEX()} {i} {TEX}و {TEX()} {j} {TEX}{TEX()} { (j > i) } {TEX}وجود دارند به طوری که{TEX()} { a_j = a_i + 21} {TEX} . پس این شطرنج باز در طول روزهای |
| {TEX()} {j,\cdots ,i+2,i+1} {TEX} روی هم 21 بازی انجام داده است. | | {TEX()} {j,\cdots ,i+2,i+1} {TEX} روی هم 21 بازی انجام داده است. |
| --- | | --- |
| !!مثال | | !!مثال |
| فرض کنید{TEX()} {a_n,\cdots ,a_2,a_1} {TEX} ، {TEX()} {n} {TEX}عدد صحیح نه لزوماً نامساوی باشند. در این صورت زیرمجموعهای از این اعداد وجود دارد که مجموع اعضایش بر {TEX()} {n} {TEX}بخشپذیر است. | | فرض کنید{TEX()} {a_n,\cdots ,a_2,a_1} {TEX} ، {TEX()} {n} {TEX}عدد صحیح نه لزوماً نامساوی باشند. در این صورت زیرمجموعهای از این اعداد وجود دارد که مجموع اعضایش بر {TEX()} {n} {TEX}بخشپذیر است. |
| __حل__ | | __حل__ |
| {TEX()} {n} {TEX}عدد صحیح را در نظر بگیرید | | {TEX()} {n} {TEX}عدد صحیح را در نظر بگیرید |
| @@{TEX()} {s_1=a_1} {TEX}@@ | | @@{TEX()} {s_1=a_1} {TEX}@@ |
| @@{TEX()} {s_2=a_1+a_2} {TEX}@@ | | @@{TEX()} {s_2=a_1+a_2} {TEX}@@ |
| @@{TEX()} {\vdots} {TEX}@@ | | @@{TEX()} {\vdots} {TEX}@@ |
| @@{TEX()} {s_n=a_1+a_2+\cdots +a_n} {TEX}@@ | | @@{TEX()} {s_n=a_1+a_2+\cdots +a_n} {TEX}@@ |
- | اگر یکی از {TEX()} {s_i} {TEX}ها بر {TEX()} {n} {TEX}بخشپذیر باشد حکم مسأله ثابت شده، فرض کنید اینطور نباشد و باقیماندههای {TEX()} {n} {TEX}عدد صحیح فوق به هنگ {TEX()} {n} {TEX}متفاوت باشد. چون برای باقیماندههای آنها در تقسیم بر {TEX()} {n} {TEX}، {TEX()} {n-1} {TEX} امکان مختلف وجود دارد، دو تا از این اعداد مانند {TEX()} { (p < q) s_q , s_p } {TEX} وجود دارند که باقیماندة آنها به هنگ {TEX()} {n} {TEX}برابر است، بنابراین تفاضل زیر بر {TEX()} {n} {TEX}بخشپذیر است. |
+ | اگر یکی از {TEX()} {s_i} {TEX}ها بر {TEX()} {n} {TEX}بخشپذیر باشد حکم مسأله ثابت شده، فرض کنید اینطور نباشد و باقیماندههای {TEX()} {n} {TEX}عدد صحیح فوق به هنگ {TEX()} {n} {TEX}متفاوت باشد. چون برای باقیماندههای آنها در تقسیم بر {TEX()} {n} {TEX}، {TEX()} {n-1} {TEX} امکان مختلف وجود دارد، دو تا از این اعداد مانند {TEX()} { (p < q) s_q , s_p } {TEX} وجود دارند که باقیمانده آنها به هنگ {TEX()} {n} {TEX}برابر است، بنابراین تفاضل زیر بر {TEX()} {n} {TEX}بخشپذیر است. |
| @@{TEX()} { S_q – s_p = a_{p + 1} + \cdots + a_q } {TEX}@@ | | @@{TEX()} { S_q – s_p = a_{p + 1} + \cdots + a_q } {TEX}@@ |
| #@ | | #@ |
| @#16: | | @#16: |
| --- | | --- |
| !!مثال | | !!مثال |
| {TEX()} { (n + 1)} {TEX} عدد از{TEX()} { \{1 , 2 , \cdots , 2n \} } {TEX}انتخاب شده است، نشان دهید از میان اعداد انتخاب شده یکی بر دیگری بخشپذیر است. | | {TEX()} { (n + 1)} {TEX} عدد از{TEX()} { \{1 , 2 , \cdots , 2n \} } {TEX}انتخاب شده است، نشان دهید از میان اعداد انتخاب شده یکی بر دیگری بخشپذیر است. |
| __حل__ | | __حل__ |
| فرض کنید {TEX()} {n+1} {TEX}عدد مفروض{TEX()} {a_{n+1},\cdots ,a_2,a_1} {TEX} باشند، آنها را به شکل{TEX()} {a_i=2^{k_i} b_i} {TEX} مینویسیم که {TEX()} {b_i} {TEX}عددی ((فرد)) باشد. در این صورت{TEX()} {b_{n+1},\cdots ,b_2,b_1} {TEX} ، {TEX()} {n+1} {TEX}عدد فرد میباشند که بین 1 و {TEX()} {2n} {TEX}قرار دارند و چون در این بازه {TEX()} {n} {TEX}عدد فرد بیشتر نداریم پس دوتا از {TEX()} {b_i} {TEX}ها مانند {TEX()} {b_p} {TEX}و {TEX()} {b_q} {TEX}برابرند، بنابراین از دو عدد {TEX()} {a_p} {TEX}و {TEX()} {a_q} {TEX}یکی بر دیگری بخشپذیر است. | | فرض کنید {TEX()} {n+1} {TEX}عدد مفروض{TEX()} {a_{n+1},\cdots ,a_2,a_1} {TEX} باشند، آنها را به شکل{TEX()} {a_i=2^{k_i} b_i} {TEX} مینویسیم که {TEX()} {b_i} {TEX}عددی ((فرد)) باشد. در این صورت{TEX()} {b_{n+1},\cdots ,b_2,b_1} {TEX} ، {TEX()} {n+1} {TEX}عدد فرد میباشند که بین 1 و {TEX()} {2n} {TEX}قرار دارند و چون در این بازه {TEX()} {n} {TEX}عدد فرد بیشتر نداریم پس دوتا از {TEX()} {b_i} {TEX}ها مانند {TEX()} {b_p} {TEX}و {TEX()} {b_q} {TEX}برابرند، بنابراین از دو عدد {TEX()} {a_p} {TEX}و {TEX()} {a_q} {TEX}یکی بر دیگری بخشپذیر است. |
| --- | | --- |
| !!مثال | | !!مثال |
| فرض کنید{TEX()} {a,b\in N} {TEX} دو عدد نسبت به هم ((اول)) باشند. در این صورت{TEX()} {x,y} {TEX} ای متعلق به {TEX()} {N} {TEX}وجود دارند به طوری که{TEX()} {ax-by=1} {TEX} | | فرض کنید{TEX()} {a,b\in N} {TEX} دو عدد نسبت به هم ((اول)) باشند. در این صورت{TEX()} {x,y} {TEX} ای متعلق به {TEX()} {N} {TEX}وجود دارند به طوری که{TEX()} {ax-by=1} {TEX} |
| __حل__ | | __حل__ |
- | اعداد{TEX()} {(b - 1) a , \cdots , 2a , a } {TEX} را در نظر بگیرید، هیچکدام از این اعداد طبق فرض بر {TEX()} {b} {TEX}بخشپذیر نیستند، زیرا اگر یکی از این اعداد مانند{TEX()} {ia} {TEX}بر {TEX()} {b} {TEX}بخشپذیر باشد چون {TEX()} {a} {TEX}و {TEX()} {b} {TEX}بخشپذیر باشد چون {TEX()} {a} {TEX}و {TEX()} {b} {TEX}نسبت به هم اول میباشند، نتیجه میشود {TEX()} {i} {TEX}بر {TEX()} {b} {TEX}بخشپذیر است اما {TEX()} {i} {TEX}عددی بین 1 و {TEX()} { b - 1} {TEX} است و چنین چیزی غیرممکن است. بنابراین اگر باقیماندة این {TEX()} {b-1} {TEX}عدد را در تقسیم بر {TEX()} {b} {TEX}در نظر بگیریم، باقیماندة صفر ظاهر نمیشود. از طرفی هیچ کدام از این {TEX()} {b-1} {TEX}عدد باقیماندة یکسان ندارند زیرا اگر مثلاً {TEX()} {pa} {TEX}و{TEX()} { (p > q) qa } {TEX} باقیماندة یکسان داشته باشند نتیجه میشود{TEX()} {pq-qa} {TEX} بر {TEX()} {b} {TEX}بخشپذیر است یعنی {TEX()} {a(p-q)} {TEX} بر {TEX()} {b} {TEX}بخشپذیر است و چون {TEX()} {a} {TEX}و {TEX()} {b} {TEX}بخشپذیر است و چون {TEX()} {a} {TEX}و {TEX()} {b} {TEX}نسبت به هم اول میباشند نتیجه میشود {TEX()} {p-q} {TEX} بر {TEX()} {b} {TEX}بخشپذیر است ولی این عدد از {TEX()} {b} {TEX}کمتر است و چنین چیزی ممکن نیست. پس مجموعة باقیماندههای {TEX()} { (b – 1) a , \cdots , 2a , a } {TEX} در تقسیم بر {TEX()} {b} {TEX}با مجموعة {TEX()} {\{1 , 2 , \cdots , b-1 \}} {TEX} برابر است، در نتیجه عددی مانند {TEX()} {xa} {TEX}وجود دارد که در تقسیم بر {TEX()} {b} {TEX}باقیمانده برابر یک دارد یعنی {TEX()} {xa-1} {TEX} بر {TEX()} {b} {TEX}بخشپذیر استو این یعنی{TEX()} {xa-1=by} {TEX} یا{TEX()} {ax-by=1} {TEX} |
+ | اعداد{TEX()} {(b - 1) a , \cdots , 2a , a } {TEX} را در نظر بگیرید، هیچکدام از این اعداد طبق فرض بر {TEX()} {b} {TEX}بخشپذیر نیستند، زیرا اگر یکی از این اعداد مانند{TEX()} {ia} {TEX}بر {TEX()} {b} {TEX}بخشپذیر باشد چون {TEX()} {a} {TEX}و {TEX()} {b} {TEX}بخشپذیر باشد چون {TEX()} {a} {TEX}و {TEX()} {b} {TEX}نسبت به هم اول میباشند، نتیجه میشود {TEX()} {i} {TEX}بر {TEX()} {b} {TEX}بخشپذیر است اما {TEX()} {i} {TEX}عددی بین 1 و {TEX()} { b - 1} {TEX} است و چنین چیزی غیرممکن است. بنابراین اگر باقیمانده این {TEX()} {b-1} {TEX}عدد را در تقسیم بر {TEX()} {b} {TEX}در نظر بگیریم، باقیمانده صفر ظاهر نمیشود. از طرفی هیچ کدام از این {TEX()} {b-1} {TEX}عدد باقیمانده یکسان ندارند زیرا اگر مثلاً {TEX()} {pa} {TEX}و{TEX()} { (p > q) qa } {TEX} باقیمانده یکسان داشته باشند نتیجه میشود{TEX()} {pq-qa} {TEX} بر {TEX()} {b} {TEX}بخشپذیر است یعنی {TEX()} {a(p-q)} {TEX} بر {TEX()} {b} {TEX}بخشپذیر است و چون {TEX()} {a} {TEX}و {TEX()} {b} {TEX}بخشپذیر است و چون {TEX()} {a} {TEX}و {TEX()} {b} {TEX}نسبت به هم اول میباشند نتیجه میشود {TEX()} {p-q} {TEX} بر {TEX()} {b} {TEX}بخشپذیر است ولی این عدد از {TEX()} {b} {TEX}کمتر است و چنین چیزی ممکن نیست. پس مجموعه باقیماندههای {TEX()} { (b – 1) a , \cdots , 2a , a } {TEX} در تقسیم بر {TEX()} {b} {TEX}با مجموعه {TEX()} {\{1 , 2 , \cdots , b-1 \}} {TEX} برابر است، در نتیجه عددی مانند {TEX()} {xa} {TEX}وجود دارد که در تقسیم بر {TEX()} {b} {TEX}باقیمانده برابر یک دارد یعنی {TEX()} {xa-1} {TEX} بر {TEX()} {b} {TEX}بخشپذیر استو این یعنی{TEX()} {xa-1=by} {TEX} یا{TEX()} {ax-by=1} {TEX} |
| #@ | | #@ |
| @#16: | | @#16: |
- | تعمیم اصل لانة کبوتری به این صورت است که: اگر {TEX()} {m\cdot n+1} {TEX} کبوتر بخواهند در {TEX()} {n} {TEX}لانه بنشینند لااقل در یک لانه لااقل {TEX()} {m+1} {TEX}کبوتر خواهد نشست. |
+ | تعمیم اصل لانه کبوتری به این صورت است که: اگر {TEX()} {m\cdot n+1} {TEX} کبوتر بخواهند در {TEX()} {n} {TEX}لانه بنشینند لااقل در یک لانه لااقل {TEX()} {m+1} {TEX}کبوتر خواهد نشست. |
| --- | | --- |
| !!مثال. (اردوش و زکریس) | | !!مثال. (اردوش و زکریس) |
| اعداد 1 تا 101 را به ترتیبی دلخواه در یک سطر نوشتهایم. نشان دهید میتوان 11 تا از آنها را بدون برهم زدن ترتیبشان در نظر گرفت به طوری که ترتیب آنها یکنوا (صعودی یا نزولی) باشد. | | اعداد 1 تا 101 را به ترتیبی دلخواه در یک سطر نوشتهایم. نشان دهید میتوان 11 تا از آنها را بدون برهم زدن ترتیبشان در نظر گرفت به طوری که ترتیب آنها یکنوا (صعودی یا نزولی) باشد. |
| __حل__ | | __حل__ |
| حال کلیتری از این مثال به شرح زیر است که سعی میکنیم آن را اثبات کنیم. اگر{TEX()} {n=(p-1)(q-1)} {TEX} و دنبالهای {TEX()} {n} {TEX}تایی از اعداد صحیح داشته باشیم در این صورت میتوان زیر دنبالهای ((صعودی)) با طول {TEX()} {p} {TEX}یا زیر دنبالههای نزولی با طول {TEX()} {q} {TEX}از آن پیدا کرد. | | حال کلیتری از این مثال به شرح زیر است که سعی میکنیم آن را اثبات کنیم. اگر{TEX()} {n=(p-1)(q-1)} {TEX} و دنبالهای {TEX()} {n} {TEX}تایی از اعداد صحیح داشته باشیم در این صورت میتوان زیر دنبالهای ((صعودی)) با طول {TEX()} {p} {TEX}یا زیر دنبالههای نزولی با طول {TEX()} {q} {TEX}از آن پیدا کرد. |
- | دنبالة داده شده از {TEX()} {n} {TEX}عدد را در نظر بگیرید، فرض کنید{TEX()} {1\le m\le n, L_m} {TEX} ، نشاندهندة طول بزرگترین زیردنبالة صعودی باشد که به {TEX()} {m} {TEX}امین عضو دنباله ختم شده است و {TEX()} {R_m} {TEX}نشاندهندة طول بزرگترین زیر دنبالة ((نزولی)) با شروع از {TEX()} {m} {TEX}امین عضو دنباله باشد. |
+ | دنباله داده شده از {TEX()} {n} {TEX}عدد را در نظر بگیرید، فرض کنید{TEX()} {1\le m\le n, L_m} {TEX} ، نشاندهنده طول بزرگترین زیردنباله صعودی باشد که به {TEX()} {m} {TEX}امین عضو دنباله ختم شده است و {TEX()} {R_m} {TEX}نشاندهنده طول بزرگترین زیر دنباله ((نزولی)) با شروع از {TEX()} {m} {TEX}امین عضو دنباله باشد. |
| ادعا میکنیم اگر {TEX()} {k} {TEX}و {TEX()} {m} {TEX}دو عدد با این شرط که {TEX()} {1\le k \neq m \le n} {TEX} باشند آنگاه حتماً یکی از دو رابطه{TEX()} {R_m\neq R_k} {TEX} یا {TEX()} {L_m \neq L_k} {TEX} اتفاق میافتد. زیرا با {TEX()} { m > k } {TEX} یا {TEX()} { m < k } {TEX} فرض کنید{TEX()} { m > k } {TEX}. حال بر حسب این که عضو {TEX()} {m} {TEX}ام دنباله از عضو k ام دنباله بزرگتر باشد یا کوچکتر، داریم {TEX()} { L_k < L_m } {TEX} یا{TEX()} { R_k > R_m } {TEX}. در حالت{TEX()} { m < k } {TEX} نیز اتفاقات مشابهی رخ خواهد داد. بنابراین ادعای گفته شده ثابت میشود. | | ادعا میکنیم اگر {TEX()} {k} {TEX}و {TEX()} {m} {TEX}دو عدد با این شرط که {TEX()} {1\le k \neq m \le n} {TEX} باشند آنگاه حتماً یکی از دو رابطه{TEX()} {R_m\neq R_k} {TEX} یا {TEX()} {L_m \neq L_k} {TEX} اتفاق میافتد. زیرا با {TEX()} { m > k } {TEX} یا {TEX()} { m < k } {TEX} فرض کنید{TEX()} { m > k } {TEX}. حال بر حسب این که عضو {TEX()} {m} {TEX}ام دنباله از عضو k ام دنباله بزرگتر باشد یا کوچکتر، داریم {TEX()} { L_k < L_m } {TEX} یا{TEX()} { R_k > R_m } {TEX}. در حالت{TEX()} { m < k } {TEX} نیز اتفاقات مشابهی رخ خواهد داد. بنابراین ادعای گفته شده ثابت میشود. |
- | بنابراین تمام زوجهای {TEX()} {(m=1,2\cdots ,n)(L_m,R_m)} {TEX}متفاوتاند. حال فرض کنید که هیچکدام از دو مورد گفته شده در حکم مسأله رخ ندهد. در این صورت{TEX()} { L_m } {TEX} میتواند تنها مقادیر{TEX()} {p-1,\cdots ,2,1} {TEX} و{TEX()} { R_m } {TEX} میتواند تنها مقادیر{TEX()} {q-1,\cdots ,2,1} {TEX} را اختیار کند. بنابراین به تعداد{TEX()} {(p-1)(q-1)} {TEX}جعبة مختلف داریم که{TEX()} {n=(p-1)(q-1)} {TEX}تا زوج در آنها قرار دارند ولی این تناقض است زیرا به این معنا است که دو تا از زوجهای{TEX()} {(L_m,R_m)} {TEX} با هم برابرند (طبق اصل لانه کبوتری). |
+ | بنابراین تمام زوجهای {TEX()} {(m=1,2\cdots ,n)(L_m,R_m)} {TEX}متفاوتاند. حال فرض کنید که هیچکدام از دو مورد گفته شده در حکم مسأله رخ ندهد. در این صورت{TEX()} { L_m } {TEX} میتواند تنها مقادیر{TEX()} {p-1,\cdots ,2,1} {TEX} و{TEX()} { R_m } {TEX} میتواند تنها مقادیر{TEX()} {q-1,\cdots ,2,1} {TEX} را اختیار کند. بنابراین به تعداد{TEX()} {(p-1)(q-1)} {TEX}جعبه مختلف داریم که{TEX()} {n=(p-1)(q-1)} {TEX}تا زوج در آنها قرار دارند ولی این تناقض است زیرا به این معنا است که دو تا از زوجهای{TEX()} {(L_m,R_m)} {TEX} با هم برابرند (طبق اصل لانه کبوتری). |
| --- | | --- |
| #@ | | #@ |
| @#16: | | @#16: |
| !!مثال | | !!مثال |
- | 5 نقطة شبکهای در صفحه انتخاب شدهاند. نشان دهید میتوان دو تا از این نقاط را در نظر گرفت به طوری که روی پارهخط واصل میان آن دو، نقطة شبکهای دیگری موجود باشد. |
+ | 5 نقطه شبکهای در صفحه انتخاب شدهاند. نشان دهید میتوان دو تا از این نقاط را در نظر گرفت به طوری که روی پارهخط واصل میان آن دو، نقطه شبکهای دیگری موجود باشد. |
| __توضیح.__ نقاط شبکهای در صفحه نقاطی هستند که مختصات آنها صحیح میباشد. | | __توضیح.__ نقاط شبکهای در صفحه نقاطی هستند که مختصات آنها صحیح میباشد. |
| __حل__ | | __حل__ |
- | در اینجا الگوی مختصات نقاط صفحه را از نظر زوجیت در نظر میگیریم، چهار حالت بیشتر نداریم که عبارتند از: (زوج و زوج) ، (فرد و زوج) ، (زوج و فرد) و (فرد و فرد) . حال چون 5 نقطه داریم طبق اصل لانة کبوتری حداقل دو تا از آنها مانند{TEX()} { A = (a , b) } {TEX} و{TEX()} { B = (c , d) } {TEX} زوجیت مؤلفههایشان یکسان است. نقطة وسط AB به نام L را در نظر بگیرید، داریم |
+ | در اینجا الگوی مختصات نقاط صفحه را از نظر زوجیت در نظر میگیریم، چهار حالت بیشتر نداریم که عبارتند از: (زوج و زوج) ، (فرد و زوج) ، (زوج و فرد) و (فرد و فرد) . حال چون 5 نقطه داریم طبق اصل لانه کبوتری حداقل دو تا از آنها مانند{TEX()} { A = (a , b) } {TEX} و{TEX()} { B = (c , d) } {TEX} زوجیت مؤلفههایشان یکسان است. نقطه وسط AB به نام L را در نظر بگیرید، داریم |
| @@{TEX()} {L=\Biggg( \frac{a+c}{2},\frac{b+d}{2} \Biggg)} {TEX}@@ | | @@{TEX()} {L=\Biggg( \frac{a+c}{2},\frac{b+d}{2} \Biggg)} {TEX}@@ |
| چون زوجیت {TEX()} {c,a} {TEX} و همچنین {TEX()} {d,b} {TEX} یکسان است {TEX()} {L} {TEX}نیز نقطهای شبکهای خواهد بود. | | چون زوجیت {TEX()} {c,a} {TEX} و همچنین {TEX()} {d,b} {TEX} یکسان است {TEX()} {L} {TEX}نیز نقطهای شبکهای خواهد بود. |
| --- | | --- |
| !!مثال | | !!مثال |
- | در دنبالة 1 , 1 , 2 , 3 , 5 , 8 , 3 , … با شروع از مرتبة سوم هر جمله رقم یکسان مجموع دو جملة قبلیاش است. نشان دهید دنباله متناوب است و ماکزیمم طول ممکن برای دورة تناوب را بیابید. |
+ | در دنباله 1 , 1 , 2 , 3 , 5 , 8 , 3 , … با شروع از مرتبه سوم هر جمله رقم یکسان مجموع دو جمله قبلیاش است. نشان دهید دنباله متناوب است و ماکزیمم طول ممکن برای دوره تناوب را بیابید. |
| __حل__ | | __حل__ |
- | هر دو جملة متوالی از دنباله را که در نظر بگیرید تمامی جملات قبل و بعد را به طور یکتا مشخص میکنند، بنابراین برای این که نشان دهیم دنباله متناوب است کافی است نشان دهیم یک زوج متوالی از جملات مانند {TEX()} {(a,b)} {TEX}تکرار میشود و در ضمن اولین زوج تکرار شونده (1 و 1) است. 101 جملة اول این دنباله را در نظر بگیرید آنها 100 زوج (2 , 3) , (1 , 2) , (1 , 1) و … را درست میکنند، چون زوج (0 , 0) تکرار نمیشوند (زیرا این مطلب باعث میشود که همة جملات دنباله بر 10 بخشپذیر باشند) تعداد حالتهای ممکن برای یک زوج متوالی مانند{TEX()} { (a , b) } {TEX} برابر{TEX()} {10^2-1} {TEX}یعنی 99 است و در نتیجه طبق اصل لانة کبوتری در بین 100 زوج اول حداقل یک زوج تکرار میشود و در نتیجه دورة تناوب حداکثر 99 است. |
+ | هر دو جمله متوالی از دنباله را که در نظر بگیرید تمامی جملات قبل و بعد را به طور یکتا مشخص میکنند، بنابراین برای این که نشان دهیم دنباله متناوب است کافی است نشان دهیم یک زوج متوالی از جملات مانند {TEX()} {(a,b)} {TEX}تکرار میشود و در ضمن اولین زوج تکرار شونده (1 و 1) است. 101 جمله اول این دنباله را در نظر بگیرید آنها 100 زوج (2 , 3) , (1 , 2) , (1 , 1) و … را درست میکنند، چون زوج (0 , 0) تکرار نمیشوند (زیرا این مطلب باعث میشود که همه جملات دنباله بر 10 بخشپذیر باشند) تعداد حالتهای ممکن برای یک زوج متوالی مانند{TEX()} { (a , b) } {TEX} برابر{TEX()} {10^2-1} {TEX}یعنی 99 است و در نتیجه طبق اصل لانه کبوتری در بین 100 زوج اول حداقل یک زوج تکرار میشود و در نتیجه دوره تناوب حداکثر 99 است. |
| --- | | --- |
| !!مثال | | !!مثال |
- | دنبالة فیبوناتچی به شکل زیر تعریف میشود |
+ | دنباله فیبوناتچی به شکل زیر تعریف میشود |
| {TEX()} { a_1 = a_2 = 1\qquad a_{n + 1} = a_n + a_{n - 1} , n > 1} {TEX} | | {TEX()} { a_1 = a_2 = 1\qquad a_{n + 1} = a_n + a_{n - 1} , n > 1} {TEX} |
- | نشان دهید به ازای هر {TEX()} {n} {TEX}عددی از ((دنبالة فیبوناتچی)) یافت میشود که به {TEX()} {n} {TEX}تا صفر ختم میشود. |
+ | نشان دهید به ازای هر {TEX()} {n} {TEX}عددی از ((دنباله فیبوناتچی)) یافت میشود که به {TEX()} {n} {TEX}تا صفر ختم میشود. |
| __حل__ | | __حل__ |
- | جملة {TEX()} {a_p} {TEX}به {TEX()} {n} {TEX}صفر ختم میشود اگر و تنها اگر {TEX()} {a_p} {TEX}بر {TEX()} {10^n} {TEX}بخشپذیر باشد یعنی {TEX()} {a_p=0 \quad (mod \ 10^n )} {TEX} بنابراین باید دنبالة فیبوناتچی را به هنگ {TEX()} {10^n} {TEX}در نظر بگیریم و نشان دهیم که در بین باقیماندهها ظاهر میشود. {TEX()} {10^{2n}+1} {TEX} جملة اول دنبالة فیبوناتچی یعنی{TEX()} {\cdots ,a_3,a_2,a_1} {TEX} را در نظر بگیرید. با استفاده از آنها میتوان {TEX()} {10^{3n}} {TEX}جفت {TEX()} {\cdots ,(a_2,a_3),(a_1,a_2)} {TEX}را درست کرد که اگر قرار باشد هیچ {TEX()} {a_i} {TEX}ای بر {TEX()} {10^n} {TEX}بخشپذیر نباشد زوج ( 0 , 0) در میان این جفتها به هنگ {TEX()} {10^n} {TEX}ظاهر نمیشود. اما صرفنظر از زوج ( 0 , 0) از لحاظ باقیمانده به هنگ {TEX()} {10^n} {TEX}، {TEX()} {10^{2n}-1} {TEX}امکان برای زوج ها وجود دارد. بنابراین یک جفت تکرار میشود. پس طول ((دوره تناوب)) دنباله به ((هنگ)) {TEX()} {10^n} {TEX}حداکثر{TEX()} {10^{2n}-1} {TEX} است. همانند مثال 8، اولین جفت کمه تکرار میشود (1 ، 1) است ، به شکل زیر |
+ | جمله {TEX()} {a_p} {TEX}به {TEX()} {n} {TEX}صفر ختم میشود اگر و تنها اگر {TEX()} {a_p} {TEX}بر {TEX()} {10^n} {TEX}بخشپذیر باشد یعنی {TEX()} {a_p=0 \quad (mod \ 10^n )} {TEX} بنابراین باید دنباله فیبوناتچی را به هنگ {TEX()} {10^n} {TEX}در نظر بگیریم و نشان دهیم که در بین باقیماندهها ظاهر میشود. {TEX()} {10^{2n}+1} {TEX} جمله اول دنباله فیبوناتچی یعنی{TEX()} {\cdots ,a_3,a_2,a_1} {TEX} را در نظر بگیرید. با استفاده از آنها میتوان {TEX()} {10^{3n}} {TEX}جفت {TEX()} {\cdots ,(a_2,a_3),(a_1,a_2)} {TEX}را درست کرد که اگر قرار باشد هیچ {TEX()} {a_i} {TEX}ای بر {TEX()} {10^n} {TEX}بخشپذیر نباشد زوج ( 0 , 0) در میان این جفتها به هنگ {TEX()} {10^n} {TEX}ظاهر نمیشود. اما صرفنظر از زوج ( 0 , 0) از لحاظ باقیمانده به هنگ {TEX()} {10^n} {TEX}، {TEX()} {10^{2n}-1} {TEX}امکان برای زوج ها وجود دارد. بنابراین یک جفت تکرار میشود. پس طول ((دوره تناوب)) دنباله به ((هنگ)) {TEX()} {10^n} {TEX}حداکثر{TEX()} {10^{2n}-1} {TEX} است. همانند مثال 8، اولین جفت کمه تکرار میشود (1 ، 1) است ، به شکل زیر |
| @@{picture=img/daneshnameh_up/5/50/com0044a.jpg}@@ | | @@{picture=img/daneshnameh_up/5/50/com0044a.jpg}@@ |
| #@ | | #@ |
| @#16: | | @#16: |
- | که {TEX()} {i} {TEX}طول دورة تناوب است. در نتیجه داریم {TEX()} {1\equive 1+a_p \quad (mod \ 10^n)} {TEX} یا{TEX()} {a_p\equive 0 \quad (mod \ 10^n)} {TEX} یعنی {TEX()} {ap} {TEX}بر {TEX()} {10^n} {TEX}بخشپذیر است. |
+ | که {TEX()} {i} {TEX}طول دوره تناوب است. در نتیجه داریم {TEX()} {1\equive 1+a_p \quad (mod \ 10^n)} {TEX} یا{TEX()} {a_p\equive 0 \quad (mod \ 10^n)} {TEX} یعنی {TEX()} {ap} {TEX}بر {TEX()} {10^n} {TEX}بخشپذیر است. |
| --- | | --- |
| !!مثال | | !!مثال |
| فرض کنید {TEX()} {a} {TEX}عددی طبیعی باشد که نسبت به 2 و 5 اول است. نشان دهید به ازای هر {TEX()} {n} {TEX}میتوان توانی از {TEX()} {a} {TEX}پیدا کرد که به{picture=img/daneshnameh_up/d/d4/com0044b.jpg }ختم میشود. | | فرض کنید {TEX()} {a} {TEX}عددی طبیعی باشد که نسبت به 2 و 5 اول است. نشان دهید به ازای هر {TEX()} {n} {TEX}میتوان توانی از {TEX()} {a} {TEX}پیدا کرد که به{picture=img/daneshnameh_up/d/d4/com0044b.jpg }ختم میشود. |
| __حل__ | | __حل__ |
- | {TEX()} {10^n} {TEX}عدد{TEX()} {a^{10^n},\cdots,a^3,a^2,a} {TEX} را در نظر بگیرید. اگر باقیماندة آنها را به هنگ {TEX()} {10^n} {TEX}بررسی کنیم درمییابیم که باقیماندة هیچ کدام برابر صفر نیست زیرا {TEX()} {a} {TEX}و 10 نسبت به هم اول هستند. بنابراین باقیماندههای این {TEX()} {10^n} {TEX}عدد از مجموعه {TEX()} { {1 , 2 ,\cdots , (10^n - 1)}} {TEX} میباشند. طبق اصل لانة کبوتری دو تا از آنها مانند {TEX()} {a_1} {TEX}و{TEX()} {(i < k) a_k } {TEX} به هنگ {TEX()} {10^n} {TEX}باقیماندة یکسانی دارند در نتیجه تفاضل آنها بر {TEX()} {10^n} {TEX}بخشپذیر است یعنی |
+ | {TEX()} {10^n} {TEX}عدد{TEX()} {a^{10^n},\cdots,a^3,a^2,a} {TEX} را در نظر بگیرید. اگر باقیمانده آنها را به هنگ {TEX()} {10^n} {TEX}بررسی کنیم درمییابیم که باقیمانده هیچ کدام برابر صفر نیست زیرا {TEX()} {a} {TEX}و 10 نسبت به هم اول هستند. بنابراین باقیماندههای این {TEX()} {10^n} {TEX}عدد از مجموعه {TEX()} { {1 , 2 ,\cdots , (10^n - 1)}} {TEX} میباشند. طبق اصل لانه کبوتری دو تا از آنها مانند {TEX()} {a_1} {TEX}و{TEX()} {(i < k) a_k } {TEX} به هنگ {TEX()} {10^n} {TEX}باقیمانده یکسانی دارند در نتیجه تفاضل آنها بر {TEX()} {10^n} {TEX}بخشپذیر است یعنی |
| {TEX()} {10^n|a^i(a^{k-i}-1)} {TEX} و{TEX()} {10^n|a^k-a^t} {TEX} | | {TEX()} {10^n|a^i(a^{k-i}-1)} {TEX} و{TEX()} {10^n|a^k-a^t} {TEX} |
| اما {TEX()} {(10^n,a^i)=1} {TEX} پس {TEX()} {10^n|a^{k-i}-1} {TEX} در نتیجه {TEX()} {q\in N} {TEX} وجود دارد که{TEX()} {a^{k-i}-1=q\times 10^n} {TEX} حال داریم {TEX()} {a^{k-i}=q\times 10^n+1} {TEX}، اگر کمی دقت کنید خواهید دید که این تساوی بدین معناست که{TEX()} {a^{k-i}} {TEX} به{picture=img/daneshnameh_up/e/e2/com0044c.jpg}ختم میشود. | | اما {TEX()} {(10^n,a^i)=1} {TEX} پس {TEX()} {10^n|a^{k-i}-1} {TEX} در نتیجه {TEX()} {q\in N} {TEX} وجود دارد که{TEX()} {a^{k-i}-1=q\times 10^n} {TEX} حال داریم {TEX()} {a^{k-i}=q\times 10^n+1} {TEX}، اگر کمی دقت کنید خواهید دید که این تساوی بدین معناست که{TEX()} {a^{k-i}} {TEX} به{picture=img/daneshnameh_up/e/e2/com0044c.jpg}ختم میشود. |
| --- | | --- |
| !!مثال | | !!مثال |
- | درون یک اتاق به مساحت 5 متر مربع، 9 قالیچه به مساحت یک مترمربع و با شکل دلخواه پهن کردهایم. (ممکن است قالیچهها مستطیل شکل نباشند) نشان دهید دو قالیچه وجود دارند که به اندازة حداقل {TEX()} {\frac{1}{9}} {TEX} مترمربع اشتراک دارند. |
+ | درون یک اتاق به مساحت 5 متر مربع، 9 قالیچه به مساحت یک مترمربع و با شکل دلخواه پهن کردهایم. (ممکن است قالیچهها مستطیل شکل نباشند) نشان دهید دو قالیچه وجود دارند که به اندازه حداقل {TEX()} {\frac{1}{9}} {TEX} مترمربع اشتراک دارند. |
| __حل__ | | __حل__ |
- | فرض کنید حکم درست نباشد یعنی ((اشتراک)) هر دو قالیچه کمتر از {TEX()} {\frac{1}{9}} {TEX} مترمربع مساحت داشته باشد. قالیچهها را یکییکی مطابق الگوی اولیه در اتاق میاندازیم. قالیچة اول مساحتی به اندازة یک متر مربع یا {TEX()} {\frac{9}{9}} {TEX} را میپوشاند، قالیچة دوم مساحتی به اندازة بزرگتر از {TEX()} {\frac{8}{9}} {TEX} را به مساحت قبلی اضافه میکند، … به همین ترتیب قالیچة آخر مساحتی به اندازة بزرگتر از {TEX()} {\frac{1}{9}} {TEX} را اضافه میکند، پس مجموع مساحتی که کل قالیچهها میپوشانند بزرگتر از {TEX()} {\frac{1}{9}+\frac{2}{9}+\cdots +\frac{9}{9}=5} {TEX} است، این بدان معنی است که مساحت اتاق از 5 بیشتر است که تناقض است. |
+ | فرض کنید حکم درست نباشد یعنی ((اشتراک)) هر دو قالیچه کمتر از {TEX()} {\frac{1}{9}} {TEX} مترمربع مساحت داشته باشد. قالیچهها را یکییکی مطابق الگوی اولیه در اتاق میاندازیم. قالیچه اول مساحتی به اندازه یک متر مربع یا {TEX()} {\frac{9}{9}} {TEX} را میپوشاند، قالیچه دوم مساحتی به اندازه بزرگتر از {TEX()} {\frac{8}{9}} {TEX} را به مساحت قبلی اضافه میکند، … به همین ترتیب قالیچه آخر مساحتی به اندازه بزرگتر از {TEX()} {\frac{1}{9}} {TEX} را اضافه میکند، پس مجموع مساحتی که کل قالیچهها میپوشانند بزرگتر از {TEX()} {\frac{1}{9}+\frac{2}{9}+\cdots +\frac{9}{9}=5} {TEX} است، این بدان معنی است که مساحت اتاق از 5 بیشتر است که تناقض است. |
| --- | | --- |
| ! پیوند های خارجی | | ! پیوند های خارجی |
| [http://Olympiad.roshd.ir/computer/content/pdf/0039.pdf] | | [http://Olympiad.roshd.ir/computer/content/pdf/0039.pdf] |
| --- | | --- |
| !همچنین ببینید | | !همچنین ببینید |
| *((اصل شمول و طرد )) | | *((اصل شمول و طرد )) |
| *((تعمیم )) | | *((تعمیم )) |
| #@^ | | #@^ |