Выбрано 2 задачи 
Убрать все задачи
Задан числовой массив А [1:m]. Сосчитать и напечатать, сколько различных чисел в этом массиве. Например, в массиве 5, 7, 5 различных чисел два (5 и 7).
РешениеНа листе бумаги отмечены точки A, B, C, D. Распознающее устройство может абсолютно точно выполнять два типа операций: а) измерять в сантиметрах расстояние между двумя заданными точками; б) сравнивать два заданных числа. Какое наименьшее число операций нужно выполнить этому устройству, чтобы наверняка определить, является ли четырёхугольник ABCD квадратом?
Решение
|
|
 |
Условие
В некоторых клетках квадратной таблицы n×n стоят звёздочки. Известно, что если вычеркнуть любой набор строк (только не все), то найдётся столбец ровно с одной невычеркнутой звёздочкой. (В частности, если строки совсем не вычёркивать, то столбец ровно с одной звёздочкой существует.) Доказать, что если вычеркнуть любой набор столбцов (только не все), то найдётся строка ровно с одной невычеркнутой звёздочкой.
Решение
Заметим, что после перестановки строк и столбцов данной таблицы получаем таблицу, удовлетворяющую условиям задачи. Возьмём столбец с одной звёздочкой (такой существует) и поменяем его с первым столбцом, а также строку, в которой стоит эта звёздочка, поменяем с первой строкой. Затем вычеркнем первую строку и применим утверждение задачи. А после этого переставим строку и столбец со звёздочкой со второй строкой и вторым столбцом. Далее вычеркнем первые две и поступим аналогично. Будем продолжать процесс, пока не упорядочим всю таблицу. Полученная таблица, во-первых, содержит звёздочки на диагонали, а во-вторых, не содержит звёздочек под диагональю. Если теперь вычеркнуть несколько столбцов и номер последнего не вычеркнутого столбца k, то в строчке с номером k ровно одна звёздочка.
