المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:مرحله‌ی سوم:دوره‌ی ۲۳:سوال ۲

واﻟﯿﺒﺎل

فرض کنید یک جدول با تعدادی عدد پر شده باشد. جمع اعداد سطر ‎$i$‎اٌم آن را ‎$a_i$‎ و جمع اعداد ستون ‎$i$‎اٌم آن را ‎$b_i$‎ می نامیم. دنباله کلیدی یک جدول ‎$m \times n$‎ را به صورت زیر تعریف می‌کنیم: ‎$$[a_1,a_2,\ldots,a_m,b_1,b_2,\ldots,b_n]$$‎

  1. بعد از بازی خوب ایران مقابل صربستان علی کوچولو تمامی حالات پر کردن یک جدول ‎$4 \times 4$‎ با ‎0‎ و ‎1‎ را به همراه دنباله کلیدی هر کدام روی کاغذ نوشته است. اگر تعداد دنباله‌های متمایز تولید شده برابر ‎$M_1$‎ باشد باقی‌مانده‌ی ‎$M_1^4$ (عدد ‎$M_1$‎ به توان 4)‎ بر ‎$\Delta$‎ چند است؟‎
  2. سپس علی تصمیم گرفت یک جدول‎$7 \times 7$‎ را با ‎0‎ و ‎1‎ پر کند حال او می‌خواهد بداند در چند جدول تمامی اعداد دنباله کلیدی برابر ‎3‎ هستند. اگر این مقدار برابر ‎$M_2$‎ باشد، باقی‌مانده‌ی عدد ‎$M_2$‎ بر ‎$\Delta$‎ چند است؟‎
  3. فرض کنید تمامی حالات پر کردن جدول ‎$5 \times 5$‎ با ‎0‎ و ‎1‎ و ‎2‎ که حداقل یک عدد ‎2‎ در جدول آمده باشد را بنویسیم و دنباله ی کلیدی هر کدام از آن‌ها را نیز محاسبه کنیم. اگر تعداد دنباله‌های متمایز تولید شده برابر‎$M_3$‎ باشد، باقی‌مانده‌ی عدد ‎$M_3$‎ بر ‎$\Delta$‎ چقدر است؟

ابزار صفحه