دو تا سوال

دو تا سوال بچه ها تو نظرات پرسیده بودند که می خواستم راه حلشون رو اینجا بنویسم.

ولی متاسفانه درج تصویر توی بلاگفا یه سری مشکلاتی داره. برای همین به راهنمایی اکتفا می کنم.

سوال 1:

در یک جدول n*n اعداد در هر سطر با هم متمایزند ثابت کنید اعداد هر سطر میتوان به گونه ای جابه جا کرد که اعداد هر ستون نیز متمایز شوند.

اعداد جدول رو a_ij بگیرید، حالا برهان خلف بزنید و یه چند جمله ای مناسب رو در نظر بگیرید. حالا با تغییر وضعیت اعداد(یعنی جابجایی شون تو سطر ها) هر بار یه چندجمله ای جدید به دست میاریم. این چندجمله ای ها رو با توجه به درجه ی جایگشت شون -که باید تعریف بشه درجه ی جایگشت چیه- جمع و تفریق کنیم، حالا با استفاده از خواص چند جمله ای ها و فرض مساله (این که اعداد هر سطر متمایزند) به تناقض برسید.

سوال 2:

حاصل مجموع مربعات انتخاب i نفر از n نفر وقتی که i از 0 تا n تغییر می کند را بیابید.

راه حل:

خب از روش های محاسباتی زیادی میشه این سوال رو حل کرد.

ولی راه ترکیبیاتیش اینه:

2n نقطه داریم که نصفشون آبی اند و نصفشون قرمزند. می خوایم n تا نقطه انتخاب کنیم، این کار رو میشه به انتخاب n از 2n حالت انجام داد،

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

ترکیبیات

سلام.

می خواستم بگم که سوالای ترکیبیات رومانی و روسیه خوبند. کم کم بشینید حلشون کنید تا ضعیف نمونید قوی بشید.