Пусть S — это наименьшее множество рациональных чисел, содержащее число 0 и удовлетворяющее условию:
* Если числа p и q принадлежат S, и |p-q|<1, то число (p+q+1)/2 также принадлежит S.

Написать программу, которая принимает рациональное число и определяет, принадлежит ли оно множеству S.

Здравствуйте, nikov, Вы писали:

N>Пусть S — это наименьшее множество рациональных чисел, содержащее число 0 и удовлетворяющее условию:
N>* Если числа p и q принадлежат S, и |p-q|<1, то число (p+q+1)/2 также принадлежит S.

N>Написать программу, которая принимает рациональное число и определяет, принадлежит ли оно множеству S.

Могу начать рассуждение. Для любых положительных l/m, l < m пусть l/m принадлежит S. Тогда, так как 0 принадлежит S, k = (l/m+1)/2 тоже принадлежит S. Видно, что k=(l+m)/2m > 1/2. Далее, число k', принадлежащее S, может быть получено аналогично из 0 и k. Число k' тоже будет больше 1/2. Но тогда (k + k' +1)/2 тоже должно принадлежать S, чего быть не может, так как |(k + k' +1)/2| > 1. Поэтому никакое положительное рациональное l/m в S не попадает. Про отрицательные думать лень.

Про отрицательные: пусть l,m >0; m>l. Тогда если -l/m принадл. S и 0 принадл. S, то и (1-l/m)/2 тоже принадлежит S. Но (m-l)/2m >0 и приходим к рассуждениям из первого абзаца.

Тест на принадлежность к S получается просто сравнением с 0.

Здравствуйте, nikov, Вы писали:

N>Пусть S — это наименьшее множество рациональных чисел, содержащее число 0 и удовлетворяющее условию:
N>* Если числа p и q принадлежат S, и |p-q|<1, то число (p+q+1)/2 также принадлежит S.

Фигня какая-то:
Если число представимо по степеням двойки p=sum(ai*2^i, i=-inf..inf ) то оно пренадлежит S.
q=p+2e+1 где e=[0..1) = sum(ei*2^-i,i=1..inf)

r=(p+q+1)/2 = p+e => p'=p+k*e где k любое целое

Т.е любые числа представимые в виде суммы по степеням двойки принадлежат S

N>Написать программу, которая принимает рациональное число и определяет, принадлежит ли оно множеству S.
И тут засада т.к. разложение то бесконечное и можно с любой степенью точности разложить например 1/3,
но вот будет оно принадлежать S или нет из постановки задачи не следует.

Здравствуйте, nikov, Вы писали:

Я понимаю, что это on-topic — но всё таки интересно — зачем/откуда такой вопрос?

Здравствуйте, andyp, Вы писали:

N>>Пусть S — это наименьшее множество рациональных чисел, содержащее число 0 и удовлетворяющее условию:
N>>* Если числа p и q принадлежат S, и |p-q|<1, то число (p+q+1)/2 также принадлежит S.

A> Но тогда (k + k' +1)/2 тоже должно принадлежать S, чего быть не может, так как |(k + k' +1)/2| > 1.

Вот это я не понял. Почему этого не может быть? В условии же импликация только в одну сторону, а не эквивалентность ("тогда и только тогда").

Здравствуйте, nikov, Вы писали:

N>>>Пусть S — это наименьшее множество рациональных чисел, содержащее число 0 и удовлетворяющее условию:
N>>>* Если числа p и q принадлежат S, и |p-q|<1, то число (p+q+1)/2 также принадлежит S.

A>> Но тогда (k + k' +1)/2 тоже должно принадлежать S, чего быть не может, так как |(k + k' +1)/2| > 1.

N>Вот это я не понял. Почему этого не может быть? В условии же импликация только в одну сторону, а не эквивалентность ("тогда и только тогда").

Числа l/m, k, k', 0 принадлежат S, условие на модуль для парных разностей выполняется (все по модулю меньше 1) => число k_1 = (k+k'+1)/2 принадлежит S. Но |k1 — 0| > 1 и k1 мы включать не должны были => пришли к противоречию. Или я не так понимаю условие?

Здравствуйте, andyp, Вы писали:

A>Числа l/m, k, k', 0 принадлежат S, условие на модуль для парных разностей выполняется (все по модулю меньше 1) => число k_1 = (k+k'+1)/2 принадлежит S. Но |k1 — 0| > 1 и k1 мы включать не должны были => пришли к противоречию. Или я не так понимаю условие?

"Но |k1 — 0| > 1 и k1 мы включать не должны были" -- вот это ничем не обосновано. Похоже, что ты совершаешь логическую ошибку "denying the antecedent": из "если А, то B" ты выводишь "если не А, то не B".

Здравствуйте, Mystic Artifact, Вы писали:

MA>Я понимаю, что это on-topic — но всё таки интересно — зачем/откуда такой вопрос?

Множество S -- это так называемые fusible numbers, которые возникают из известной головоломки про точное отмеривание временных интервалов с помощью неравномерно сгорающих фитилей. Эти числа имеют неожиданную связь с ординалами в теории множеств, и ними связан ряд интересных математических теорем и недоказанных гипотез.

Здравствуйте, nikov, Вы писали:

N>"Но |k1 — 0| > 1 и k1 мы включать не должны были" -- вот это ничем не обосновано. Похоже, что ты совершаешь логическую ошибку "denying the antecedent": из "если А, то B" ты выводишь "если не А, то не B".

Кажется понял, что ты хочешь сказать: в множестве S могут существовать такие пары p,q, что |p-q|>=1, но они не могут порождать новые элементы множества. Тогда мои рассуждения неверны . Значит, все-таки неверно понял условие

Здравствуйте, kov_serg, Вы писали:

_>Т.е любые числа представимые в виде суммы по степеням двойки принадлежат S

В условии было еще про минимальность S. А раз так, то точно не любые.

Если p=q, то по условию p+0.5 тоже принадлежит S. Поэтому если принадлежит ноль, то и все целые и полуцелые.
Но вот дальше уже сложнее. Поскольку S принадлежат p=0 и q=1/2, то принадлежит и (p+q+1)/2 = 3/4, и все k/4 для натуральных k>=2. Но вот про 1/4 такого вроде сказать нельзя...
Аналогично, поскольку p=0 и q=3/4, то принадлежат и (p+q+1)/2 = 7/8, а поскольку p=1/2 и q=3/4, то и 9/8. Значит и все k/8 при k>=7. А вот 1/8, 3/8, 5/8 — вроде нет.
Ну и т.д. Вроде получается, что S принадлежат все числа вида k/2^n, где k>=A(n), но вид A(n) остается непонятен...


Т.е. индукция только вверх. И из минимальности S следует, что отрицательных чисел в нем нет!

Здравствуйте, kov_serg, Вы писали:

_>Фигня какая-то:
_>Если число представимо по степеням двойки p=sum(ai*2^i, i=-inf..inf ) то оно пренадлежит S.

Если оно при этом рациональное, то знаменатель будет степенью двойки после сокращения дроби.

Здравствуйте, kfmn, Вы писали:

K>Здравствуйте, kov_serg, Вы писали:

_>>Т.е любые числа представимые в виде суммы по степеням двойки принадлежат S

K>В условии было еще про минимальность S. А раз так, то точно не любые.

>>Пусть S — это наименьшее множество рациональных чисел, содержащее число 0 и удовлетворяющее условию:
>>* Если числа p и q принадлежат S, и |p-q|<1, то число (p+q+1)/2 также принадлежит S.

(1) q=p: p'=p+1/2, p=p'-1/2 => pk=p0 + k/2
q=p+1/2: p'=(2p+1/2+1)/2=p+3/4 => pk=p0 + k*(1/2+1/4)
q=p+1/2+1/4: p'=p+1/2+1/4+1/8 => pk=p0 + k*(1/2+1/4+1/8)
...
q=p+z: p'+1/2+z/2 => pk=p0+k*(1/2+z/2)
1/2+1/4+1/8 + ... + 2^-m = 1-2^-m
(2) p(k,m)=p0+k*(1-2^-m)
из (1) pk=p0+r
p'(k,m)=p0+k*(1-2^-m)-k=p0-k*2^-m

p'=p+a*2^-m

p'(0)=0+a*2^-m при любом целом a и сколь угодно большом m дают двоичное представление числа.


K>Если p=q, то по условию p+0.5 тоже принадлежит S. Поэтому если принадлежит ноль, то и все целые и полуцелые.
K>Но вот дальше уже сложнее. Поскольку S принадлежат p=0 и q=1/2, то принадлежит и (p+q+1)/2 = 3/4, и все k/4 для натуральных k>=2. Но вот про 1/4 такого вроде сказать нельзя...

Почему?

q=p+2*e-1 => 0<e<1, r=(p+q+1)/2 => r=p+e => p=r-e => pk = p + k*e где любое k-целое

K>Аналогично, поскольку p=0 и q=3/4, то принадлежат и (p+q+1)/2 = 7/8, а поскольку p=1/2 и q=3/4, то и 9/8. Значит и все k/8 при k>=7. А вот 1/8, 3/8, 5/8 — вроде нет.
K>Ну и т.д. Вроде получается, что S принадлежат все числа вида k/2^n, где k>=A(n), но вид A(n) остается непонятен...

K>Т.е. индукция только вверх. И из минимальности S следует, что отрицательных чисел в нем нет!

почему o_O ?

Здравствуйте, vdimas, Вы писали:

V>Из постановки задачи следует, что существуют такие e_i, для которых выполняется система уравнений:
V>(для только положительных значений, поэтому без модуля)
V>e_x=e_y+2e_z+1
V>...

Это уравнение, похоже, неверно. В условии сказано: "Если числа p и q принадлежат S, и |p-q|<1, то число (p+q+1)/2 также принадлежит S."
Т. е., должно быть e_x = -e_y + 2e_z — 1.

Здравствуйте, kov_serg, Вы писали:

K>>Т.е. индукция только вверх. И из минимальности S следует, что отрицательных чисел в нем нет!
_>почему o_O ?
Если в каком-то S есть отрицательные числа, то давайте построим S', который будет состоять только из неотрицательных чисел, входящих в S.
S' тоже будет удовлетворять условию задачи. И ещё оно будет меньше, чем S. А это значит, что S никак не может быть ответом.

Здравствуйте, Eugene Sh, Вы писали:

K>>>Т.е. индукция только вверх. И из минимальности S следует, что отрицательных чисел в нем нет!
_>>почему o_O ?
ES>Если в каком-то S есть отрицательные числа, то давайте построим S', который будет состоять только из неотрицательных чисел, входящих в S.
ES>S' тоже будет удовлетворять условию задачи. И ещё оно будет меньше, чем S. А это значит, что S никак не может быть ответом.

Если в каком-то S есть положительные числа, то давайте построим S', который будет состоять только из отрицательных чисел, далее по тексту. ))

На самом деле оба утверждения не верны, согласно условию.

Здравствуйте, vdimas, Вы писали:

V>Здравствуйте, Eugene Sh, Вы писали:

K>>>>Т.е. индукция только вверх. И из минимальности S следует, что отрицательных чисел в нем нет!
_>>>почему o_O ?
ES>>Если в каком-то S есть отрицательные числа, то давайте построим S', который будет состоять только из неотрицательных чисел, входящих в S.
ES>>S' тоже будет удовлетворять условию задачи. И ещё оно будет меньше, чем S. А это значит, что S никак не может быть ответом.

V>Если в каком-то S есть положительные числа, то давайте построим S', который будет состоять только из отрицательных чисел, далее по тексту. ))

Если какое-то p число принадлежит S, то и все числа вида p+k/2 — тоже принадлежат для любого натурального k. Поэтому только отрицательными ограничиться не получится. К тому же по условию ноль содержится в S.
А вот только неотрицательными — вполне. Потому что (p+q+1)/2 больше чем p и q, и индукция вправо по оси возможна, а вот влево — нет.

Здравствуйте, kfmn, Вы писали:

V>>Если в каком-то S есть положительные числа, то давайте построим S', который будет состоять только из отрицательных чисел, далее по тексту.
K>Если какое-то p число принадлежит S, то и все числа вида p+k/2 — тоже принадлежат для любого натурального k.

Там неточность условия в том, что в формуле (p+q+1)/2 должно было оговариваться, что p и q — это уникальные элементы множества.
Иначе задача не имеет решения.


K>Поэтому только отрицательными ограничиться не получится.

Я не ограничивался отрицательными специально, это получилось в результате вычислений.


K>К тому же по условию ноль содержится в S.

При условии уникальности p и q — да.
Иначе получалось противоречие сходу, т.к. 1/2 не является элементом мн-ва.


K>А вот только неотрицательными — вполне. Потому что (p+q+1)/2 больше чем p и q,

Это только для положительных p и q верно.
Для отрицательных — зависит от (p+q+1).
Например, чтобы получить элемент мн-ва 0, (p+q+1) должно быть равно 0-лю, т.е. отрицательные числа должны входить в мн-во.


K>и индукция вправо по оси возможна, а вот влево — нет.

Следовательно, дальнейшие рассуждения неверные.

Здравствуйте, vdimas, Вы писали:

V>Там неточность условия в том, что в формуле (p+q+1)/2 должно было оговариваться, что p и q — это уникальные элементы множества.
Уникальные, значит различные?
nikov про это в условии не писал, и любое определение fusible numbers открой — там этого нет.

V>Иначе задача не имеет решения.
Объясни, почему.

K>>К тому же по условию ноль содержится в S.

V>При условии уникальности p и q — да.
V>Иначе получалось противоречие сходу, т.к. 1/2 не является элементом мн-ва.

Откуда это?

Здравствуйте, kfmn, Вы писали:

V>>Иначе получалось противоречие сходу, т.к. 1/2 не является элементом мн-ва.
K>Откуда это?

Из условия. Иначе получается растущее вправо бесконечное мн-во, т.е. речи о его минимальности быть не может.
Т.е., мн-во fusible numbers бесконечно.

Тогда принадлежность к нему определяется элементарно (ответил сразу же):

Если оно при этом рациональное, то знаменатель будет степенью двойки после сокращения дроби.

Итого, решение:
UPD (сравнить с 0-лем):

bool isFusible(uint numerator, uint denominator) {
    assert(denominator);
    if(!numerator) return true;
    uint a = numerator, b = denominator;
    while(a!=b) if(a>b) a-=b; else b-=a;
    denominator/=a;
    return !(denominator&(denominator-1));
}

Здравствуйте, nikov, Вы писали:

N>Пусть S — это наименьшее множество рациональных чисел, содержащее число 0 и удовлетворяющее условию:
N>* Если числа p и q принадлежат S, и |p-q|<1, то число (p+q+1)/2 также принадлежит S.

N>Написать программу, которая принимает рациональное число и определяет, принадлежит ли оно множеству S.

Понятно, что S — некое подмножество конечных двоичных дробей. Так что сразу отвергнем всё то, что разлагается в бесконечные дроби.

Индукционная формула выглядит так:
r = p + (q-p)/2 + 1/2
где 0 <= q-p < 1
С каждой итерацией разрядность увеличивается на 1.
С каждой итерацией получается бОльшее число.

Таким образом, мы можем выполнить NP-полную, но, всё-таки, конечную, проверку.

Берём проверяемое число r, находим его разрядность. Пусть младший разряд назовётся eps.
Получаем уравнение r-1/2 = p+d, 0<=d<1
Для всех d в [0;1) с шагом eps получаем пары p,q = r-1/2-d, r-1/2
Для каждого числа из пары рекурсивно выполняем проверку вхождения в S.

Здравствуйте, 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 из множества?

По условию по ссылке исходно ряд строился по другой формуле:
x_i=x_i-1+(1-x_i-1)/2 = (x_i-1+1)/2, где x₀=0
И число 1 тоже входит в это ряд по-условию (время горения 1-го фитиля).

Итого, получается ряд:
x_i=0
x₁=1/2
x₂=3/4
x₃=7/8
x_i=1-1/2ⁱ
x_oo=1

Так же по условию мы можем складывать и вычитать эти числа, чтобы получать из них новые.
Учитывая, что разница x_i-x_i-1=1/2ⁱ, можно получить любое число вида 1/2ⁱ, через сумму которых представить произвольное fusible number.

Итого:

Formally, a rational number x is fusible if and only if x=a*2^-b, with a and b natural numbers.

Здравствуйте, Кодт, Вы писали:

К>Понятно, что S — некое подмножество конечных двоичных дробей.

Fusible numbers можно вычитать:

You are allowed to light one or more unlit ends of any fuse, but only at time \(t = 0\) or when a fuse burns out completely.

Т.е., догорел один фитиль, подожгли другой или отсчитали время м/у сгоранием двух фетилей.
Итого, можно получить произвольное число 2^-n.

А значит S — это множество всех двоичных дробей.

Т.е., любое целое число или число с плавающей точкой, представимое в двоичном виде, — оно заведомо fusible. ))

Поэтому, программа может быть такой (для представления рационального числа в виде дроби):
http://www.rsdn.org/forum/etude/6746954.1

Или такой:

bool isFusible(float a) { return a>=0; }
bool isFusible(double a) { return a>=0; }
bool isFusible(int a) { return a>=0; }
bool isFusible(long a) { return a>=0; }
bool isFusible(unsigned a) { return true; }
bool isFusible(unsigned long a) { return true; }

Здравствуйте, 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>x_i=x_i-1+(1-x_i-1)/2 = (x_i-1+1)/2, где x₀=0
V>И число 1 тоже входит в это ряд по-условию (время горения 1-го фитиля).
о, выходит, "неточность" в определении nikov-а, т.е. требование уникальности p и q ты взял именно из своего ряда.

V>Итого, получается ряд:
V>x_i=0
V>x₁=1/2
V>x₂=3/4
V>x₃=7/8
V>x_i=1-1/2ⁱ
V>x_oo=1

V>Так же по условию мы можем складывать и вычитать эти числа, чтобы получать из них новые.
И даже вычитать? Т.е. -1/2 по-твоему тоже fusible.

V>Учитывая, что разница x_i-x_i-1=1/2ⁱ, можно получить любое число вида 1/2ⁱ, через сумму которых представить произвольное 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}
и найдём его неподвижные точки S_fix = F(S_fix) = F^*(S_seed)
то окажется, что между ними можно установить частичный порядок — что чьим подмножеством является. И очевидно, что если S_seed1 <= S_seed2, то S_fix1 <= S_fix2
Абсолютный минимум в этом, топологическом, смысле — это пустое множество, но мы его не засчитываем.
Самая маленькая затравка S_seed0 = {0} — по условию задачи.

Здравствуйте, Кодт, Вы писали:

V>>Fusible numbers можно вычитать:
V>>А значит S — это множество всех двоичных дробей.
К>Нет. У нас подмножество множества fusible numbers. Сказано же: "минимальное множество"

Э-э-э... ну тогда для любого представленного в двоичном виде числа за основу мн-ва можно взять слагаемые 2^e-n_i, где n_i — номера ненулевых разрядов мантиссы (начиная со старших) и e=экспонента для плавающего представления или сдвиг точки для фиксированного. Затем дополнить это мн-во производными членами по формуле (a+b+1)/2 для всех пар слагаемых, у которых |a-b|<1. Проводить такое дополнение в цикле до тех пор, пока в мн-ве будут появляться новые члены. Оно?

Здравствуйте, samius, Вы писали:

V>>По условию по ссылке исходно ряд строился по другой формуле:
S>Нет по ссылке никакого ряда

Плохо читал, значит.
Обрати внимание на то, как получили 45 секунд.


V>>Так же по условию мы можем складывать и вычитать эти числа, чтобы получать из них новые.
S>И даже вычитать?

Да. Зажги две разных цепочки "фитильных событий", и замерь время м/у окончанием их.


S>Т.е. -1/2 по-твоему тоже fusible.

Только если "отрезок времени" может быть отрицательным. ))



V>>

V>>Formally, a rational number x is fusible if and only if x=a*2^-b, with a and b natural numbers.

S>И при каких же натуральных a и b выходит fusible -1/2, 5/8?

5/8 => a=5, b=3

Здравствуйте, vdimas, Вы писали:

V>Э-э-э... ну тогда для любого представленного в двоичном виде числа за основу мн-ва можно взять слагаемые 2^e-n_i, где n_i — номера ненулевых разрядов мантиссы (начиная со старших) и e=экспонента для плавающего представления или сдвиг точки для фиксированного. Затем дополнить это мн-во производными членами по формуле (a+b+1)/2 для всех пар слагаемых, у которых |a-b|<1. Проводить такое дополнение в цикле до тех пор, пока в мн-ве будут появляться новые члены. Оно?

А не, это просто нахождение такого минимального мн-ва, которому принадлежит исходное число.
Но не выяснение принадлежности к минимальному мн-ву, получаемому от 0-ля.

Здравствуйте, samius, Вы писали:

V>>Так же по условию мы можем складывать и вычитать эти числа, чтобы получать из них новые.
S>И даже вычитать?

По той ссылке недостаточно было сказано.
Нашел первоисточник, там написано:

The
 interval 
starts 
when 
first 
fuse 
is 
lit, 
ends 
when 
last 
fuse 
goes 
out.

Т.е. вычитать нельзя.

Здравствуйте, vdimas, Вы писали:

V>Из условия. Иначе получается растущее вправо бесконечное мн-во, т.е. речи о его минимальности быть не может.
Минимальное множество не обязано быть ограниченным. Пусть себе растёт вправо, сколько ему вздумается. Главное, чтобы у него не было меньшего подмножества, которое тоже бы удовлетворяло условию задачи.

Здравствуйте, Кодт, Вы писали:

К>2.xxxxxxx — начиная с 2.0, встречаются все числа
Совсем все? Или можно взять только числа конечной длины?

Здравствуйте, 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}
К>и найдём его неподвижные точки S_fix = F(S_fix) = F^*(S_seed)
К>то окажется, что между ними можно установить частичный порядок — что чьим подмножеством является. И очевидно, что если S_seed1 <= S_seed2, то S_fix1 <= S_fix2
К>Абсолютный минимум в этом, топологическом, смысле — это пустое множество, но мы его не засчитываем.
К>Самая маленькая затравка S_seed0 = {0} — по условию задачи.

Как написал уже рядом, похоже, что любая сумма fusible numbers так же выражается через "обязательное" применение формулы (x+y+1)/2, вычисляющей "необходимый обязательный минимум". То бишь, похоже, что объединение вообще всех (произвольных) мн-в, удовлетворяющих условию, будет совпадать с минимальным или являться его подмножеством.

Здравствуйте, vdimas, Вы писали:

V>А можно еще уточнить насчет "счетны"?
Счётное множество

Здравствуйте, Eugene Sh, Вы писали:

К>>2.xxxxxxx — начиная с 2.0, встречаются все числа
ES>Совсем все? Или можно взять только числа конечной длины?

Да, я имел в виду все конечные дроби. С самого начала же сказал, что из {0} за конечное число шагов получаются только конечноразрядные числа.

Здравствуйте, 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}
К>>и найдём его неподвижные точки S_fix = F(S_fix) = F^*(S_seed)
К>>то окажется, что между ними можно установить частичный порядок — что чьим подмножеством является. И очевидно, что если S_seed1 <= S_seed2, то S_fix1 <= S_fix2
К>>Абсолютный минимум в этом, топологическом, смысле — это пустое множество, но мы его не засчитываем.
К>>Самая маленькая затравка S_seed0 = {0} — по условию задачи.

V>Как написал уже рядом, похоже, что любая сумма fusible numbers так же выражается через "обязательное" применение формулы (x+y+1)/2, вычисляющей "необходимый обязательный минимум". То бишь, похоже, что объединение вообще всех (произвольных) мн-в, удовлетворяющих условию, будет совпадать с минимальным или являться его подмножеством.

Как это — "объединение всех" будет являться подмножеством минимального?!
Надмножеством — будет. Подмножеством максимального — будет. (А что возьмём за максимум?)

Здравствуйте, Eugene Sh, Вы писали:

V>>А можно еще уточнить насчет "счетны"?
ES>Счётное множество

Ну тогда искомое мн-во не счетно, т.к. оно по-определению имеет мощность N², где N-мощность мн-ва натуральных чисел.

Здравствуйте, Кодт, Вы писали:

К>Отсюда — парадоксы, например, о том, что множество чётных натуральных чисел эквивалентно множеству всех натуральных чисел. Хотя "на бытовом уровне" множество чётных "меньше" множества натуральных.

Ну, это я еще помню. ))
Коэф при мощности не считается, считаются степени/логарифмы.

Например, мощность мн-ва попарных сочетаний всех натуральных чисел будет больше мощности мн-ва натуральных чисел, выражается как N², где N-мощность мн-ва натуральных чисел.


К>Поэтому топикстартер толкнул нас на тонкий лёд.
К>1. Все подходящие множества счётны.

Минимальное искомое мн-во прямо по условию имеет мощность N².
Эту же мощность имеет мн-во рациональных чисел, т.е. представимых в виде простых дробей N_a/N_b.

Поэтому и захотелось уточнить, почему счётно-то?


К>Вот чисто для доведения до абсурда: пусть операция слияния выглядит так: 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 является элементом этого мн-ва, примем x₀=0.

Итого, подставляя x₀ в F, получим:
x_0:1 = F(x₀, x₀).

Далее:
x_0:2 = F(x₀, x_0:1).
x_0:3 = F(x₀, x_0:2).
x_1:2 = F(x_0:1, x_0:1).
x_1:3 = F(x_0:1, x_0:2).
и т.д.

Т.е. необходимо попарно применить F ко всем имеющимся и получаемым на каждом шаге x_i и x_j, расстояние м/у которыми меньше 1. Полученное мн-во я рядом назвал "обязательным минимумом", т.е. оно и есть искомое минимальное мн-во.

Рассуждаем далее. Представим, что можно взять произвольное число r, "насильно" включить его в мн-во и так же попарно по формуле нагенерить еще элементы такого мн-ва. Так вот, если r не является числом, полученным по исходной рекуррентной формуле, то мы нагенерим большее мн-во чем "минимальное обязательное", ОК.

Просто я утверждал, что любое число, представимое в виде суммы элементов x_i из минимального мн-ва, тоже волшебным образом входит в это мн-во.
Например:
x_0:1+x_0:1=1/2+1/2=1.
и предел ряда x_0:n, n->oo тоже равен 1.

Еще:
x_0:1+x_0:2=1/2+3/4=5/4.
предел ряда x_1:n, n->oo тоже равен 5/4.
и т.д.

Далее.
Есть еще такие наблюдения:
Для любого числа вида 2-x_0:n обязательно найдётся ряд из того самого минимального мн-ва, сходящийся к этому числу.
Например:
2 — 1/2 = 3/2 — есть такой ряд.
2 — 3/4 = 5/4 — есть такой ряд.
2 — 7/8 = 9/8 — есть такой ряд.
2 — x_0:n, n->oo = x_0:n, n->oo = 1
2 — 0 = x_3: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-й матрицы содержатся одинаковые числа, т.е. каждую из них можно заменить на любой её столбец или строку.
Итого, группа матриц вырождается в одну матрицу, принадлежность к которой надо найти...

====
Интересно, а у ТС есть своё решение? ))

Здравствуйте, vdimas, Вы писали:

V>Ну, это я еще помню. ))
V>Коэф при мощности не считается, считаются степени/логарифмы.

V>Например, мощность мн-ва попарных сочетаний всех натуральных чисел будет больше мощности мн-ва натуральных чисел, выражается как N², где N-мощность мн-ва натуральных чисел.

Что-то ты не то помнишь.
||N^2|| = ||N||

Способ биекции:
— для любого натурального числа пишем его в позиционной (двоичной, десятичной, какой угодно) системе, и разбираем на две строки — одну из чётных разрядов, другую из нечётных.
— для любых двух натуральных чисел пишем их в той же самой системе, дополняем ведущими нулями до одной длины, и собираем в одну строку, чередуя чётные разряды из одного числа, нечётные из другого.

Подобным же образом доказывается равномощность целых и рациональных чисел: каждое рациональное число представляют несократимой парой числитель/знаменатель, строят инъекцию на натуральные числа (инъекцию — потому что множество несократимых числителей/знаменателей — это подмножество пар произвольных чисел). Затем строят инъекцию натуральных чисел на рациональные (тривиально: всякое натуральное число есть рациональное).
||N|| <= ||Q|| <= ||N||

К>>Поэтому топикстартер толкнул нас на тонкий лёд.
К>>1. Все подходящие множества счётны.

V>Минимальное искомое мн-во прямо по условию имеет мощность N².
V>Эту же мощность имеет мн-во рациональных чисел, т.е. представимых в виде простых дробей N_a/N_b.

V>Поэтому и захотелось уточнить, почему счётно-то?

Ну, по определению.
Строим последовательность: a₁ = 0, a_k+1 = 0@a_k чисел, которые определённо принадлежат нашему множеству.
Таким образом, каждому натуральному числу соответствует какой-то элемент множества. То есть, это множество не менее чем счётно.
(На самом деле, операция @ замечательно может быть определена и на вещественных числах, если мы позволим себе перегрузку по типу для 1, 2, (+) и (/)).

Почему множество, полученное из затравки {0}, (не более чем) счётно: тут всё очень просто. Так как операция определена над рациональными числами, то иррациональным числам там взяться просто неоткуда.
А множество рациональных чисел счётно.

V>Там в этих рядах, порождаемых исходной рекуррентной формулой, слияние "хорошо работает" только до значения <2, т.е. когда одно и то же число генерится разными способами. Поэтому, там счётно только мн-во чисел <2.

Это один из детских парадоксов теории множеств
Рациональные числа плотны. Но континуум — "плотнее"!

Здравствуйте, vdimas, Вы писали:

V>Здравствуйте, samius, Вы писали:

V>>>По условию по ссылке исходно ряд строился по другой формуле:
S>>Нет по ссылке никакого ряда

V>Плохо читал, значит.
V>Обрати внимание на то, как получили 45 секунд.

Обратил. Двумя шнурками. Ряда не заметил.


V>>>Так же по условию мы можем складывать и вычитать эти числа, чтобы получать из них новые.
S>>И даже вычитать?

V>Да. Зажги две разных цепочки "фитильных событий", и замерь время м/у окончанием их.


S>>Т.е. -1/2 по-твоему тоже fusible.

V>Только если "отрезок времени" может быть отрицательным. ))
Это следует из твоего тезиса о возможности вычитания для получения новых.


V>>>

V>>>Formally, a rational number x is fusible if and only if x=a*2^-b, with a and b natural numbers.

S>>И при каких же натуральных a и b выходит fusible -1/2, 5/8?

V>5/8 => a=5, b=3

а 1/4 при a=1 и b=2 у тебя fusible?

Так то с уникальностью p и q?

Здравствуйте, vdimas, Вы писали:

V>Здравствуйте, samius, Вы писали:

S>>И даже вычитать?

V>По той ссылке недостаточно было сказано.
V>Нашел первоисточник, там написано:
V>

V>The
 interval 
starts 
when 
first 
fuse 
is 
lit, 
ends 
when 
last 
fuse 
goes 
out.

V>Т.е. вычитать нельзя.

значит, и утверждение

Formally, a rational number x is fusible if and only if x=a*2^-b, with a and b natural numbers.

ложно

Здравствуйте, kfmn, Вы писали:

K>Здравствуйте, kov_serg, Вы писали:

_>>Т.е любые числа представимые в виде суммы по степеням двойки принадлежат S

K>В условии было еще про минимальность S. А раз так, то точно не любые.

Что такое минимальность? По мощности? Множество по любому бесконечное, т.к. если p и q принадлежат S, то и p+q тоже принадлежит. Для всех p и q больше или равных 1. Так как импликация в этом случае будет выполняться, ибо |p-q| < 1 === false

Здравствуйте, sr_dev, Вы писали:

_>Что такое минимальность? По мощности? Множество по любому бесконечное, т.к. если p и q принадлежат S, то и p+q тоже принадлежит. Для всех p и q больше или равных 1. Так как импликация в этом случае будет выполняться, ибо |p-q| < 1 === false

Я уже выступал по этому поводу.
Раз по мощности мы имеем дело с, как минимум, счётными множествами (континуум вещественных чисел тоже подходит, но мы его, так и быть, отвергнем), — то остаётся минимум топологической сортировки для частичного порядка "является подмножеством".
И такой минимум есть, и им является множество S, порождённое из {0}.
Потому что если мы возьмём любое другое множество, включающее в себя 0 (а это — условие задачи), то оно будет обязано включить в себя все элементы S.

Здравствуйте, sr_dev, Вы писали:

_>Что такое минимальность?

Минимальность множества S означает, что оно является подмножеством каждого множества, удовлетворящего указанным условиям.
Или, другими словами, является пересечением всех множеств рациональных чисел, удовлетворящих указанным условиям.

Здравствуйте, nikov, Вы писали:

N>Здравствуйте, sr_dev, Вы писали:

_>>Что такое минимальность?

N>Минимальность множества S означает, что оно является подмножеством каждого множества, удовлетворящего указанным условиям.
N>Или, другими словами, является пересечением всех множеств рациональных чисел, удовлетворящих указанным условиям.

Я ошибся насчет того что множество по любому бесконечное.

Наименьшее по мощности множество S это {0, 1}
импликация для него выполняется, ибо |0+1| < 1 === false
Меньше двух элементов уже нельзя.

Может задачу более приближенно к практике как то сформулировать?

Здравствуйте, sr_dev, Вы писали:

_>Здравствуйте, nikov, Вы писали:

N>>Здравствуйте, sr_dev, Вы писали:

_>>>Что такое минимальность?

N>>Минимальность множества S означает, что оно является подмножеством каждого множества, удовлетворящего указанным условиям.
N>>Или, другими словами, является пересечением всех множеств рациональных чисел, удовлетворящих указанным условиям.

_>Я ошибся насчет того что множество по любому бесконечное.

_>Наименьшее по мощности множество S это {0, 1}
_>импликация для него выполняется, ибо |0+1| < 1 === false
_>Меньше двух элементов уже нельзя.

Неверное заключение. Пусть S это {0, 1}. Тогда 0 и 0 принадлежит S.
Тогда |0-0| == 0 < 1. Значит 1/2 принадлежит S. И так далее.

Здравствуйте, vdimas, Вы писали:

V>Там неточность условия в том, что в формуле (p+q+1)/2 должно было оговариваться, что p и q — это уникальные элементы множества.
V>Иначе задача не имеет решения.

Если потребовать, что бы p не равнялось q, то множество из одного 0 и будет минимальным...

Здравствуйте, Кодт, Вы писали:

К>Поэтому топикстартер толкнул нас на тонкий лёд.

Возможно имеется в виду такое множество, которое является подмножеством любого описанного в задаче.

Например множества из нуля из нуля и 1/2, а так же {0, 1/2, 3/4} обладает таким свойством.
Возможно можно найти объединение всех таких множеств.

Например, если у нас есть какое-то счётное {Xi}, то его можно пополнить 0 и всеми возможными {Xj + Xi + 1}/2, потом опять пополнить и так счётное число раз.
Ясно, что если есть {Yi}, то тоже можно пополнить. Пусть такая операция называется А({Xi}).
Очевидно, что A({Xi}) + A({Yi}) -- подмножество A({Xi} + {Yi}).
А A({0}) -- подмножество любого A({Xi})

Я так понимаю, что именно вот A({0}) нам и надо найти, вернее научиться проверять что заданное число лежит в таком A({0})...

Здравствуйте, Erop, Вы писали:

E>Возможно имеется в виду такое множество, которое является подмножеством любого описанного в задаче.
E>Я так понимаю, что именно вот A({0}) нам и надо найти, вернее научиться проверять что заданное число лежит в таком A({0})...

Ну, мне кажется, что я нашёл такое множество и способ проверки.
Но как это доказать, — ещё не придумал.

Здравствуйте, Erop, Вы писали:

V>>Там неточность условия в том, что в формуле (p+q+1)/2 должно было оговариваться, что p и q — это уникальные элементы множества.
V>>Иначе задача не имеет решения.
E>Если потребовать, что бы p не равнялось q, то множество из одного 0 и будет минимальным...

В противном случае "минимальным" будет всё мн-во, порождаемое этой формулой рекуррентно.

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

Вторая часть док-ва проста, по аналогии с тем, что накопительная сумма ряда 1/2+1/4+1/8... сколь угодно близко приближается к 1.
Т.е. это ряд вида:
(a) 1-2^-n, n->oo, где члены этого ряда входят в искомое мн-во.

А у нас в диапазоне от 1/2 до 3/2 есть сетка рядов такого вида:
(б) 2-x_i-2^-n, n->oo, n>0, где x_i — это любой элемент из ряда (а).

Здравствуйте, vdimas, Вы писали:

V>Вторая часть док-ва проста, по аналогии с тем, что накопительная сумма ряда 1/2+1/4+1/8... сколь угодно близко приближается к 1.
V>Т.е. это ряд вида:
V>(a) 1-2^-n, n->oo, где члены этого ряда входят в искомое мн-во.

V>А у нас в диапазоне от 1/2 до 3/2 есть сетка рядов такого вида:
V>(б) 2-x_i-2^-n, n->oo, n>0, где x_i — это любой элемент из ряда (а).

Первый набор (1/2; 1)
x(i) = 1-2^-i

Второй набор, по твоей версии
y(i,j) = 2-x(i)-2^-j = 1+2^-i-2^-j

Смотрим, что получается из двух чисел первого набора:
f(x(a),x(b)) = (1 + 1-2^-a + 1-2^-b)/2 = 1+2^-a-1+2^-b-1+2^-1
Извини, но это уже не похоже на твою формулу...