Войти в систему

Home
    - Создать дневник
    - Написать в дневник
       - Подробный режим

LJ.Rossia.org
    - Новости сайта
    - Общие настройки
    - Sitemap
    - Оплата
    - ljr-fif

Редактировать...
    - Настройки
    - Список друзей
    - Дневник
    - Картинки
    - Пароль
    - Вид дневника

Сообщества

Настроить S2

Помощь
    - Забыли пароль?
    - FAQ
    - Тех. поддержка



Некто написал в [info]studium,
Задачка:

Счетно ли множество всех конечных подмножеств натуральных чисел?

Верно ли такое решение (ответ -- счетно):

Запишем каждое подмножество как последовательность из нулей и единиц так, что на месте чисел, лежащих в подмножестве, стоят 1, а на месте чисел, не лежащих в подмножестве, стоит 0.
Например, {1,2,5} -- 110010000...

Теперь занумеруем все подмножества. Рассмотрим запись целых чисел в двоичной системе счисления. Будем брать двоичное число, записывать его наоборот (младший разряд слева) и приписывать справа бесконечно много нулей.

0 -> 0000000...
1 -> 1000000...
10 -> 0100000...
11 -> 1100000...
100 -> 0010000...
101 -> 1010000...
110 -> 0110000...
111 -> 1110000...
...

Так рано или поздно мы доберемся до любой конечной последовательности из нулей и единиц. Именно, чтобы узнать номер данной последовательности, обрежем ее по последней единице, за которой начинается бесконечность нулей (мы знаем, когда начинаются нули, потому нам известно, что подмножество конечно, и значит, известен его последний элемент -- последняя единица в последовательности). Затем перевернем получившееся число -- это и будет номер последовательности в двоичной системе счисления.


(Читать комментарии)

Добавить комментарий:

Как:
(комментарий будет скрыт)
Identity URL: 
имя пользователя:    
Вы должны предварительно войти в LiveJournal.com
 
E-mail для ответов: 
Вы сможете оставлять комментарии, даже если не введете e-mail.
Но вы не сможете получать уведомления об ответах на ваши комментарии!
Внимание: на указанный адрес будет выслано подтверждение.
Имя пользователя:
Пароль:
Тема:
HTML нельзя использовать в теме сообщения
Сообщение:



Обратите внимание! Этот пользователь включил опцию сохранения IP-адресов пишущих комментарии к его дневнику.