Сломанная линейка

[fortpost]

У Васи есть линейка, у которой обломился конец, так что ее длина стала равной 33 см. Большинство делений на линейке стерлось, так что разобрать можно только 8 из них. Тем не менее с помощью линейки можно измерить любое целое число сантиметров от 1 до 33. Где расположены сохранившиеся деления? Разумеется, нужное измерение следует сделать, приложив линейку один раз.

[moonlight]

Показать скрытый текст

связано с числами Фибоначчи

Нет, вру.
Это нужно понимать так что 8 делений кроме 0 и 33 - всего 10?
Тогда решений много.

[fortpost]

Показать скрытый текст

связано с числами Фибоначчи

Нет, вру.
Это нужно понимать так что 8 делений кроме 0 и 33 - всего 10?
Тогда решений много.

Ага, где-то около 16. Приведите хотя бы пару. А для линейки в 36 см можете?

[moonlight]

всего 120 (60 симметричных пар).
Показать скрытый текст

0  1  2  3  4  10  16  22  28  33
0  2  5  6  13  15  27  29  32  33

[fortpost]

всего 120 (60 симметричных пар).
Показать скрытый текст

0  1  2  3  4  10  16  22  28  33
0  2  5  6  13  15  27  29  32  33

[iPhonograph]

А для линейки в 36 см можете?

жадный алгоритм нашёл моментально
0, 1, 3, 6, 13, 20, 27, 31, 35, 36

[семеныч]

ещё у Васи есть треугольная линейка со сторонами 19  18  13 см
нужно нанести наименьшее количество делений чтобы можно было измерить любое целое число сантиметров от 1 до 19.


//текст доступен после регистрации//

[Ispanka5]

))))

[семеныч]

А для линейки в 36 см можете?

жадный алгоритм нашёл моментально
0, 1, 3, 6, 13, 20, 27, 31, 35, 36

два раза отрезок равный единице?


наверное можно поменьше?

для 34

M(1,7)=34 -- Exactly 1 distinct example exists.
0    1    4    9    15    22    32    34




//текст доступен после регистрации//

[семеныч]

ещё у Васи есть треугольная линейка со сторонами 19  18  13 см
нужно нанести наименьшее количество делений чтобы можно было измерить любое целое число сантиметров от 1 до 19.


//текст доступен после регистрации//

слабо??

[iPhonograph]

семеныч, не умничай - непрямоугольных треугольных линеек не бывает

[iPhonograph]

на той странице с ответами, куда ты дал ссылку, есть примеры с 2 дополнительными точками на каждой стороне, т.е., по 6 измеримых расстояний на каждой стороне, итого 18 расстояний на весь треугольник, значит, какого-то одного не хватит - нужно получить все от 1 до 19.

[семеныч]

та да

8-9-1
3-12-4
6-5-2

нет - 14



значит минимальное - 7(21) делений

[iPhonograph]

думаю, меньше 7

[iPhonograph]

то, что 4 делений не хватит, можно доказать без перебора

компу хватило 5 дополнительных делений (все - на 18 см стороне)
0,19
0,1,3,6,10,17,18
0,13

а теперь - вопрос на сообразительность:
15 см на такой линейке можно получить двумя способами.
найдите эти способы
поставлю спасибку первому догадавшемуся