المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:مرحله ی دوم:دوره ی ۱۵:سوال ۸

جدول‌های ستون‌متعادل

یک جدول $n \times m$ (دارای $n$ سطر و $m$ ستون) از اعداد صفر و یک «ستون‌متعادل» است٬ اگر هر دو ستون مجزا از آن را که کنار هم قرار دهیم٬ تعداد زوج‌های ۱۰٬۰۱٬۰۰ و ۱۱ که در سطرهای مختلف از این دو ستون قرار دارند برابر باشند. مثلاً جدول زیر ستون‌متعادل است زیرا اگر ستون ۱ و ۲ یا ۲ و ۳ و یا ۱ و ۳ از آن را در کنار هم قرار دهیم٬ از هر زوج ۱۰٬۰۱٬۰۰ و ۱۱ یکی تولید می‌شود.

الف) به ازای هر $k$ ($3 \le k$) یک جدول ستون‌متعادل $ 2^k \times (2^k - 1)$ بسازید. (دارای $2^k$ سطر و $2^k - 1 $ ستون)

ب) می‌دانیم هیچ جدول ستون‌متعادل $ 2^k \times (2^k + 1)$ وجود ندارد. حال ثابت کنید هیچ جدول ستون‌متعادل $2^k \times 2^k$ نیز نمی‌توان ساخت.


ابزار صفحه