Знаменитая "диагональная конструкция" придумана Кантором для доказательства того, что нельзя пронумеровать натуральными числами все последовательности нулей и единиц. Она может быть пересказана так: "на n-м шаге мы гарантируем выполнение n-го требования и так строим объект, удовлетворяющий всем требованиям".
Этот тип рассуждений встречается во многих ситуациях (в теории алгоритмов и не только). Мы разберём несколько примеров в зависимости от интересов слушателей.
Задача для разогрева: можно ли отметить точки на прямой так, чтобы расстояния между ними были натуральными и среди них ровно по одному разу встречались все натуральные числа?
Александр Шень (CNRS, ИППИ РАН) — специалист по дискретной математике и информатике, автор книг, популяризатор.
Этот тип рассуждений встречается во многих ситуациях (в теории алгоритмов и не только). Мы разберём несколько примеров в зависимости от интересов слушателей.
Задача для разогрева: можно ли отметить точки на прямой так, чтобы расстояния между ними были натуральными и среди них ровно по одному разу встречались все натуральные числа?
Александр Шень (CNRS, ИППИ РАН) — специалист по дискретной математике и информатике, автор книг, популяризатор.
