Processing math: 27%

المپدیا

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

ابزار کاربر

ابزار سایت


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

سوال ۱

تعریف: به ماتریس ‎n×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‎ وجود داشته باشد. ‎‎

ابزار صفحه