المپدیا

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

ابزار کاربر

ابزار سایت


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

سوال ۱

$mn$ شکلات در خانه های یک جدول $m×n$ قرار گرفته اند (لزومی ندارد در هر خانه دقیقاً یک شکلات باشد. است برخی از خانه ها بدون شکلات و برخی از خانه ها شامل بیش از یک شکلات باشند). در هر مرحله می توانیم یکی از چهار کار زیر را انجام دهیم:

  • دو سطر را انتخاب کرده و محتوایشان را جابه جا کنیم.
  • دو ستون را انتخاب کرده و محتوایشان را جابه جا کنیم.
  • دو خانه را انتخاب کرده و محتوایشان را جابه جا کنیم.
  • تعدادی شکلات از یک خانه برداشته (نه لزوماً تمام شکلات های آن خانه) و به خانه ای مجاور منتقل کنیم.(دو خانه را مجاور گوییم، اگر یک ضلع مشترک داشته باشند).

می خواهیم با تعدادی مرحله به وضعیتی برسیم که هر خانه دقیقاً یک شکلات داشته باشد. کم ترین تعداد مرحله ی لازم برای رسیدن به این هدف را فان دی نامبر جدول می نامیم. بیشینه ی فان دی نامبر در میان تمام جدول های $m×n$ چقدر است؟


ابزار صفحه