باغچه آبولف به صورت یک جدول ۱۳۹۸ در ۱۳۹۸ است. به مجموعه ای از ۱۳۹۸ خانه جدول سلطانی می گوییم اگر هیچ دو تا از آن ها هم‌سطر یا هم‌ستون نباشند. خانه واقع در سطر i ام و ستون j ام را با (i,j) نمایش می دهیم.
در ابتدا در تمام خانه های (i,j) که i<j است آفتی قرار دارد. آبولف دستگاهی خریده است که می تواند مجموعه ای سلطانی از جدول انتخاب کند و تمام خانه های آن را دگرگون کند. پس از تعداد دلخواهی مرحله استفاده از دستگاه، کمینه تعداد آفت هایی که آبولف در باغچه اش خواهد داشت چیست؟
پاسخ
پاسخ برابر $\frac{1398}{2} = 699 $ است.
ابتدا روشی برای سلطان ارائه می کنیم که در پایان، حداکثر ۶۹۹ آفت وجود داشته باشد. فرض کنید سطر ها از بالا به پایین و ستون ها از چپ به راست شماره گذاری شده باشند. به قطری که خانه $(1,1398)$ تا خانه $(1398,1)$ را در بر می گیرد، قطر آبولفی می گوییم.
خانه هایی که ابتدا آفت دارند ( خانه های زیر قطر اصلی ) را به صورت قطری لایه بندی می کنیم. ( بزرگترین قطر که ۱۳۹۷ خانه دارد لایه ۱ و کوچک ترین قطر که یک خانه دارد را لایه ۱۳۹۷ می نامیم ) به ازای هر $1\le i \le 1398$ سلطان در مرحله i ام خانه های لایه i به همراه خانه های ۱ تا i قطر آبولفی را انتخاب کند. با این روش در انتهای کار تنها خانه های قطر آبولفی می توانند آفت داشته باشند. اگر در قطر آبولفی بیش از نصف آفت وجود داشت، یک بار دستگاه را روی قطر آبولفی اعمال می کنیم. با این روش، حداکثر ۶۹۹ آفت در باغچه خواهیم داشت.
حال ثابت می کنیم در هر لحظه حداقل 699 آفت در جدول وجود دارد. به یک سطر فرد می گوییم اگر تعداد فردی آفت داشته باشد. به همین ترتیب سطر زوج را تعریف می کنیم. در هر مرحله سطر های زوج، فرد می شوند و بالعکس ( زیرا دقیقا یک خانه از هر سطر تغییر وضعیت می دهد. در ابتدا ۶۹۹ سطر فرد و ۶۹۹ سطر زوج داریم. پس همواره ۶۹۹ سطر فرد خواهیم داشت که هر کدام دست کم یک آفت دارند.