2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу 1, 2  След.
 
 Туймаада 2016
Сообщение19.07.2016, 12:54 
Аватара пользователя


07/01/15
1145
Математическая часть международной олимпиады. Перед каждой задачей записано имя автора задачи.

А. Голованов. 1. Последовательность $(a_n)$ задана условиями $a_1=0$, $$a_{n+1} = \frac{a_1+a_2+\ldots+a_n}n+1.$$ Докажите, что $a_{2016} > \frac 12 + a_{1000}$.

А. Чухнов. 2. На одной из клеток клетчатой плоскости стоит кубик. На каждой грани кубика нарисована стрелочка в одном из четырёх направлений, параллельных сторонам грани. Антон смотрит на кубик сверху и перекатывает его через ребро в направлении, указанном стрелкой, нарисованной на верхней грани. Докажите, что кубик никогда не заметёт никакого квадрата $5\times5$.

А. Пастор. 3. Высоты $AA_1, BB_1, CC_1$ остроугольного треугольника $ABC$ пересекаются в точке $H$. Точки $A_0, B_0, C_0 -$ середины сторон $BC, CA$ и $AB$ соответственно. На отрезках $AH, BH$ и $HC_1$ отмечены точки $A_2, B_2, C_2$ соответственно, такие что $\angle{A_0B_2A_2} = \angle{B_0C_2B_2} = \angle{C_0A_2C_2} = 90^\circ$. Докажите, что прямые $AC_2, BA_2$ и $CB_2$ пересекаются в одной точке.

В. Шевелёв. 4. При каждом натуральном $k$ найдите число решений уравнения $$8^k = x^3 + y^3 + z^3 - 3xyz$$
в неотрицательных целых числах $x, y, z,$ причем $0 \le x\le y\le z$.

 Профиль  
                  
 
 Re: Туймаада 2016
Сообщение19.07.2016, 16:24 
Аватара пользователя


20/03/12
139
$\displaystyle1.\ a_n=H_{n-1}=\sum_{k=1}^{n-1}\frac1k,\ n\geqslant2$

 Профиль  
                  
 
 Re: Туймаада 2016
Сообщение20.07.2016, 14:35 
Аватара пользователя


07/01/15
1145
Первый орешек расколот! Human вывел соотношение, из которого сразу же получаем: $$a_{2016} - a_{1000} = \sum\limits_{k=1000}^{2015}\frac1k > \frac{1016}{2015} > \frac 12.$$

 Профиль  
                  
 
 Re: Туймаада 2016
Сообщение20.07.2016, 16:35 


25/08/11

1074
Кубический многочлен не раскладывается на множители?

 Профиль  
                  
 
 Re: Туймаада 2016
Сообщение21.07.2016, 04:02 
Аватара пользователя


07/01/15
1145
sergei1961, если я отвечу, это уже будет подсказка. А хотя... Если бы не раскладывалось, то уравнение вообще было бы невозможно решить.

 Профиль  
                  
 
 Re: Туймаада 2016
Сообщение21.07.2016, 16:09 
Заслуженный участник


10/01/16
2315

(Оффтоп)

SomePupil в сообщении #1139117 писал(а):
если я отвечу, это уже будет подсказка.

Это - уже подсказка...

 Профиль  
                  
 
 Re: Туймаада 2016
Сообщение21.07.2016, 21:01 
Заслуженный участник


08/04/08
8556
Про 4 все так пишут, будто она легкая, но ничего не пишут.
Ну напишу я, только у меня не особо простое решение:

$F=x^3+y^3+z^3-3xyz=(x+y+z)(x+\omega y+\omega^2 z)(x+\omega^2 y+\omega z), \ \ \omega^3=1$
Последние 2 множителя сопряжены. $2$ - простое в $\mathbb{Z}$ и $3\nmid 2-1$, значит $2$ - простое в $\mathbb{Z}[\omega]$. Значит 2,3-й множитель действительны: $y=z$, значит $F=(x+2y)(x-y)^2$.
$u=x-y, x=u+y, F=(u+3y)u^2=8^k$
Если $k=0$, то $u=1,y=0$.
Если $2|u$, то $2|y$, откуда уравнение $(u+3y)u^2=8^k$ сводится к уравнению $(u_1+3y_1)u_1^2=8^{k-1}$
Если $2\nmid u$, то $u=1, 3y=8^k-1$ - единственное решение есть только при четном $k$.
Значит всего $\left[\frac{k}{2}\right]$ решений.

Правильно хоть? :roll:

 Профиль  
                  
 
 Re: Туймаада 2016
Сообщение22.07.2016, 00:44 
Аватара пользователя


07/01/16
1426
Аязьма
Sonic86 в сообщении #1139353 писал(а):
Правильно хоть? :roll:
У меня по-другому получилось, для любого $k$ решение одно и при том тривиальное: $\{x,y,z\}=\{0,0,2^k\}$. Логика такая: мы можем положить $y=x+u, z=x+u+v, x,u,v\ge 0$, тогда исходное равенство эквивалентно $8^k=(3x+2u+v)(u^2+uv+v^2)$. Обе скобки должны быть степенями двойки, значит, $x,u,v$ по крайней мере четны; выделив двойку из этих трех чисел мы получим равенство того же вида; бесконечно так не поделаешь, значит, одно (и только одно) из $u,v$ равно нулю. При этом, $v=0$ решений не дает, т.к. должно быть одновременно $u=2^n$ и $3x+2u=2^n$, а $u=0$ дает упомянутое выше единственное тривиальное решение.

-- 22.07.2016, 00:57 --

А, нет, ерунду спорол :-( то что один из множителей равен $4^n$, не означает, что другой должен быть равен $2^n$, а лишь $2^{3k-2n}$...

-- 22.07.2016, 01:35 --

В общем, похоже, всего $k+1$ решений, половина для $u=0$, а половина для $v=0$ (половина с точностью до $\pm 1$ если $k$ четно). Например, для $k=5$ годятся следующие тройки $x,y,z$:

$2730,2730,2732

168,168,176

0,0,32

10922,10923,10923

680,684,684

32,48,48$

 Профиль  
                  
 
 Re: Туймаада 2016
Сообщение22.07.2016, 08:54 


26/08/11
2057
Назовем решение "базовым", если хотя бы одно из трех чисел нечетное.
$(x+y+z)(x^2+y^2+z^2-xy-yz-zx)=8^k$
При таких условиях оба сомножителя не могут быть четными, следовательно или $x+y+z=1$, что неинтересно, решение $(0,0,1)$ является базовым для $k=0$, или
$x^2+y^2+z^2-xy-yz-zx=1$

$(z-y)^2+(z-x)^2+(y-x)^2=2$
Сумма трех квадратов равна двум, решения ясны:
$(x,x,x+1)$, а также $(x,x+1,x+1)$
В первом случае $3x+1=8^k$, во втором $3x+2=8^k$
В зависимости от четности $k$ либо первое, либо второе уравнение имеет решение. Тоесть, для любого $k$ существует ровно одно базовое решение.
Нам нужно посчитать все базовые решения от $0$ до $k$ - их ровно $k+1$

 Профиль  
                  
 
 Re: Туймаада 2016
Сообщение24.07.2016, 17:39 
Заслуженный участник


10/01/16
2315
2. Странная какая-то задача. Или я чё не пОнял? И что значит "заметет"?
Нарисуем еще на каждой грани красную стрелку, противоположную существующей. Красные стрелки показывают, какая грань будет следующей верхней. (Если отметить центры граней, и соединить соответствующие центры по красным стрелкам, получим орграф с вершинами в вершинах октаэдра). Ясно, что, гуляя по стрелкам, мы вляпаемся в цикл. Какой длины?
а) 2. Тогда кубик будет дергаться по двум клеткам, и всего затопчет не боле $2+4$ клеток.
б) 3. Катание кубика показывает, что такому циклу соответствует движение по квадратику $2\times 2$. Мало.
в) 4. Пар противоположных вершин - три. Значит, в цикле есть така пара, пусть это
$A_1$ и $A_2$, Тогда цикл есть $A_1,Y, A_2, X$. Если $X,Y$ - противоположны, то кубик укатится по прямой в туман. Если нет, то - катаем - кубик катится по контуру квадратика $3\times3$. Мало.
г) 5. Одна вершинка не вошла, есть пара противоположных, и с одной стороны от них - одна вершинка, а с другой - две. Методом глядения на картинку видим, что, с точностью до переобозначений и симметрии, цикл есть $A_1,B_1,A_2,B_2,C_1$ (либо $A_1,B_1,A_2, C_1,B_2$ - но это то же самое). Катая кубик, видим: затопчет контур квадратика $6\times6$ со вдавленными углами ( в шахматной нотации:
$b_1$ (старт!), $ c_1,d_1,e_1,e_2; f_2$ (второй цикл)$f_3,f_4,f_5,e_5,e_6$ (третий) $d_6,c_6, b_6,b_5,a_5$ (четвертый ) $a_4,a_3,a_2,b_2,b_1$. Далее - зациклились). Итого: $20+1$ клеток (не боле)
д) 6. Расставим по кругу 6 точек: 2 красных, две синих и 2 зеленых, так, что одноцветные не стоят рядом. Это можно сделать (с точностью до перекрашивания и симметрий) двумями способами : либо все одноцветные - в противоположных вершина, либо только одна пара - в противоположных. Катание кубика показывает, что в обоих случаях он уедет в туман (за три перекатывания он "ходит конем" (в первом случае - конем $1+1$, во втором - обычным конем $2+1$), далее этот же ход повторяется ). Опять ни фига не вышло...

(Оффтоп)

Ну дурное какое-то решение. Может, как то четность-нечетность цикла обыграть - для 4 и 6 - едет в туман....

 Профиль  
                  
 
 Re: Туймаада 2016
Сообщение25.07.2016, 05:05 
Аватара пользователя


07/01/15
1145
Shadow, изящно и правильно!

DeBill, да, вторая задача довольно странная. "Заметет квадрат $5\times 5$" означает "побывает в клетках, составляющих квадрат $5\times 5$".
DeBill писал(а):
Ясно, что, гуляя по стрелкам, мы вляпаемся в цикл

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

P. S. Задачи такого рода, как вторая, требуют решения определенного вида. Фокус тут в том, что надо расписать всё, что очевидно, а всё, что неочевидно $-$ замести под ковёр и сделать вид, что это очевидно. Да, это не то, что научные статьи писать $-$ тут олимпиада.

 Профиль  
                  
 
 Re: Туймаада 2016
Сообщение25.07.2016, 09:16 
Заслуженный участник


10/01/16
2315
SomePupil
Гуляя по стрелкам - на графе!
А - что движение бывает без циклов - так в решении как раз и получены три таких случая...

 Профиль  
                  
 
 Re: Туймаада 2016
Сообщение25.07.2016, 09:53 
Заслуженный участник
Аватара пользователя


30/01/06
72407
DeBill
Не хотите расписать все циклы на октаэдре и  додека  икосаэдре?

 Профиль  
                  
 
 Re: Туймаада 2016
Сообщение25.07.2016, 10:03 


30/03/08
196
St.Peterburg
2) Всего $24 $ положения кубика на плоскости, $12 $ пар отличающихся поворотом на $180^0 $.

Возможны $2 $ случая:

1. После нескольких ходов встретится два положения кубика образующих пару . Это может произойти не более чем за $12 $ ходов. Поэтому , в этом случае, мы "зациклимся" и сделаем до этого момента не более $24 $ ходов.

2. Не встретились два положения кубика образующих пару.
В этом случае у кубика на плоскости может быть не более $6 $ различных ориентаций ( по $1 $ на каждой из граней). Т.е. не далее чем за $6 $ ходов траектория либо "зациклится" , либо начнет повторяться со смещением (a, b), где $|a|+|b| \le 6 $.

 Профиль  
                  
 
 Re: Туймаада 2016
Сообщение25.07.2016, 10:33 
Заслуженный участник


10/01/16
2315
Sergic Primazon
Здорово! То-то мне мое решение не нравилось...
Munin

(Оффтоп)

Это Вы так шутите, да?
Я ж по рабоче-крестьянски, именно что расписал все циклы на октаэдре; зачем про это спрашивать? А вот насчет доде-ико - тут я не понял....Или у меня что-то с чувством юмора не то? Или не у меня?

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 22 ]  На страницу 1, 2  След.

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group