Здравствуйте, 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
Извини, но это уже не похоже на твою формулу...