Maths Olympiad Prep

Library / /54 of 61

Combinatorics Difficulty 6.9 National olympiad Prove it Ukraine

Mariyka has drawn a square grid 2006×20062006 \times 2006 on a blackboard. During one step, it is allowed to choose any unit segment of that grid and erase it together with all adjacent segments, which were not erased before (so, at most 77 segments can be erased in one step). Is it possible to erase the whole drawing in no more than 13000001300000 steps?

Solution

Відповідь: ні, не можна. Задача полягає в тому, чи можемо ми покрити всю "сітку" таблиці 13000001300000 фігурками, зображеними на рисунку. Якщо така фігурка не лежить повністю в таблиці, то вона покриває не більше 66 відрізків. Якщо фігурка повністю знаходиться в таблиці, тоді інші фігурки повинні покрити відрізки BCBC і EFEF (див. рисунок). Фігурка, яка закриє BCBC, обов'язково закриє й хоча б один з відрізків BGBG, CHCH (це легко перевіряється невеличким перебором). Аналогічно, фігурка, яка закриє EFEF, обов'язково закриє й принаймні один з відрізків FGFG, EHEH. Кожному відрізку фігурок, що покривають відрізок таблиці без перекриття з іншими відрізками, поставимо у відповідність коефіцієнт 11, кожному з відрізків, що покривають з перекриттям, — коефіцієнт 1/21/2. Тоді сума всіх коефіцієнтів для однієї фігурки не більша за 66, по всіх фігурках — не перевищує 78000007800000.

З іншого боку, по всій покритій таблиці сума коефіцієнтів має бути не меншою за кількість відрізків: 2200620072 \cdot 2006 \cdot 2007. Але 220062007>78000002 \cdot 2006 \cdot 2007 > 7800000, і тому всю "сітку" таблиці покрити 13000001300000 фігурками не можна.

Figure 1

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.