В некоторых клетках таблицы 1000 × 1000 стоят плюсики. Каждый плюсик является единственным либо в строке, либо в столбце. Какое наибольшее количество плюсиков может стоять в таблице?
Владимир Трошин
Стаж: 3 года 2 месяца
Баллы: 10671 (Легенда)
#3147: ответ на задачу №12175
Условие
Нужно правильно понять условие задачи. Не «в каждой строке и каждом столбце стоит единственный плюсик», а «каждый плюсик является единственным либо в строке, либо в столбце». Поэтому решать будем так: поставим плюсики в каждой клетке первой строки и в каждой клетке первого столбца таблицы. После этого уберем один плюсик из угловой клетки, который был одновременно и в строке, и в столбце. Оставшиеся 1998 плюсиков удовлетворяют условию задачи. 999 из них являются единственными в столбцах от 2-го до 1000-ного, а 999 являются единственными в строках от 2-ой до 1000-ной.
Ответ 1998.