|
Freicoin или Фрейкоин (FRC)
Валюта создана на основе Bitcoin в 2013 году. Цель Freicoin - решить одну из проблем современных денег, основанную на том, что инвесторы часто накапливают у себя валюту вместо вложения её. Эта проблема способна дестабилизировать цены и затормозить экономический рост. Текущий курс Freicoin – 0,00649209 доллара. Ограничение количества эмиссируемых монет в 100 млн.
Чтобы решить эту проблемы создатели Freicoin внесли годовой налог за «простой» – 5%, которым будут автоматически облагаться все сделки. По их мнению, этот налог должен стимулировать оборот валюты. Кроме того, создатели Freicoin, преследуя благую цель, утвердили правило, согласно которого 80% валюты будет выплачено фондом Freicoin Foundation как пожертвования, а 20% будут получать участники сети, которые предоставляют вычислительные мощности.
2.4 Схема Якоба Штейнера
Система Штейнера (названа именем Якоба Штейнера) — вариант блок-схем, точнее, t-схемы с λ = 1 и t ≥ 2.
Система Штейнера с параметрами t, k, n (записывается S(t,k,n)) — это n-элементное множество S вместе с набором k-элементных подмножеств множества S (называемых блоками) со свойством, что каждое t-элементное подмножество S содержится ровно в одном блоке. В альтернативном обозначении блок-схем S(t,k,n) обозначается как t-(n,k,1) схема.
Это определение относительно ново и обобщает классическое определение системы Штейнера, в котором дополнительно требуется, чтобы k = t + 1. Схема S(2,3,n) называлась (и по-прежнему называется) системой троек Штейнера, S(3,4,n) называлась системой четвёрок Штейнера и так далее. После обобщения определения система имён соблюдается не так строго.
В теории схем было долгое время неизвестно, существует ли нетривиальная (t < k < n) система Штейнера с t ≥ 6, а также существует ли бесконечно много схем с t = 4 или 5[1]. Утвердительный ответ дал Питер Киваш в 2014[2][3][4].
Примеры
Конечные проективные плоскости
Конечная проективная плоскость порядка q с прямыми в качестве блоков является схемой S(2, q + 1, q2 + q + 1), поскольку она имеет q2 + q + 1 точек, каждая прямая проходит через q + 1 точек, а каждая пара различных точек находится ровно на одной прямой.
Конечные аффинные плоскости
Конечная аффинная плоскость порядка q с прямыми в качестве блоков является схемой S(2, q, q2). Аффинная плоскость порядка q может быть получена из проективной плоскости того же порядка получается путём удаления одного блока и всех точек этого блока из проективной плоскости. Если выбрать другие блоки для удаления, можно получить неизоморфные аффинные плоскости.
Классические системы Штейнера
Системы троек Штейнера
Схема S(2,3,n) называется системой троек Штейнера, а его блоки называются тройками. Часто для систем троек Штейнера используется обозначение STS(n). Число троек, проходящих через точку, равно (n-1)/2, а потому общее число троек равно n(n−1)/6. Это показывает, что n должно иметь вид 6k+1 или 6k + 3 для некоторого k. Факт, что это условие для n достаточно для существования S(2,3,n), доказали Рей Чандра Бозе и Т. Сколем. Проективная плоскость порядка 2 (плоскость Фано) — это STS(7), а аффинная плоскость[en] порядка 3 — это STS(9).
С точностью до изоморфизма STS(7) и STS(9) единственны. Существует две схемы STS(13), 80 схем STS(15) и 11 084 874 829 схем STS(19).
Мы можем определить умножение на множестве S используя систему троек Штейнера, если положим aa = a для всех a из S и ab = c, если {a,b,c} — тройка Штейнера. Это делает S идемпотентной коммутативной квазигруппой. Квазигруппа имеет дополнительное свойство, что из ab = c следует bc = a и ca = b[комм. 1]. В обратную сторону, любая (конечная) квазигруппа с такими свойствами получается из системы троек Штейнера. Коммутативные идемпотентные квазигруппы, которые удовлетворяют этому дополнительному свойству, называются квазигруппами Штейнера].
Система четвёрок Штейнера
Схема S(3,4,n) называется системой четвёрок Штейнера. Необходимое и достаточное условие существования S(3,4,n) — n {\displaystyle \equiv } 2 или 4 (mod 6). Для этих систем часто используется обозначение SQS(n).
С точностью до изоморфизма SQS(8) и SQS(10) единственны, имеется 4 схемы SQS(14) и 1.054.163 схем SQS(16)[9].
Системы пятёрок Штейнера
Схема S(4,5,n) называется системой пятёрок Штейнера. Необходимое условие существования такой системы — n {\displaystyle \equiv } 3 или 5 (mod 6), что получается из соглашений, которые применимы ко всем классическим системам Штейнера. Дополнительное условие для общих систем, что n {\displaystyle \not \equiv } 4 (mod 5), получается из факта, что число блоков должно быть целым. Достаточные условия неизвестны.
Существует единственная система пятёрок Штейнера порядка 11, но нет систем порядка 15 или 17[10]. Известны системы с порядками 23, 35, 47, 71, 83, 107, 131, 167 и 243. Наименьший порядок, для которого существование неизвестно (на 2011 год) — 21.
Свойства
Из определения S(t, k, n) ясно, что 1Если система S(t, k, n) существует, выбор блоков, содержащих определённый элемент и удаление этого элемента, даёт производную систему S(t−1, k−1, n−1). Таким образом, существование S(t−1, k−1, n−1) является необходимым условием существования схемы S(t, k, n).
Число t-элементных подмножеств в S равно {\displaystyle {\tbinom {n}{t}}} , в то время как число t-элементных подмножеств в каждом блоке равно {\displaystyle {\tbinom {k}{t}}} . Поскольку любое t-элементное подмножество содержится ровно в одном блоке, мы получаем {\displaystyle {\tbinom {n}{t}}=b{\tbinom {k}{t}}},
где b — число блоков. Аналогичные рассуждения о t-элементных подмножествах, содержащих конкретный элемент, даёт нам
где r — число блоков, содержащих выбранный элемент. Из этих определений следует равенство {\displaystyle bk=rn} . Необходимым условием для существования схемы S(t, k, n) является целочисленность b и r. Как и для любой блок-схемы, неравенство Фишера {\displaystyle b\geq n} верно для систем Штейнера.
Если заданы параметры системы Штейнера S(t, k, n) и подмножество размера {\displaystyle t'\leq t} , содержащееся по меньшей мере в одном блоке, можно посчитать число блоков, пересекающих это подмножество с фиксированным числом элементов путём построения треугольника Паскаля[11]. В частности, число блоков, пересекающих фиксированный блок с любым числом элементов, не зависит от выбора блока.
Число блоков, содержащих любое i-элементное множество точек, равно:
для {\displaystyle i=0,1,\ldots ,t,}Можно показать, что если существует система Штейнера S(2, k, n), где k степень простого числа, большая 1, тогда n {\displaystyle \equiv } 1 или k (mod k(k−1)). В частности, система троек Штейнера S(2, 3, n) должна иметь n = 6m + 1 или 6m + 3. Как мы уже упоминали, это является единственным ограничением систем троек Штейнера, то есть для каждого натурального числа m системы S(2, 3, 6m + 1) и S(2, 3, 6m + 3) существуют.
История
Системы троек Штейнера первым определил В.С.Б. Вулхауз в 1844 в премиальном вопросе #1733 в журнале Lady's and Gentlemen's Diary. Поставленную задачу решил Томас Киркман. В 1850 Киркман поставил вариант задачи, получивший название «задача Киркмана о школьницах», в которой спрашивается о системе троек с дополнительным свойством (разрешимость). Не зная работы Киркмана, Якоб Штейнер[14] определил систему троек, и его работа получила бо́льшую известность, так что система получила его имя.
Группы Матьё
Некоторые примеры систем Штейнера тесно связаны с теорией групп. В частности, конечные простые группы, называемые группами Матьё, возникают как группы автоморфизмов систем Штейнера:
Группа Матьё M11 является группой автоморфизмов системы Штейнера S(4,5,11)
Группа Матьё M12 является группой автоморфизмов системы Штейнера S(5,6,12)
Группа Матьё M22 является единственной подгруппой с индексом 2 группы автоморфизмов системы Штейнера S(3,6,22)
Группа Матьё M23] является группой автоморфизмов системы Штейнера S(4,7,23)
Группа Матьё M24 является группой автоморфизмов системы Штейнера S(5,8,24).
Система Штейнера S(5, 6, 12)
Существует единственная система Штейнера S(5,6,12). Её группа автоморфизмов — группа Матьё M12, и в этом контексте группа обозначается как W12.
Построения
Имеются различные пути построения системы S(5,6,12).
Do'stlaringiz bilan baham: |
