Применение классических комбинаторных методов к разным задачам → .06 Чётность

Заметим, что у каждого ребенка в наборе есть буквы K, О и P, так как в данных словах эти буквы встречаются дважды, а у одного ребенка буквы не повторяются. Буквы, из которых составлялись слова, помимо и -Л, Т и H , каждая использована по одному разу. Значит, всего было использовано карточек, а у двух малышей карточек в сумме четное количество. Значит, хотя бы одна карточка не использована.

Заметим, что всего пар соседних клеток из разных домино штук. В каждой из них должно быть хотя бы одно нечетное число. Но нечетных чисел всего по единиц, троек и пятерок.

Посмотрим на два оставшихся числа. Так как сумму всех чисел от до Аня знает, то два оставшихся числа таковы, что по их произведению также нельзя определить четность их суммы. Поэтому их произведение можно представить как причем и разной четности, а и одной. Тогда и — четные, поэтому четное из чисел и равно Далее все восстанавливается однозначно, и получаются числа и или и Тогда произведение пяти чисел будет равно

Первое решение.

Обозначим детей, давших ответы через А, Б, В соответственно. Заметим, что если в классе мальчиков, то первое число в ответах девочек имеет ту же чётность, что и , а в ответах мальчиков - противоположную. Следовательно, дети А и Б одного пола, а В - другого.

Первые числа в ответах А и Б отличаются на 4, значит, они оба неправильные. Таким образом, количество одноклассников у А и Б равно 15 , а количество одноклассниц - 11 .

Если А и Б - мальчики, то в классе 16 мальчиков и 11 девочек. При этом у девочки В тогда 16 одноклассников и 10 одноклассниц, и ее ответ противоречит условию. Значит, А и Б девочки, и в классе 15 мальчиков и 12 девочек. ______________________

Второе решение.

Пусть какой-то ребёнок написал числа . Если бы оба числа он написал правильно, то он бы написал один из четырёх вариантов: .

Тогда, если этот ребёнок — мальчик, то существует четыре варианта количества мальчиков и девочек в классе: и .

Аналогично, если этот ребёнок — девочка; возможные варианты в этом случае: .

Таким образом, каждый из ответов даёт нам восемь вариантов, сколько мальчиков и девочек могло быть в классе, один из которых должен быть верным:

для это ;

для это ;

для это .

Осталось заметить, что только вариант встречается во всех трёх строчках.

Назовем группой экономистов несколько (возможно, одного) экономиста, сидящих подряд, слева и справа от которых сидят представители других профессий. При этом если нет менеджера или бухгалтера, рядом с которым сидят два экономиста, то каждый человек поднял руку не более одного раза, а тогда общее количество поднявших руку людей равно удвоенному количеству групп, т.е. четно. А по условию их Противоречие.

Всего в строке и столбце, проходящих через данную клетку 19 клеток, поэтому если мы проделаем операции со всеми парами строк и столбцов таблицы (всего операций), то каждый знак в таблице поменяется 19 раз, став из минуса плюсом.

100 операций достаточно.

_________________________________________________________________________________________________________________________________________________________________________________

Операцию замены знаков во всех клетках некоторого столбца и некоторой строки будем называть операцией относительно клетки-пересечения этих строки и столбца. Клетки, относительно которых мы делали операции, назовём красными, остальные синими. Строки и столбцы, содержащие чётное число красных клеток назовём чётными, а содержащие нечётное число красных клеток — нечётными.

_________________________________________________________________________________________________________________________________________________________________________________

Допустим, можно поменять все знаки в таблице меньше чем за 100 операций, тогда рассмотрим некоторую синюю клетку в строке и столбце . Чтобы знак в поменялся, нужно, чтобы, чтобы и вместе содержали нечётное количество красных клеток, можно считать строку чётной, а столбец — нечётным.

Заметим, что на пересечении строки и столбца одинаковой чётности должна стоять красная клетка, а на пересечении строки и столбца разной чётности — синяя, иначе знак в этой клетке после всех операций не изменится. Следовательно, количество красных клеток в каждой чётной строке равно числу чётных столбцов, а количество синих — числу нечётных столбцов таблицы. Есть хотя бы одна чётная строка , значит, всего в таблице чётное число нечётных столбцов. Но количество красных клеток в каждой нечётной строке (нечётное!) равно числу нечётных столбцов, то есть чётному числу — противоречие с тем, что есть хотя бы один нечётный столбец. Следовательно, нельзя обойтись меньше, чем 100 операциями.