Loading [MathJax]/jax/output/HTML-CSS/jax.js

المپدیا

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

ابزار کاربر

ابزار سایت


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

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

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

الف) به ازای هر k (3k) یک جدول ستون‌متعادل 2k×(2k1) بسازید. (دارای 2k سطر و 2k1 ستون)

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


ابزار صفحه