Здравствуйте, vdimas, Вы писали:
K>>и любое определение fusible numbers открой — там этого нет.
V>Открыл — есть: V>http://googology.wikia.com/wiki/Fusible_number
V>По условию, данному по ссылке, нет смысла проводить идентичные манипуляции с разными фитилями, т.к. по условию они идентичны и сгорают полностью за одно и то же время.
(все, что ты открываешь, читаешь не вникая)
Formally, a real number xx is fusible if and only if x=0 or x=(a+b+1)/2, with a and b fusible numbers and |a−b|<1
Итак, если взять исходно x=0, то где же взять уникальные a и b из множества? С уникальным подходом множество fusible одноэлементно.
Здравствуйте, samius, Вы писали:
V>>По условию, данному по ссылке, нет смысла проводить идентичные манипуляции с разными фитилями, т.к. по условию они идентичны и сгорают полностью за одно и то же время. S>(все, что ты открываешь, читаешь не вникая)
Кто бы говорил. ))
S>
S>Formally, a real number xx is fusible if and only if x=0 or x=(a+b+1)/2, with a and b fusible numbers and |a−b|<1
S>Итак, если взять исходно x=0, то где же взять уникальные a и b из множества?
По условию по ссылке исходно ряд строился по другой формуле:
xi=xi-1+(1-xi-1)/2 = (xi-1+1)/2, где x0=0
И число 1 тоже входит в это ряд по-условию (время горения 1-го фитиля).
Так же по условию мы можем складывать и вычитать эти числа, чтобы получать из них новые.
Учитывая, что разница xi-xi-1=1/2i, можно получить любое число вида 1/2i, через сумму которых представить произвольное fusible number.
Итого:
Formally, a rational number x is fusible if and only if x=a*2-b, with a and b natural numbers.
Здравствуйте, vdimas, Вы писали:
V>Здравствуйте, samius, Вы писали:
V>>>По условию, данному по ссылке, нет смысла проводить идентичные манипуляции с разными фитилями, т.к. по условию они идентичны и сгорают полностью за одно и то же время. S>>(все, что ты открываешь, читаешь не вникая)
V>Кто бы говорил. ))
S>>
S>>Formally, a real number xx is fusible if and only if x=0 or x=(a+b+1)/2, with a and b fusible numbers and |a−b|<1
S>>Итак, если взять исходно x=0, то где же взять уникальные a и b из множества?
V>По условию по ссылке исходно ряд строился по другой формуле:
Нет по ссылке никакого ряда
V>xi=xi-1+(1-xi-1)/2 = (xi-1+1)/2, где x0=0 V>И число 1 тоже входит в это ряд по-условию (время горения 1-го фитиля).
о, выходит, "неточность" в определении nikov-а, т.е. требование уникальности p и q ты взял именно из своего ряда.
V>Итого, получается ряд: V>xi=0 V>x1=1/2 V>x2=3/4 V>x3=7/8 V>xi=1-1/2i V>xoo=1
V>Так же по условию мы можем складывать и вычитать эти числа, чтобы получать из них новые.
И даже вычитать? Т.е. -1/2 по-твоему тоже fusible.
V>Учитывая, что разница xi-xi-1=1/2i, можно получить любое число вида 1/2i, через сумму которых представить произвольное fusible number.
V>Итого: V>
V>Formally, a rational number x is fusible if and only if x=a*2-b, with a and b natural numbers.
И при каких же натуральных a и b выходит fusible -1/2, 5/8 ?
Здравствуйте, nikov, Вы писали:
N>Написать программу, которая принимает рациональное число и определяет, принадлежит ли оно множеству S.
Небольшой натурный эксперимент показал, что двоичные представления чисел там очень характерного вида
0.
0.1
0.11
0.111
.....
1.
1.0 (от 0 до 1 нуля вперемешку с единицами) 1
1.10 (от 0 до 2 нулей вперемешку с единицами) 1
1.(k-1 единиц) 0 (от 0 до k нулей вперемешку с единицами) 1
2.xxxxxxx — начиная с 2.0, встречаются все числа
Поэтому проверка выглядит достаточно простой:
x >= 2 — да, входит
x < 1 — x == 1-1/2**k
x in [1;2) — раскладываем в дробь, считаем количество L ведущих единиц (включая одну штуку до запятой) и количество значащих нулей Z; если Z<=L, то — да, входит.
Теперь осталось
— доказать, что после 2 встретятся все числа
— объяснить, почему между 1 и 2 именно такие дроби
Здравствуйте, vdimas, Вы писали:
V>Fusible numbers можно вычитать: V>А значит S — это множество всех двоичных дробей.
Нет. У нас подмножество множества fusible numbers. Сказано же: "минимальное множество"
Например, мы совершенно спокойно можем выкинуть диапазон (0;0.5).
Но тут мы, на самом деле, наталкиваемся на философский вопрос, что считать минимальным множеством.
Понятно, что все множества, удовлетворяющие условию "с нулём и замкнутое по слиянию" — счётны.
Достаточно просто взять любую функцию — f(x) = 0@x или f(x) = x@x (где @ — операция слияния, x@y = (x+y+1)/2)
и проитерировать счётное количество раз.
То есть, банально сравнивать мощности — бесполезно.
Но если мы напишем функцию F(M) = M U {x@y | x,y <- M}
и найдём его неподвижные точки Sfix = F(Sfix) = F*(Sseed)
то окажется, что между ними можно установить частичный порядок — что чьим подмножеством является. И очевидно, что если Sseed1 <= Sseed2, то Sfix1 <= Sfix2
Абсолютный минимум в этом, топологическом, смысле — это пустое множество, но мы его не засчитываем.
Самая маленькая затравка Sseed0 = {0} — по условию задачи.
Здравствуйте, Кодт, Вы писали:
V>>Fusible numbers можно вычитать: V>>А значит S — это множество всех двоичных дробей. К>Нет. У нас подмножество множества fusible numbers. Сказано же: "минимальное множество"
Э-э-э... ну тогда для любого представленного в двоичном виде числа за основу мн-ва можно взять слагаемые 2e-ni, где ni — номера ненулевых разрядов мантиссы (начиная со старших) и e=экспонента для плавающего представления или сдвиг точки для фиксированного. Затем дополнить это мн-во производными членами по формуле (a+b+1)/2 для всех пар слагаемых, у которых |a-b|<1. Проводить такое дополнение в цикле до тех пор, пока в мн-ве будут появляться новые члены. Оно?
Здравствуйте, vdimas, Вы писали:
V>Э-э-э... ну тогда для любого представленного в двоичном виде числа за основу мн-ва можно взять слагаемые 2e-ni, где ni — номера ненулевых разрядов мантиссы (начиная со старших) и e=экспонента для плавающего представления или сдвиг точки для фиксированного. Затем дополнить это мн-во производными членами по формуле (a+b+1)/2 для всех пар слагаемых, у которых |a-b|<1. Проводить такое дополнение в цикле до тех пор, пока в мн-ве будут появляться новые члены. Оно?
А не, это просто нахождение такого минимального мн-ва, которому принадлежит исходное число.
Но не выяснение принадлежности к минимальному мн-ву, получаемому от 0-ля.
Здравствуйте, vdimas, Вы писали:
V>Из условия. Иначе получается растущее вправо бесконечное мн-во, т.е. речи о его минимальности быть не может.
Минимальное множество не обязано быть ограниченным. Пусть себе растёт вправо, сколько ему вздумается. Главное, чтобы у него не было меньшего подмножества, которое тоже бы удовлетворяло условию задачи.
Здравствуйте, Eugene Sh, Вы писали:
V>>Из условия. Иначе получается растущее вправо бесконечное мн-во, т.е. речи о его минимальности быть не может. ES>Минимальное множество не обязано быть ограниченным. Пусть себе растёт вправо, сколько ему вздумается. Главное, чтобы у него не было меньшего подмножества, которое тоже бы удовлетворяло условию задачи.
Боюсь, в данном случае оба мн-ва совпадают, что минимальное, что полное.
Наверно имелось ввиду исключить всякие суммы таких fusible numbers из мн-ва? Но тут, похоже, любая их сумма может быть выведена как последовательность "обязательных" применений исходной формулы (p+q+1)/2.
Здравствуйте, Кодт, Вы писали:
К>Но тут мы, на самом деле, наталкиваемся на философский вопрос, что считать минимальным множеством. К>Понятно, что все множества, удовлетворяющие условию "с нулём и замкнутое по слиянию" — счётны. К>Достаточно просто взять любую функцию — f(x) = 0@x или f(x) = x@x (где @ — операция слияния, x@y = (x+y+1)/2) К>и проитерировать счётное количество раз.
А можно еще уточнить насчет "счетны"?
Например, порождаемый простейший ряд (для случая y=0) 1-2-n бесконечен, сходится в пределе к 1-му.
Или имелось ввиду конкретное двоичное представление числа с плавающей запятой в компьютере?
К>Но если мы напишем функцию F(M) = M U {x@y | x,y <- M} К>и найдём его неподвижные точки Sfix = F(Sfix) = F*(Sseed) К>то окажется, что между ними можно установить частичный порядок — что чьим подмножеством является. И очевидно, что если Sseed1 <= Sseed2, то Sfix1 <= Sfix2 К>Абсолютный минимум в этом, топологическом, смысле — это пустое множество, но мы его не засчитываем. К>Самая маленькая затравка Sseed0 = {0} — по условию задачи.
Как написал уже рядом, похоже, что любая сумма fusible numbers так же выражается через "обязательное" применение формулы (x+y+1)/2, вычисляющей "необходимый обязательный минимум". То бишь, похоже, что объединение вообще всех (произвольных) мн-в, удовлетворяющих условию, будет совпадать с минимальным или являться его подмножеством.
Здравствуйте, vdimas, Вы писали:
V>А можно еще уточнить насчет "счетны"? V>Например, порождаемый простейший ряд (для случая y=0) 1-2-n бесконечен, сходится в пределе к 1-му. V>Или имелось ввиду конкретное двоичное представление числа с плавающей запятой в компьютере?
Пределы здесь не при чём, речь идёт о мощностях.
Известно, что все счётные множества равномощны, то есть, каждому элементу одного такого множества можно взаимно однозначно сопоставить элемент другого.
Отсюда — парадоксы, например, о том, что множество чётных натуральных чисел эквивалентно множеству всех натуральных чисел. Хотя "на бытовом уровне" множество чётных "меньше" множества натуральных.
Поэтому топикстартер толкнул нас на тонкий лёд.
1. Все подходящие множества счётны. Потому что из нуля можно бесхитростно нарожать счётное количество чисел, которые должны принадлежать множеству.
2. Множество Q+ подходит и счётно.
3. Ну а раз мы нашли одно такое множество, зачем искать что-то ещё?
Вот чисто для доведения до абсурда: пусть операция слияния выглядит так: x@y = x+y+15.
Натуральные числа, кратные 15 — подходят.
Натуральные числа, кратные 3 или 5 — опять подходят.
Натуральные числа, кратные 15 или 17 — тоже подходят, хотя откуда взялось 17? Да с потолка.
Все натуральные числа — подходят.
Что из этого добра выберем в качестве "минимального"?
К>>Но если мы напишем функцию F(M) = M U {x@y | x,y <- M} К>>и найдём его неподвижные точки Sfix = F(Sfix) = F*(Sseed) К>>то окажется, что между ними можно установить частичный порядок — что чьим подмножеством является. И очевидно, что если Sseed1 <= Sseed2, то Sfix1 <= Sfix2 К>>Абсолютный минимум в этом, топологическом, смысле — это пустое множество, но мы его не засчитываем. К>>Самая маленькая затравка Sseed0 = {0} — по условию задачи.
V>Как написал уже рядом, похоже, что любая сумма fusible numbers так же выражается через "обязательное" применение формулы (x+y+1)/2, вычисляющей "необходимый обязательный минимум". То бишь, похоже, что объединение вообще всех (произвольных) мн-в, удовлетворяющих условию, будет совпадать с минимальным или являться его подмножеством.
Как это — "объединение всех" будет являться подмножеством минимального?!
Надмножеством — будет. Подмножеством максимального — будет. (А что возьмём за максимум?)
Здравствуйте, Кодт, Вы писали:
К>Отсюда — парадоксы, например, о том, что множество чётных натуральных чисел эквивалентно множеству всех натуральных чисел. Хотя "на бытовом уровне" множество чётных "меньше" множества натуральных.
Ну, это я еще помню. ))
Коэф при мощности не считается, считаются степени/логарифмы.
Например, мощность мн-ва попарных сочетаний всех натуральных чисел будет больше мощности мн-ва натуральных чисел, выражается как N2, где N-мощность мн-ва натуральных чисел.
К>Поэтому топикстартер толкнул нас на тонкий лёд. К>1. Все подходящие множества счётны.
Минимальное искомое мн-во прямо по условию имеет мощность N2.
Эту же мощность имеет мн-во рациональных чисел, т.е. представимых в виде простых дробей Na/Nb.
Поэтому и захотелось уточнить, почему счётно-то?
К>Вот чисто для доведения до абсурда: пусть операция слияния выглядит так: x@y = x+y+15. К>Натуральные числа, кратные 15 — подходят. К>Натуральные числа, кратные 3 или 5 — опять подходят. К>Натуральные числа, кратные 15 или 17 — тоже подходят, хотя откуда взялось 17? Да с потолка. К>Все натуральные числа — подходят. К>Что из этого добра выберем в качестве "минимального"?
Там в этих рядах, порождаемых исходной рекуррентной формулой, слияние "хорошо работает" только до значения <2, т.е. когда одно и то же число генерится разными способами. Поэтому, там счётно только мн-во чисел <2.
Здравствуйте, Кодт, Вы писали:
V>>Как написал уже рядом, похоже, что любая сумма fusible numbers так же выражается через "обязательное" применение формулы (x+y+1)/2, вычисляющей "необходимый обязательный минимум". То бишь, похоже, что объединение вообще всех (произвольных) мн-в, удовлетворяющих условию, будет совпадать с минимальным или являться его подмножеством. К>Как это — "объединение всех" будет являться подмножеством минимального?!
Попробую пояснить.
Есть некая ф-ия, которая постулирует наличие неких элементов в мн-ве, т.к. она говорит, что если p и q — элементы мн-ва и расстояние м/у ними <1, то x=F(p, q) — тоже элемент этого мн-ва. Еще дано, что 0 является элементом этого мн-ва, примем x0=0.
Итого, подставляя x0 в F, получим:
x0:1 = F(x0, x0).
Т.е. необходимо попарно применить F ко всем имеющимся и получаемым на каждом шаге xi и xj, расстояние м/у которыми меньше 1. Полученное мн-во я рядом назвал "обязательным минимумом", т.е. оно и есть искомое минимальное мн-во.
Рассуждаем далее. Представим, что можно взять произвольное число r, "насильно" включить его в мн-во и так же попарно по формуле нагенерить еще элементы такого мн-ва. Так вот, если r не является числом, полученным по исходной рекуррентной формуле, то мы нагенерим большее мн-во чем "минимальное обязательное", ОК.
Просто я утверждал, что любое число, представимое в виде суммы элементов xi из минимального мн-ва, тоже волшебным образом входит в это мн-во.
Например:
x0:1+x0:1=1/2+1/2=1.
и предел ряда x0:n, n->oo тоже равен 1.
Еще:
x0:1+x0:2=1/2+3/4=5/4.
предел ряда x1:n, n->oo тоже равен 5/4.
и т.д.
Далее.
Есть еще такие наблюдения:
Для любого числа вида 2-x0:n обязательно найдётся ряд из того самого минимального мн-ва, сходящийся к этому числу.
Например:
2 — 1/2 = 3/2 — есть такой ряд.
2 — 3/4 = 5/4 — есть такой ряд.
2 — 7/8 = 9/8 — есть такой ряд.
2 — x0:n, n->oo = x0:n, n->oo = 1
2 — 0 = x3:n, n->oo = 2
И это почему-то верно для любого числа r >= 2.
Т.е, любое число r >= 2, во-первых, представимо в виде суммы элементов x из минимального мн-ва 1/2 <= x <= 3/2, во вторых, тоже входит в это минимальное мн-во при рекуррентном его вычислении.
Итого, для чисел из диапазона 1/2..1 достаточно узнать на принадлежность ряду:
1/2, 3/4, 7/8, ..., 1-2-n
Что элементарно, если рациональное число представить в виде натуральной дроби.
А вот для чисел из диапазона 1..2 "достаточно" узнать на принадлежность одному из рядов:
1.
1/2+3/2-1/2, 1/2+3/2-3/4, 1/2+3/2-7/8...
1/2+5/4-1/2, 1/2+5/4-3/4, 1/2+5/4-7/8...
1/2+9/8-1/2, 1/2+9/8-3/4, 1/2+9/8-7/8...
...
2.
3/4+3/2-1/2, 3/4+3/2-3/4, 3/4+3/2-7/8...
3/4+5/4-1/2, 3/4+5/4-3/4, 3/4+5/4-7/8...
...
3.
7/8+3/2-1/2, 7/8+3/2-3/4, 7/8+3/2-7/8...
n.
...
Пока что есть наблюдение, что в диагоналях каждой n-й матрицы содержатся одинаковые числа, т.е. каждую из них можно заменить на любой её столбец или строку.
Итого, группа матриц вырождается в одну матрицу, принадлежность к которой надо найти...