Дано натуральное число N. Придумать алгоритм нахождения минимально возможного набора чисел такого, чтобы с помощью суммирования каких-то элементов из этого набора, можно было получить все натуральные числа до N включительно.

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

Например, возьмём N = 7, тогда:

  1. 7 = 3 + 4
  2. 3 = 1 + 2
  3. 1 = 0 + 1

Ответ: (4, 2, 1)

Проверим:

  1. 1 = 1
  2. 2 = 2
  3. 3 = 2 + 1
  4. 4 = 4
  5. 5 = 4 + 1
  6. 6 = 4 + 2
  7. 7 = 4 + 2 + 1

Вроде всё нормально (надеюсь). Можно ли как-то обосновать (доказать) корректность работы этого алгоритма (или почему этот алгоритм некорректен) и то, что ответа ещё лучше получить нельзя (не знаю с чего доказательство начать).

задан 4 Окт '19 14:39

1

@Tiny Toon: тут двоичная система. Подразумевается, что слагаемые повторять нельзя. Ясно, что 1 должно быть, 2 тоже -- так как 1+1 нельзя брать. Число 3 выражается. Если нужно 4, то из 1+2 её не получить (мало), так что хотя бы одно новое число придётся брать. Тогда 4 и берём. Все числа до 1+2+4=2^3-1 представимы. Для 8 нужно брать новое слагаемое, и так далее.

Проверки в принципе лишние -- это всё из двоичного представления следует.

(4 Окт '19 20:24) falcao

@falcao. Спасибо, идею доказательства понял. Но почему слагаемые повторять нельзя? Это ведь никак не оговорено. Например, для N = 17 я думаю, что должен быть набор (9, 4, 2, 1, 1), но также возможен и набор (1, 2, 4, 8, 16). Проверку я провёл, чтобы просто показать, что за решение в задаче имеется в виду и почему оно именно такое. А вообще второй набор мне больше понравился :) с ним доказательство будет проще.

А как можно обосновать, что предложенный Вами способ гарантирует минимальность набора? Я не сомневаюсь, что в нём будет [ln(N)/ln(2)] + 1 чисел, но желательно обосновать почему это так.

(4 Окт '19 21:00) Tiny Toon

@falcao. Может можно рассмотреть какой-то простой случай, когда в наборе [ln(N)/ln(2)] чисел, убедиться, что их должно быть [ln(N)/ln(2)] + 1 и это будет обоснованием. N=7, пусть чисел в наборе 2, а не 3. Переберём все возможные случаи и убедимся, что 7 мы не достигним.

(4 Окт '19 21:09) Tiny Toon

@Tiny Toon: слово "набор" часто используют как синоним слова "множество", а там элементы не повторяются. Это две версии одной задачи. Формулировать желательно точнее.

Для N=1 нужно 1 число, меньше нельзя. Для N=2 или 1+2, или 1+1. Это 2 числа. Ясно, что одного числа мало -- так как оно либо не 1, либо не 2. Для N=3 мы уже знаем, что двух чисел хватает, а одного точно мало. При N=4, вплоть до 7, хватает трёх чисел. Достаточно доказать, что даже для N=4 мало двух чисел. Надо сослаться на то, что для N=2 два числа -- это 1+2 или 1+1, и их для 4 не хватает. Дальше должна работать индукция.

(4 Окт '19 22:09) falcao

@falcao. Спасибо!

(4 Окт '19 22:23) Tiny Toon
10|600 символов нужно символов осталось
1

Я подумал о том, что нетрудно дать совсем формальное доказательство. Если 2^k<=N < 2^{k+1}, то мы знаем, что k+1 слагаемого хватает, причём можно их не повторять. Напомним, что для этого достаточно взять набор из 1, 2, 4, ... , 2^k и использовать свойства двоичной системы.

Осталось доказать, что k слагаемых не хватит, чтобы все числа от 1 до 2^k были представимы, даже если разрешить повторения. Упорядочим их по неубыванию: x(1)<=...<=x(k). Предположим, что x(i)<=2^{i-1} для всех i. Тогда в сумме получится не больше 1+2+...+2^{k-1}=2^k-1, и число 2^k не представить.

Таким образом, существует i, для которого x(i) > 2^{i-1}. Выберем его минимальным. Это значит, что перед ним идут числа x(1), ... , x(i-1), не большие 1, 2, ... , 2^{i-2} соответственно. Тогда их сумма, как и выше, не больше 2^{i-1}-1, и число 2^{i-1} ими не представить. Нельзя представить его и с использованием других чисел, потому что каждое из них строго больше.

ссылка

отвечен 4 Окт '19 23:55

Спасибо ещё раз! На счёт формулировки этого задания: можно как угодно интерпретировать его смысл. Эту задачу я просто случайно нашёл и захотел сделать. Мне больше доказательство интересно было.

(5 Окт '19 8:26) Tiny Toon

@falcao. Здравствуйте! math.hashcode.ru/questions/182604/ самообразование-цветы-бабочки-и-тервер . Можете, пожалуйста, подсказать можно ли на эту задачу посмотреть как на приписывание каждой бабочке номера цветка, на который она села, тогда возможны случаи: 11111, 11112, 11113, 11121, ..., 33333? Количество всех таких чисел = количеству всех исходов: 3^5 (количество размещений с повторениями). А вот с нахождением количества благоприятных исходов в общем случае, несомненно, проще использовать формулу для подсчёта сюръекций.

(5 Окт '19 22:55) Tiny Toon
1

@Tiny Toon: там суть только в подсчёте числа сюръекций. Размещения с повторениями -- самая простая комбинаторная функция. То, что общее число исходов равно 3^5, очевидно по-всякому. Рассмотрение последовательностей номеров, разумеется, возможно. Но там ответ и так сразу виден. Я считаю, что удобнее всего оперировать с понятием функции (отображения), и помнить, что отображений из m в n имеется n^m. А такое отображение по определению есть последовательность из m членов со значениями в {1,2,...,n}. То есть это не какая-то хитрая кодировка, позволяющая лучше представить себе вещи, а определение.

(5 Окт '19 23:48) falcao

@falcao. ясно, мне тоже кажется, что удобнее найти количество исходов как количество всех отоборажений. Просто задача одна вспомнилась очень похожая (но давно была уже не помню её почти).

(6 Окт '19 0:06) Tiny Toon
10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×1,787
×273

задан
4 Окт '19 14:39

показан
233 раза

обновлен
6 Окт '19 0:06

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru