| ClipArtMag Science Blog |

Free Cliparts

Гипотеза о коллекциях подмножеств

Перевод статьи - A Conjecture on Collections of Subsets

Автор - Philip J. Erdelsky

Источник оригинальной статьи:

http://www.efgh.com/math/subsets.htm

3 сентября 2002

Пожалуйста, пишите замечания, исправления и дополнения к админу по pje@efgh.com.

ПРИМЕЧАНИЕ: поиск Интернета наконец показал, что эта гипотеза верна и известна как Теорема Спернера.

Вот проблема в комбинаторике, которая много лет прослушивала меня. Возможно, комбинаторист может решить ее сразу. Я не могу.

Рассмотрите конечное множество S объектов N. Коллекция без включения - коллекция C подмножеств S, таким образом, что никакое подмножество в коллекции не надлежащее подмножество никакого другого подмножества в коллекции.

Один вид коллекции без включения - коллекция всех подмножеств единственного элемента S. Другой - коллекция всех подмножеств с двумя элементами. Однако есть многие, многие другие.

Вот гипотеза: коллекция N/2-элемент подмножеств содержит, по крайней мере, столько же подмножеств сколько любая другая коллекция без включения. Здесь N/2 округляется вверх или вниз, если N нечетно. Это не имеет никакого значения, потому что размер коллекции в обоих случаях одинаковый.

Проверка грубой силы с помощью компьютера может проверить эту гипотезу только для очень малых значений N. Число подмножеств равно P = 2N, а количество коллекций подмножеств-2P, что становится очень большим очень быстро!

Применение, которое дало начало этой гипотезе, вероятно, устаревшее к настоящему времени, но вот оно. Раньше было что-то названное PROM (programmable read-only memory). Это было произведено содержащий все ноли. При помощи специальной машины, которая выборочно сожгла внутренние связи, пользователь может изменить любой ноль на один, но не наоборот. Это назвали, "жгущий" PROM.

Теперь предположите, что каждое слово PROM содержит биты N. Если вы закодируете информацию, чтобы точно N/2 бита каждого слова были изменены на единицы, информация не может быть изменена и останется действительной. Если существует коллекция без включения, большего, чем совокупность всех N/2-элементных подмножеств, существует более эффективный способ сделать это.