Соответствия и биекция

Иногда честно сосчитать количество каких-то объектов очень сложно. Но если мы хотим узнать, каких объектов больше, необязательно их считать: можно сравнить и по-другому. Для этого нужно построить соответствие: если так получится, что каждому элементу одного множества соответствует ровно один элемент другого множества, и наоборот, то в этих двух множествах поровну объектов. Такое соответствие еще называют взаимно однозначным, или биекцией.

Поясним на примерах.

1.  В классе трансфигурации нарисована окружность. На ней отмечены 20 синих точек и 1 красная точка. Гарри посчитал количество треугольников с вершинами в синих точках, а Рон посчитал количество четырехугольников с вершинами в этих точках, у которых одна из вершин красная. У кого получилось больше фигурок?

Ответ. Поровну

Решение. Сопоставим каждой четверке точек, одна из которых красная, тройку, в которой присутствуют те же самые 3 синие точки, что и в этой четверке. Наоборот, каждой тройке синих точек сопоставим ту четверку, в которой присутствуют те же синие точки и добавляется красная точка.

Тогда мы получим соответствие между четырехугольниками, которые считал Рон, и треугольниками, которые считал Гарри. Причем каждому четырехугольнику будет соответствовать один треугольник, а каждому треугольнику — ровно один четырехугольник. Значит, фигурок у ребят поровну.

2.  Усидчивый Невилл выписал все 101-значные числа, состоящие только из цифр «1» и «2». Каких чисел больше: в которых четное число единиц или в которых нечетное число единиц?

Ответ. Поровну

Решение. Вновь сопоставим числам одной группы числа другой группы. На этот раз рассмотрим произвольное число, например, 11212…211. Поменяв в нем все единицы на двойки и наоборот, мы получим число 22121…122. Заметим, что если в числе было единиц, то после замены их будет При этом числа и разной четности, так как их сумма нечетна. Поэтому из числа одной группы, то есть с четным числом единиц, мы получили число другой группы, то есть с нечетным числом единиц, и наоборот.

Мы снова получили соответствие, в котором каждому числу одного множества соответствует ровно одно число другого множества. При этом никаких чисел без пары не осталось. Значит, чисел в двух множествах поровну.

Если же однозначное соответствие построилось, но некоторые объекты остались без пары, то можно сделать вывод, что то множество, в котором остались лишние, больше.

3.  У каждой домашней собаки только один хозяин. Есть люди, которые держат сразу несколько собак. Кого на Земле больше: собак или их хозяев?

Ответ. Собак

Решение. Сопоставим каждому хозяину одну из имеющихся у него собак. При этом останутся «лишние» собаки, ведь по условию у некоторых хозяев несколько собак. При этом разным хозяевам сопоставлены разные собаки. Значит, у нас получилось однозначное соответствие, каждому хозяину сопоставлена собака, но остались и лишние собаки. Значит, собак больше.