Задача
COM-B2-M03-P001 Подмножества как строки
#1
★★☆☆☆ Уровень 2 из 5
Постройте биекцию между подмножествами множества \(\{1,\ldots,n\}\) и бинарными строками длины \(n\). Сделайте вывод, что подмножеств \(2^n\).
Записывайте \(1\), если элемент выбран, и \(0\), если нет.
Подмножеству \(A\) сопоставим строку \(a_1\ldots a_n\), где \(a_i=1\), если \(i\in A\), и \(a_i=0\), если \(i\notin A\). По такой строке однозначно восстанавливается \(A=\{i:a_i=1\}\). Значит, это биекция. Бинарных строк длины \(n\) ровно \(2^n\).
Стартовая задача на явное обратное отображение.