AB

Периодически возникающие в Спаме (и также быстро угасающие) темы про задачи предлагается продолжать здесь, в Библиотеке, в одной мозговой ветке, которую имеет смысл выращивать именно тут. Поэтому свою активность по решению и загадыванию сабжа далее буду здесь проявлять, чего и вам желаю:)

Пост номер 1)
Офицер выстроил американских новобранцев в шеренгу и скомандовал им "Налево!". В принципе новобранцы знали примерно где право, а где лево, но не были на 100% уверены в своих знаниях. Поэтому когда оказывается, что некоторые после поворота стоят лицом к лицу, в таких парах оба в испуге разворачиваются в обратные стороны! После поворота ситуация может повториться в других местах строя, и так далее - каждую секунду некоторые болванчики (все одновременно) поворачиваются на 180 градусов, увидев лицо соседа. Те же, кто видит затылок соседа или вообще не видит соседа (стоит на краю строя) - не поворачиваются, а остаются стоять как стояли. Наблюдая этот процесс, сержант думает - ват за фака, когда это кончится?

Вопрос - возможно ли бесконечное движение (считайте что жизнь новобранца бесконечна и конца света не будет в 2012 году)) и если нет, то какое максимальное время движение продлится, если скажем их 100 человек?

fagot

Крайние повернутся не более одного раза, соседние с ними - не более трех раз (т. к. на каждые 2 их поворота приходится поворот крайних), соседние с ними - не более 7 раз и т. д. Значит, будет конечное число поворотов.
Чуть сложнее доказывается точная оценка на время. Предположим, a новобранцев повернулись налево, а b - направо. Можно считать, что новобранцы не поворачиваются, а просто меняются местами. Тогда самый левый из повернувшихся налево новобранцев будет двигаться каждую секунду, пока не займет крайнее левое положение, следующий за ним может не двигаться не более 1 секунды до того, как займет второе слева положение, следующий - не более 2 секунд и т. д. самый правый сможет не двигаться не более a-1 секунд. Двигаться же он сможет не более b секунд, так как при каждом движении он пропускает новобранца, повернувшегося направо, поэтому не более, чем через a+b-1 секунд он займет свое a-тое слева положение, после чего все операции прекратятся. Следовательно, перестановки могут продолжаться не более a+b-1=99 секунд. Пример на 99 секунд очевиден: например, только самый правый новобранец повернется налево.

AB

Ну шото вроде этого)

Следующая загадка. Темная кладовка имеет треугольную форму, в центре двух стенок (длиной a и b скажем) неподвижно сидят кошки, которые видят в темноте на расстояние соответственно a/2 и b/2. Они увидят всех мышей в кладовке? Если нет - то пример, если да - почему? Аналогичный вопрос для кладовки в форме (неправильного) четырехугольника, в котором кошки сидят на всех сторонах (то есть, кошек четыре).

v1005869

Для разных треугольников разные варианты: допустим, если треугольник равнобедренный (самый простой вариант), и у него высота меньше а/2 (а - основание), то даже одна кошка сидящая на а, будет видеть всех мышей.
Если треугольник прямоугольный, То на стороне без кошек всегда будет "мертвая зона". (А вообще-то, если кладовка высокая, и ее высота больше a/2 и b/2, и учитывая, что мыши умеют лазить по стенам... :))

AB

мыши на плоскости)

fagot

Для любой точки в треугольнике одна из сторон a или b будет видна под прямым или тупым углом, так как сумма этих углов больше 180. Тогда соответствующая кошка и будет видеть эту точку, поскольку медиана неострого угла треугольника не превосходит половины противоположной стороны.
Для четырехугольника то же самое: для любой точки в четырехугольнике одна из сторон будет видна под прямым или тупым углом, эта кошка и будет видеть эту точку.

AB

Решение такое: если опустить высоту из угла между кошками, то треугольник разбивается на два прямоугольных треугольника, которые вписываются в окружности, построенные на гипотенузах (то есть - сторонах исходного треугольника) как на диаметрах. Четырехугольник - это два треугольника, если разбить по диагонали.

Следующая задача. Пусть x,y>1. Доказать, что

y^logxy+x^logyx>=x+y.

fagot

Будем считать, что x\geq(больше либо равно) y\geq 1 и a\geq b. Тогда поскольку производная x^a-x^b равна ax^{a-1}-bx^{b-1}\geq 0, то x^a-x^b\geq y^a-y^b,
откуда x^a+y^b\geq x^b+y^a. Подставляя вместо a и b числа \log_yx и \log_xy соответственно, получаем требуемое неравенство.

Чтобы было интересно не только математикам, надо давать куда менее специализированные и более жизненные задачи. Например:
перед алкоголиком Васей стоят две бесконечно большие бочки со спиртом. У
Васи есть два очень ценных ковша: один емкостью $2-\sqrt{2}$ литров, а
другой~--- $\sqrt {2} $ литров. Удастся ли ему с их помощью перелить из одной
бочки в другую ровно 1 литр спирта ? :)

AB

А у меня доказательство неравенства есть элементарное, только через неравенство между средним арифметическим и геометрическим)

Насчет Васи - не понял что значит $2-\sqrt{2}$ - это два минус корень из двух? Кажется мне что таки не удастся и все сводится в непредставимости корня из двух как m/n)

AB

Вот еще: картина раскрашена двумя цветами. У меня в руках игла и я хочу поместить ее на картину так, чтобы концы иглы попали на точки одного цвета. Всегда ли можно так сделать и если нет, то как раскрасить картину, чтобы нельзя было? Тот же вопрос, но если я хочу чтобы концы иглы наоборот - попали в разные цвета. Картину гнуть незя.

fagot

Ничего не понял. Какой формы и размеров картина?


Да. Я использую стандартные TEX-овские обозначения. Их вообще весьма полезно
знать - это общепринятая среда для набора научных статей. Подробнее, например,
http://www.tex.uniyar.ac.ru/doc.htm

Безусловно. Вопрос в том - как именно? Ведь целое число 2 литра легко можно перелить :)

AB

Ну скажем так: картина это прямоугольное (например) полотно намного больше иголки в размерах. Можно считать что плоскость окрашена в два цвета.

Насчет Васи - какие у него действия могут быть в принципе? Если набирать тем или другим полным ковшом только и переливать, то пусть он налил a ковшей по $2-\sqrt{2}$ литров, b ковшей по $\sqrt {2} $ литров, a и b могут быть отрицательными, если каким-то ковшом он больше забрал обратно в бочку. Тогда
a$2-\sqrt{2}$ + b$\sqrt {2}$ =1 и $\sqrt {2}$(a-b)=1-2b, что возможно только если обе части равны 0, но так тоже не получается, так что не сможет перелить.
Вернее может чисто случайно и сможет, если поддаст хорошо)

fagot

Абсолютно верно
По поводу картины - ну, это совсем просто, я не буду здесь писать решение - пусть другие подумают. А если им тоже покажется просто, то пусть решат ту же задачу для 3 цветов. Кстати, это известная нерешенная проблема комбинаторной геометрии - какого минимального количества цветов достаточно, чтобы не существовали 2 одноцветные точки на расстоянии 1?
Вроде, доказано для 4 и есть пример для 6, но 6 или 5 - пока неизвестно.
Я знаю простой пример для 7.

AB

Пусть подумают)