Пусть 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 или нет из постановки задачи не следует.
Здравствуйте, 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 следует, что отрицательных чисел в нем нет!
Здравствуйте, kfmn, Вы писали:
K>Здравствуйте, kov_serg, Вы писали:
_>>Т.е любые числа представимые в виде суммы по степеням двойки принадлежат S
K>В условии было еще про минимальность S. А раз так, то точно не любые.
>>Пусть S — это наименьшее множество рациональных чисел, содержащее число 0 и удовлетворяющее условию: >>* Если числа p и q принадлежат S, и |p-q|<1, то число (p+q+1)/2 также принадлежит S.
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 следует, что отрицательных чисел в нем нет!
Здравствуйте, vdimas, Вы писали:
V>Из постановки задачи следует, что существуют такие ei, для которых выполняется система уравнений: V>(для только положительных значений, поэтому без модуля) V>ex=ey+2ez+1 V>...
Это уравнение, похоже, неверно. В условии сказано: "Если числа p и q принадлежат S, и |p-q|<1, то число (p+q+1)/2 также принадлежит S."
Т. е., должно быть ex = -ey + 2ez — 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 не является элементом мн-ва.
Здравствуйте, 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.