Processing math: 100%

المپدیا

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

ابزار کاربر

ابزار سایت


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

جدول جادویی

جدول جادویی n×n جدولی است که برای هر i و j که 1in و 1jn ، در خانه ی (i,j) آن عدد i+j نوشته شده است. در هر مرحله می توان این جدول را به صورت زیر تغییر داد.

  • در هر مرحله یک زیر مجموعه از سطرها مانند S ، یک زیرمجموعه از ستون ها مانند T و یک عدد k>۰ انتخاب می کنیم.سپس عدد تمام خانه های (i,j) که iS و jT را k واحد کم می کنیم.

در مثال زیر تمام اعداد یک جدول جادویی ۲×۲ در سه مرحله صفر شده اند. زیر مجموعه های S و T توسط پیکان در شکل نشان داده شده اند.

الف) روشی ارائه دهید که در ۱۵ مرحله تمام اعداد یک جدول جادویی ۱۰۰×۱۰۰ را صفر کند.

ب) ثابت کنید در کم تر از ۱۴ مرحله نمی توان تمام اعداد یک جدول جادویی ۱۰۰×۱۰۰ را صفر کرد.


ابزار صفحه