Гирьки, весы, спички и треугольники

[finesoul]

1-я задача (в основном для математически подкованных): Есть 4 гирьки. Выберите их номинал (целые числа) так что бы можно было взвесить любой вес (целые числа) от 1 до 39 кг. Математики даже легко укажут какой максимальный диапазон весов можно охватить 3-мя, 4-мя, 5-ю гирьками. ;)

Решено:
29th-Jul-2011 09:31 pm EEST (GMT +3) alik_ntu Решено. Доказательство "на пальцах".

2-я задача (для тех кто сможет подойти к задаче нестандартно): Составьте из 6 спичек 4 РАВНОСТОРОННИХ треугольника. Спички не могут пересекать друг-друга (нельзя их класть одну на другую.)

Решено:
27th-Jul-2011 10:22 pm EEST (GMT +3) loteriel
29th-Jul-2011 09:31 pm EEST (GMT +3) alik_ntu
Но неоднозначность формулировки задачи позволяет и другие решения, например, можно из спичек составить "звезду Давида" и получить даже 6 равносторонних треугольников (или 6+2, смотря как считать). Поправил.

Comments

[loteriel.livejournal.com]

Вторая простенькая совсем - четыре на квадрат и ещё две на диагонали этого квадрата.

[finesoul]

не получится по теореме Пифагора
диагональ^2 = сторона^2 + сторона^2 = 2 * сторона^2
диагональ > сторона
http://ru.wikipedia.org/wiki/Теорема_Пифагора

[loteriel.livejournal.com]

А, ну да, не равносторонние же..:)
Будем искать :)

[loteriel.livejournal.com]

На плоскости нужно или в трёхмерном прострастве? Если второе, то можно тетраэдр из шести спичек построить - будут все четыре треугольника.

[finesoul]

В точку! ;) Поздравляю.

[alik-ntu.livejournal.com]

2-я задача
Очевидно, что подразумевается решение построить из 6 спичек правильную пирамиду и ее 4 грани будут теми самыми искомыми 4 равносторонними треугольниками.

Но неоднозначность формулировки задачи позволяет и другие решения, например, можно из спичек составить "звезду Давида" и получить даже 6 равносторонних треугольников (или 6+2, смотря как считать).

[finesoul]

Круто подмечено. Обновил задачу.
Решено на 200%. :)

[alik-ntu.livejournal.com]

1-я задача

Ответ: чтобы взвесить любой целый вес от 1 до 39 кг (а на самом деле даже до 40 кг) - надо взять гирьки номиналом 1 кг, 3 кг, 9 кг и 27 кг

Демонстрация.

Условные обозначения:
(n) - это взвешиваемый объект весом в n кг, например, (7) - объект весом в 7 кг
n - это гирька номиналом n кг, например, 9 - гирька номинала 9 кг
= - это разделитель чашечек, например, запись "(4) = 1+3" означает, что на одной чаше весов лежит взвешиваемый объект весом в 4 кг, а на другой - две гирьки 1 кг и 3 кг, плюс весы находятся в уравновешенном состоянии

Вся хитрость в том, что гирьки при необходимости подкладываются в обе чашки весов:

(1) = 1
(2)+1 = 3
(3) = 3
(4) = 1+3
(5)+1+3 = 9
(6)+3 = 9
(7)+3 = 1+9
(8)+1 = 9
(9) = 9
(10) = 1+9
(11)+1 = 3+9
(12) = 3+9
(13) = 1+3+9
(14)+1+3+9 = 27
(15)+3+9 = 27
(16)+3+9 = 1+27
(17)+1+9 = 27
(18)+9 = 27
(19)+9 = 1+27
(20)+1+9 = 3+27
(21)+9 = 3+27
(22)+9 = 1+3+27
(23)+1+3 = 27
(24)+3 = 27
(25)+3 = 1+27
(26)+1 = 27
(27) = 27
(28) = 1+27
(29)+1 = 3+27
(30) = 3+27
(31) = 1+3+27
(32)+1+3 = 9+27
(33)+3 = 9+27
(34)+3 = 1+9+27
(35)+1 = 9+27
(36) = 9+27
(37) = 1+9+27
(38)+1 = 3+9+27
(39) = 3+9+27
(40) = 1+3+9+27

Рассуждения при решении такие. Гирька 1 кг нужна в любом случае, ее зачисляем сразу. Далее, раз наша цель минимизировать количество гирек - смотрим можем ли мы обойтись без гирьки в 2 кг при взвешивании объекта весом 2 кг. Можем, если подложим к взвешиваемому объекту гирьку 1 кг, а на вторую чашечку кладем гирьку 3 кг. Значит вторая гирька - 3 кг. С помощью гирек 1 кг и 3 кг мы можем взвесить любой объект весом от 1 кг до 4 кг, значит теперь думаем как взвесить объект весом 5 кг и опять же пытаемся минимизировать число разных гирек, т.е. подкладываем обе имеющиеся в чашечку к объекту, следовательно третья гирька должна быть весом 5+1+3 = 9 кг.
Или в общем виде: n-я гирька должна иметь вес Xn = 2*сумма(Xi, при i от 1 до n-1) + 1
Значит 4-я гирька должна иметь номинал = 2*(1+3+9) + 1 = 27
А 5-я = 2*(1+3+9+27) + 1 = 81
и т.д.

Ну и, соответственно:
с помощью 3-х гирек можно взвесить любой объект с весом от 1 кг до 1+3+9=13 кг
с помощью 4-х - от 1 кг до 1+3+9+27=40 кг
с помощью 5-ти - от 1 кг до 1+3+9+27+81=121 кг

[finesoul]

Решено, но доказательство "на пальцах".

А как будеш доказывать на большем количестве гирек?
Опять перечислением всевозможных вариантов?
Почему не 2 и 3 ? И т.д.

> Или в общем виде: n-я гирька должна иметь вес
а кто сказал что ты сможешь при таком подходе взвесить весь диапазон?

Оно то понятно что "так должно быть", но почему?
Достаточность доказывается за пять минут под другим углом зрения.

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

[alik-ntu.livejournal.com]

Согласен, никакого строгого доказательства в моем ответе нет.
Скажем так, это было решение полученное эмпирическим путем. )

Ну, а если попытаться его (решение) обосновать теоретически, то видимо удобнее всего углубиться в троичную систему счисления (не зря ведь у меня эмпирически получились гирьки, у которых номинал постоянно умножается на 3, это по сути равно весу очередного разряда троичного числа). Почему именно троичная - каждая гирька может либо быть в первой чашечке, либо во второй, либо быть отложена в сторону. Три состояния = троичная система счисления.

Тогда вопрос "почему именно 1,3,9,27,81,..." снимается - это веса разрядов выбранной троичной системы счисления. Осталось только сформулировать алгоритм представления и доказать, что произвольное число можно разложить таким образом.

[finesoul]

По почте прийдет...
Решение очень элегантное. Если подробно, то длинно и четко...
1) Каждая гирька може быть -m 0 +m, что есть смещеный на -m диапазон 0m 1m 2m
и фактически есть проекцией разряда в 3-ичной системе с весом m.
2) У нас 4 гирьки значит 4 разряда с весами m3, m2, m1, m0.
Числа у которых веса удовлетворяют условию m (i) = m(i-1)*m
покрывают весь диапазон значений 0 до m^разрядов-1.
Если вес разряда больше пявляются пробелы, меньше - дубликаты.
Можно доказать идукцией, а можно принять как аксиому.
Поэтому нам подойдут веса троичной СИ ( ...,27, 9, 3, 1).
3) Посчитаем хватит ли нам значений?
2222 = 2*27+2*9+2*3+2*1 = 81-1=80
4) Вспоминаем, что 2m у нас нет, а есть только -m.
Остался только финальный рывок: 2m = 3m -m
Т.е. для двоек надо увеоичить след разряд на 1, а в текущем разряде установить -1
5) Дополнительное ограничение уменьшает покрываемый диапазон до 1111
1111 = 1*27+1*9+1*3+1*1 = 40