سلام میگم یک سر به سایت www.fanavard.ir بزنید. مسابقات برنامه نویسی شون شروع شده. گواهی رسمی از طرف دانشگاه شریف می ده. 50 تا سکه هم جایزشه
2016-10-26 08:10:28 -0600 امیر شکریآمار پرسش:
- پرسیده شده: 2014-07-01 17:03:30 -0600
- مشاهده شده: 188 بار
- بروز شده: 2014-07-18 16:29:26 -0600
پرسش‌های مشابه:
چرخاندن میز با n مهمان طوری که حداقل دو مهمان سرجای خود قرار بگیرند
تعداد گراف‌های دو بخشی و غیردوبخشی $n$راسی و $2n$ یالی
تورنمنت با تعداد زیادی مسیر همیلتونی
گروهی از دانش آموزان شامل حداقل نصف افراد ، هر پسر با تعداد فردی دختر دوست است
n نفر با کلاه های قرمز و آبی و حدس زدن بیشترین تعداد درست
n زیرمجموعه با میانگین اندازه ی داده شده و وجود دو زیرمجموعه با اشتراک زیاد.
نکاتی در مورد نوشتن پاسخ:
استفاده از ویرایشگر:
علائم ریاضی:
مساله ی مسابقه ی دانشجویی 93_ ماتریس
فرض کنید $A$ ماتریسی $n\times n$ باشد که درایه های آن همگی از اعداد ${1,2,\ldots,n}$ هستند . ثابت کنید با جابجایی ستونهای $A$ می توان به ماتریس $B$ رسید که \begin{equation} K(B)\leq n \end{equation} باشد . به طوری که $K(B)$ برابر است با تعداد اعضای مجموعه ی
${(i,j):b_{ij}=j}$
2014-07-01 17:03:30 -0600
حمید کاملی 2921 ● 30 ● 56 ● 83
نظرات
1 پاسخ
یک راه حل احتمالاتی :
یک جایگشت تصادفی روی ستون های ماتریس $A$ در نظر می گیریم . فرض کنید ماتریس $B$ با جایگشت دادن ستون های $A$ بدست بیاید. متغیر تصادفی $X_{ij}$ را برابر با یک در نظر می گیریم اگر ستون $j$ به ستون شماره ی $a_{ij}$ منتقل شود و در غیر اینصورت $X_{ij}$ را برابر با صفر در نظر می گیریم.
به عنوان مثال فرض کنید $a_{35}=1$ باشد . $X_{35}$ را برابر با یک در نظر می گیریم اگر ستون 5 به ستون شماره ی یک منتقل شود.
بدیهی است که \begin{equation} K(B)=\sum_{1\leq i\leq n , 1\leq j \leq n}X_{ij} \end{equation} با توجه به اینکه هر عدد $i$ در ماتریس $A$ با احتمال $\frac{1}{n}$ به ستون $i$ منتقل می شود ، داریم $E[X_{ij}]=\frac{1}{n}$ و با توجه به خطی بودن امید ریاضی داریم \begin{equation} E[K(B)]=\sum_{1\leq i\leq n , 1\leq j \leq n}E[X_{ij}]=n \end{equation} پس یک جایگشت تصادفی روی ستون های $A$ وجود دارد به طوری که برای ماتریس بدست آمده ی $B$ داریم $K(B)\leq n $.
2014-07-18 16:28:32 -0600
حمید کاملی 2921 ● 30 ● 56 ● 83
نظرات