В первой, если не ошибаюсь, надо взять гирьки с весами 1, 3, 9 и 12. Тогда можно взвесить все от 1 до 25. У меня подобная была на собеседовании в ABBYY :) Во второй всякие неравенства просто записываются. Вроде их даже решить можно.
Пусть мы можем взвесить любой весь от 1 до х включительно. Тогда нам нужна гирька 2х+1. С помощью неё можно уже взвесить от 1 до 3х+1. От 1 до х уже умели, все остальное - это новая гирька, а старые либо ставим на другую чашу, либо на ту же. В общем можно вывести рекуррентное соотношение для весов гирек. А там и общую формулу. Ну или проще, в начале ничего не умеем, нужна гирька 1, затем нужна гирька 3, затем 9... и тут можно начать что-то подозревать))
1. 1, 3, 9, 27, общая формула - 3^n, с очевидностью.
2. если круглое озеро, то рассмотрим ГМТ таких точек, что сумма расстояний до города и деревни равна x>расстояние от города до деревни. Это эллипс, точнее семейство непересекающихся эллипсов с общими фокусами.
введем систему координат: (1, 0) - город, (-1, 0) - деревня, (x_0, y_0) - центр озера.
далее система уравнений из уравнения круга (центр, радиус) и уравнения эллипса(фокусы, большая ось как параметр). С очевидностью, получаем до 4 точек в зависимости от параметра. Ищем минимальное значение параметра, чтобы было хотя бы одно пересечение.
Это, конечно, правда. ))) Но хочется найти что-то попроще... Возможно, что-то аналогичное решению в предыстории... Ну, там, отражение+линия=профит. )))
а по первой - то же самое, что и Пете. Как показать, что это и далее будет оптимальный выбор гирек 3^n?
по первой - там простейшая индукция. Если хочешь, то каждый груз может находиться в одном из 3 состояний(справа, слева, не на весах), то есть состояний всего - 3^N. Таким образом, мы можем определить точно не более (3^n-1)/2 весов. Таким набором гирек он определяется.
по второй - можно поиграться с инверсиями. Я даже вроде нашел решение циркулем и линейкой, но надо на чертеже показывать.
Comments 9
Во второй всякие неравенства просто записываются. Вроде их даже решить можно.
Reply
Reply
Reply
Reply
2. если круглое озеро, то рассмотрим ГМТ таких точек, что сумма расстояний до города и деревни равна x>расстояние от города до деревни.
Это эллипс, точнее семейство непересекающихся эллипсов с общими фокусами.
введем систему координат: (1, 0) - город, (-1, 0) - деревня, (x_0, y_0) - центр озера.
далее система уравнений из уравнения круга (центр, радиус) и уравнения эллипса(фокусы, большая ось как параметр). С очевидностью, получаем до 4 точек в зависимости от параметра. Ищем минимальное значение параметра, чтобы было хотя бы одно пересечение.
Reply
Но хочется найти что-то попроще... Возможно, что-то аналогичное решению в предыстории... Ну, там, отражение+линия=профит. )))
а по первой - то же самое, что и Пете. Как показать, что это и далее будет оптимальный выбор гирек 3^n?
Reply
по второй - можно поиграться с инверсиями. Я даже вроде нашел решение циркулем и линейкой, но надо на чертеже показывать.
Reply
2. У меня тоже сть некое предположение с циркулем и линейкой, но не могу его доказать. ))) Вобщем, нам будет о чём поспорить при встрече. )
Reply
Leave a comment