المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره ی تابستان:دوره ی ۲۲:تئوری مقدماتی اول:سوال ۱

سوال ۱

تعریف: به ماتریس ‎$n \times n$‎ همانند ‎$A$‎ بامزه می‌گوییم هرگاه تمام درایه‌های آن ‎$+1$‎ و یا ‎$-1$‎ باشند و به ازای هر دو سطر مثل ‎$i$‎ و $j$ داشته باشیم: ‎ ‎$$\sum_{k=1}^{n}‎ ~ ‎a_{i,k} \times a_{j,k} =0 $$ تعریف: به ماتریس ‎$n \times n$‎ همانند ‎$A$‎ خوشمزه می‌گوییم، هرگاه بامزه باشد و به ازای ‎$1\leq i \leq n$‎ داشته باشیم: ‎$a_{i,1}=a_{1,i}=+1$‎

  1. ثابت کنید اگر ماتریس ‎$n \times n$‎ بامزه وجود داشته باشد، ماتریس ‎$n \times n$‎ خوشمزه نیز وجود دارد. ‎
  2. ‎$n$‎ دنباله به نام‌های ‎$A_1,\ldots,A_n$‎ داریم که طول هر کدام ‎$n-1$‎ بوده و اعضای هر کدام از آنها ‎$+1$‎ و یا ‎$-1$‎ است. ضرب داخلی دو بردار برابر مجموع حاصلضرب درایه‌های متناظر آنها در یکدیگر است. در صورتی که ضرب داخلی هر دو بردار از این ‎$n$‎ تا منفی شود، به این ‎$n$‎تایی تلخ می‌گویند‎. ثابت کنید ‎$n$‎تایی تلخ وجود دارد اگر و فقط اگر، ماتریس بامزه ‎$n \times n$‎ وجود داشته باشد. ‎‎

ابزار صفحه