Областная олимпиада по математике, 2026 год, 10 класс

Шахмат ретімен екі түске (қара және ақ) боялған шексіз торкөз қағаз берілген. Бұл қағаздан 25 ақ және 25 қара торкөзден тұратын торкөзді фигура қиып алынған. Бұл фигураның кез келген торкөзінен кез келген басқа торкөзіне ортақ қабырғасы бар көрші торкөздері (диагональ бойынша емес) өту арқылы жетуге болады. Фигурадан кепілді түрде қиып алуға болатын доминолардың ең көп саны қандай? (Домино — бұл өлшемі $1\times 2$ немесе $2 \times 1$ болатын фигура). ( П. Кожевников )

Комментарий/решение

Рассмотрим клетки фигуры как вершины связного графа, где соседние по стороне клетки соединены рёбрами. Степень каждой вершины не превышает 4. Возьмём остовное дерево этого графа. В нём всегда есть висячие вершины. У любой невисячей вершины A к ней присоединена хотя бы одна висячая вершина B, и клетки A и B образуют домино.Удаляя такое домино, мы удаляем не более 4 вершин, при этом связность сохраняется. Всего вершин 50, значит, так можно вырезать 12 домино, после чего останутся ещё две соседние клетки, образующие 13-е домино.Следовательно, из фигуры можно вырезать не менее 13 домино.