Две задачки по дискретной математике

[destronix]

1. Борьба c воровством в космических масштабах

Если брать одинаковую плату за все номера, то поскольку номеров бесконечное число, денег тоже будет бесконечное количество. Ho как мы знаем, из бесконечно большой бочки можно незаметно воровать, причем в неограниченных, и даже бесконечных масштабах. Как установить плату за проживание в гостинице, чтобы все деньги были под контролем, и любое воровство было бы сразу заметно?




2. Задачка Георга Кантора

До сих пор все встреченные нами бесконечные множества были счетными (их элементы оказывалось возможным пересчитать). Возникает вопрос: может быть несчетных множеств вообще не существует? Попробуйте (вслед за Георгом Кантором) доказать, что множество чисел между нулем и единицей несчетно (это множество называется множеством мощности континуума).


Заранее огромное спасибо

[Draeden]

Элементарное и красивое доказательство дал сам Кантор,
т.н. Канторовский диагональный процесс:

пусть все числа между нулём и единицей счётны, тогда их можно занумеровать:


очевидно эти числа можно записать десятичными дробями:



возъмём и построим число , -ая цифра которой равна если -ая цифра не равна и в противном случае.
Число не совпадает ни c одним из чисел хотя и принадлежит интервалу . Противоречие.