ماراتن ترکیبیات

[erfankh]

استقرا می زنیم
پایه استقرا که به ازای 2 برقرار است فرض می کنیم که به ازای n بین 2 و k حکم مساله برقرار است.می خواهیم حکم را برای k+1 اثبات کنیم.
اگر k+1 زوج باشد با در نظر نگرفتن خانه k/2+1/2+1 تا k+1 می دانیم که طبق فرض استقرا یکی از مهره ها را به k/2+1/2 برسانیم در نتیجه چون خانه های جلوی آن خالی است پس در حرکت بعد آن را به k+1 می بریم
اگر k+1 فرد باشد مثل قسمت قبل یکی از مهره ها را به k/2 می رسانیم سپس مهره ای که در چند خانه قبل از آن است را به توجه به قانون سوال حرکت می دهیم تا از خانه k/2 بگذرد (چون مهره مذبور در خانه ای با شماره کمتر از k/2 قرار دارد پس هنگامی که از مهره مو جود در خانه k/2 جلو می زند در خانه k+1 قرار نمیگیرد)سپس مهره موجود در خانه K/2 را حرکت می دهیم و چون در فاصله بین خانه های k/2 تا k+1 مهره دیگری وجود دارد طبق قانون حرکت مهره ها در سوال مهره به خانه k+1 می رود

 

[combinatorics]

پاسخ : ماراتن ترکیبیات

چرا ماراتن را رها کرده اید. از المپیادی ها خواهش می کنم دوباره به آن رونق بدهید. به نظر من مفید ترین قسمت سایت همین ماراتن هاست. حالا یکی به من بگوید الان سوالی باز هست یا نه؟ اگر هست کدام سوال؟

 

[combinatorics]

پاسخ : ماراتن ترکیبیات

انگار خبری از بچه ها در ماراتن ترکیبیات مقدماتی نیست. پس خودم یک سوال ترکیبیات مقدماتی(آنالیز ترکیبی) می گذارم.
سوال:
تعداد دنباله های n حرفی از حروف a,b,c,d را بیابید به طوری که تعداد a ها با b ها برابر باشد.

 

[fereidoon]

پاسخ : ماراتن ترکیبیات

جواب ميشه:

.براي اثباتش هم كافيه يه تناظر بزنيد.

 

[combinatorics]

پاسخ : ماراتن ترکیبیات

جواب ميشه:

.براي اثباتش هم كافيه يه تناظر بزنيد.

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

 

[fereidoon]

پاسخ : ماراتن ترکیبیات

سوال بعد
2n+1 عدد گنگ داريم,ثابت كنيد دست كم n+1 عدد وجود دارد كه دوبه دو جمعشان گنگ است.

 

[mahanmath]

پاسخ : ماراتن ترکیبیات

سوال بعد
2n+1 عدد گنگ داريم,ثابت كنيد دست كم n+1 عدد وجود دارد كه دوبه دو جمعشان گنگ است.

میشه ثابت کرد که n+1 از اونها هستن که هیچ ترکیب خطی از اونها با ضرایب گویا نامنفی صفر نمی شه
(جز حالت بدیهیه که همه ضرایب صفر هستند)

فرض کنید این حکم درست نباشه حالا n تا از اونهارو ثابت بگیرید و هر دفعه یکی از عددهای بیرونو با این n تا بگیرید و یه ترکیب خطی خوب (یعنی متناسب با فرض خلف !) از اون هارو بنویسید ، در آخر هم برای n+1 عدد بیرون این کارو بکنید و نتیجه بگیرید که برای هر n عدد می شه یه ترکیب خطی خوب پیدا کرد .حالا همین روندو رو ادامه بدین ....

 

[fereidoon]

پاسخ : ماراتن ترکیبیات

خيلي ممنون.راه حل من واسه اين سوال كاملا تركيبياتيه(گرافه)اگه خواستيد مي تونم راهم رو بنويسم,به نظر خودم خيلي قشنگ بود.

 

[fereidoon]

پاسخ : ماراتن ترکیبیات

من داشتم پست هاي قبلي رو ميديدم,استاد shoki تو صفحه 19 هم اينجا سوال من رو مطرح كرده بود.

 

[combinatorics]

پاسخ : ماراتن ترکیبیات

میشه ثابت کرد که n+1 از اونها هستن که هیچ ترکیب خطی از اونها با ضرایب گویا نامنفی صفر نمی شه
(جز حالت بدیهیه که همه ضرایب صفر هستند)

فرض کنید این حکم درست نباشه حالا n تا از اونهارو ثابت بگیرید و هر دفعه یکی از عددهای بیرونو با این n تا بگیرید و یه ترکیب خطی خوب (یعنی متناسب با فرض خلف !) از اون هارو بنویسید ، در آخر هم برای n+1 عدد بیرون این کارو بکنید و نتیجه بگیرید که برای هر n عدد می شه یه ترکیب خطی خوب پیدا کرد .حالا همین روندو رو ادامه بدین ....

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

 

[fereidoon]

پاسخ : ماراتن ترکیبیات

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

پست بالا رو بخون

 

[fereidoon]

پاسخ : ماراتن ترکیبیات

من راه اينو ميگم:يه گراف 2n+1 راسي ميكشيم,حال يال ها رو اين طوري رنگ مي كنيم؛يال بين دو راس i و j رو قرمز مي كنيم اگر i+j گنگ باشد.حال بر حسب رنگ اميزي يه گراف دو بخشي داريم و با در نظر گرفتن تعداد دورها در اين گراف مسئله براحتي حل ميشه.

 

[combinatorics]

پاسخ : ماراتن ترکیبیات

من راه اينو ميگم:يه گراف 2n+1 راسي ميكشيم,حال يال ها رو اين طوري رنگ مي كنيم؛يال بين دو راس i و j رو قرمز مي كنيم اگر i+j گنگ باشد.حال بر حسب رنگ اميزي يه گراف دو بخشي داريم و با در نظر گرفتن تعداد دورها در اين گراف مسئله براحتي حل ميشه.

لطفا سوال بعدی رو هم بگذار.

 

[rezashiri]

پاسخ : ماراتن ترکیبیات

با اجازه بزرگترا اینم یه سوال (شاید ساده!) :

n>=3 نقطه در صفحه داده شده که هیچ 3 تایی هم خط نیستند.نقطه ای را خوب می نامیم که مجموع فواصلش از بقیه ی نقاط کمینه باشد. ثابت کنید دقیقا یک نقطه خوب وجود دارد.

 

[bgo]

پاسخ : ماراتن ترکیبیات

فک کنم مرحله دو بوده..................

توجه کنید حتمن حداقل یه نقطه خوب داریم...........
حالا اگه دو تا نقطه خوب داشته باشیم وسط این دو تا خوب تره!!!!!!!!!!!!!!

 

[fereidoon]

پاسخ : ماراتن ترکیبیات

سوال بعدي-واقعا ارزش فك كردن داره-
جايگشتي دوري از اعداد

تا

داده شده است. هر بار مي توانيم جاي دو عدد مجاور را عوض كنيم به شرط ان كه تفاضل ان دو به پيمانه

با

همنهشت نباشد.دو جايگشت دوري را هم ارز مي ناميم هرگاه از يكي با انجام چند تا از اعمال فوق بتوانيم به ديگري برسيم.حداكثر تعداد هاي جايگشت هاي دوري دو به دو غير هم ارز را براي هر

به دست اوريد!

 

[mahanmath]

پاسخ : ماراتن ترکیبیات

سوال بعدي-واقعا ارزش فك كردن داره-
جايگشتي دوري از اعداد

تا

داده شده است. هر بار مي توانيم جاي دو عدد مجاور را عوض كنيم به شرط ان كه تفاضل ان دو به پيمانه

با

همنهشت نباشد.دو جايگشت دوري را هم ارز مي ناميم هرگاه از يكي با انجام چند تا از اعمال فوق بتوانيم به ديگري برسيم.حداكثر تعداد هاي جايگشت هاي دوري دو به دو غير هم ارز را براي هر

به دست اوريد!

چه عجب این توپولوژی به درد خورد !

این کار درجه نگاشت رو ثابت نگاه میداره پس می شه حداقل 1-n تا ناهم ارز پیدا کرد ، برای این که ثابت کنیم این کران بهترین کران ممکن هست کافی نشون بدیم از یه جایگشت دوری با درجه نگاشت m میشه به جایگشت زیر رسید :

m, m − 1, . . , 2, 1, m+1, m+2, . . . , n

(توجه کنید درجه نگاشت رو ساعت گرد تعریف کردم )

که اینم سادس ...

(چون اولین تجربه توپولوژیکی منه احتمال جوب فراوان است!)

 

[mahanmath]

پاسخ : ماراتن ترکیبیات

درجه نگاشت هم باید تعریف میکردم راستی !!! :

فرض کنید در جهت ساعت گرد دارید موقعیت عدد هارو دنبال میکنید ، یعنی بالا سر ۱ وایستادید بعد میرین بالا سر ۲ (در جهت ساعت گرد میچرخین تا ۲ رو پیدا کنید .) بعد ۳ ، بعد ۴ ، .... ، تا میرسید به n و بالاخره دوباره میرین سراغ ۱

حالا ببینید در آخر چند بار دور دایره گشتین ، مثلا اگه عددا بصورت زیر باشن 1-n بار میگردید :

1 2 3 4 .... n

(اگه درجه نگاشت رو پاد ساعت گرد تعریف می*کردم ۱ بار میگشتین )

به این تعداد میگن درجه نگاشت .

 

[fereidoon]

پاسخ : ماراتن ترکیبیات

من كه هيچي متوجه نشدم ولي جواب مسئله n-1 است،احتمالا يكي از نگاشت هارو بايد حذف كنيد!
البته بگم حل شما خيلي نزديك به حل اصلي سواله...

 

[goodarz]

پاسخ : ماراتن ترکیبیات

درجه نگاشت هم باید تعریف میکردم راستی !!! :

فرض کنید در جهت ساعت گرد دارید موقعیت عدد هارو دنبال میکنید ، یعنی بالا سر ۱ وایستادید بعد میرین بالا سر ۲ (در جهت ساعت گرد میچرخین تا ۲ رو پیدا کنید .) بعد ۳ ، بعد ۴ ، .... ، تا میرسید به n و بالاخره دوباره میرین سراغ ۱

حالا ببینید در آخر چند بار دور دایره گشتین ، مثلا اگه عددا بصورت زیر باشن n بار میگردید :

1 2 3 4 .... n

(اگه درجه نگاشت رو پاد ساعت گرد تعریف می*کردم ۱ بار میگشتین )

به این تعداد میگن درجه نگاشت .

قشنگ بود, ولی یه تذکر کوچولو, تو مثالت فک کنم درجه نگاشت n-1 باشه نه n.