а) В квадрате $7 \times 7$ клеток нужно отметить центры к клеток так, чтобы никакие четыре отмеченные точки не являлись вершинами прямоугольника со сторонами, параллельными сторонам квадрата. При каком наибольшем к это возможно?
б) Решите аналогичную задачу для квадрата $13 \times 13$ клеток.

Подробнее

На доске написано несколько нулей, единиц и двоек. Разрешается стереть две неравные цифры и вписать вместо них цифру, отличную от стертых (вместо 0 и 1 - цифру 2, вместо 1 и 2 - 0, вместо 0 и 2 - 1). Докажите, что если в результате таких операций на доске останется одно число, то оно не зависит от порядка, в котором производились стирания.

Подробнее

Для каких натуральных $k$ можно составить куб размерами $k \times k \times k$ из белых и черных кубиков $1 \times 1 \times 1$ так, чтобы для любого кубика ровно два из его соседей имели тот же цвет, что и он сам? (Два кубика считаются соседними, если они имеют общую грань.)

Подробнее

В чемпионате мира и Европы участвуют 20 команд. Среди них имеется $k$ европейских команд, результаты встреч между которыми на чемпионате мира идут в зачет чемпионата Европы. Чемпионат проводится в один круг.
При каком наибольшем $k$ может оказаться, что команда, набравшая строго наибольшее количество очков в чемпионате Европы, наберет строго наименьшее количество очков в чемпионате мира, если это:
а) чемпионат по хоккею (допускаются ничьи)?
б) чемпионат по волейболу (ничьих не бывает)?

Подробнее

а) Даны вещественные числа $a_1, a_2, a_3, b_2$ и положительные числа $p_1, p_2, q_1, q_2$. Докажите, что в следующей таблице $2 \times 2$

$\binom {\frac {a_1 + b_1}{p_1 + a_1} \frac {a_1 + b_2}{p_1 + q_2}}{\frac {a_2 + b_1}{p_2 + q_1} \frac {a_2 + b_2}{p_2 + q_2}}$

найдется число, которое не меньше числа, стоящего с ним в одной строке, и не больше числа, стоящего с ним в одном столбце.
б) Даны вещественные числа $a_1, a_2, \cdots, a_m, b_1, b_2, \cdots, b_n$ и положительные числа $p_1, p_2, \cdots, p_m, q_1, q_2, \cdots, q_n$. Составлена таблица $m \times n$, в которой на пересечении $i$-й строки ($i = 1, 2, \cdots, m$) и $j$-го столбца ($j = 1,2, \cdots, n$), стоит число

$\frac {a_i + b_j}{p_i + q_j}$.

Докажите, что в этой таблице найдется число, которое не меньше любого числа, стоящего с ним в одной строке, и не больше любого числа, стоящего с ним в одном столбце.

Подробнее

На столе лежат 50 правильно идущих часов. Докажите, что в некоторый момент сумма расстояний от центра стола до концов минутных стрелок окажется больше суммы расстояний от центра стола до центров часов.

Подробнее

В строчку подряд написано 1000 чисел. Под ней пишется вторая строчка чисел по следующему правилу: под каждым числом а первой строчки выписывается натуральное число, указывающее, сколько раз а встречается в первой строчке. Из второй строчки таким же образом получается третья: под каждым числом $b$ второй строчки выписывается натуральное число, указывающее, сколько раз $b$ встречается во второй строчке. Затем из третьей строчки так же строится четвертая, из четвертой - пятая и так далее.
а) Докажите, что некоторая строчка совпадает со следующей.
б) Более того, докажите, что 11-я строчка совпадает с 12-й.
в) Приведите пример такой первоначальной строчки, для которой 10-я строчка не совпадает с 11-й.

Подробнее

Можно ли вершины куба занумеровать различными трехзначными числами, составленными из цифр 1 и 2, так чтобы номера любых двух соседних вершин различались не менее чем в двух разрядах?

Подробнее

На квадратном листе бумаги нарисованы $n$ прямоугольников со сторонами, параллельными сторонам листа. Никакие два из этих прямоугольников не имеют общих внутренних точек. Докажите, что если вырезать все прямоугольники, то количество кусков, на которые распадется оставшаяся часть листа, не более $n + 1$.

Подробнее

На шахматной доске размера $99 \times 99$ отмечена фигура (эта фигура будет разной в пунктах а), б), в)). В каждой клетке фигуры $\: Ф$ сидит по жуку. В какой-то момент жуки взлетели и сели снова в клетки той же фигуры $\: Ф$; при этом в одну клетку могло сесть несколько жуков. После перелета любые два жука, занимавшие соседние клетки, оказались снова в соседних клетках или попали на одну клетку. (Соседними называются клетки, имеющие общую сторону или общую вершину.)
а) Пусть фигура $\: Ф$ - это «центральный крест», т. е. объединение средней вертикали и средней горизонтали (рис. а). Докажите, что в этом случае какой-то жук вернулся на место либо перелетел в соседнюю клетку



б) Верно ли утверждение, если фигура - это «оконная рама», то есть объединение центрального креста и всех граничных клеток доски (рис. б)?
в) Верно ли утверждение, если фигура - это вся доска?


Подробнее

В вершинах правильного $n$-угольника с центром в точке $О$ расставлены числа (+1) и (-1). За один шаг разрешается изменить знак у всех чисел, стоящих в вершинах какого-либо правильного $k$-угольника с центром $О$ (при этом мы допускаем и 2-угольники, понимая под 2-угольником отрезок с серединой в точке $О$). Докажите, что в случаях а), б), в) существует такое первоначальное расположение (+1) и (-1), что из него ни за какое число шагов нельзя получить набор из одних (+1):
а) $n = 15$;
б) $n = 30$;
в) $n$ - любое число, большее 2;
г) Попробуйте пояснить для произвольного $n$, чему равно наибольшее число $k(n)$ различных расстановок (+1) и (-1), среди которых ни одну нельзя получить из другой за несколько шагов. Докажите, например, что $K(200) = 2^{80}$.

Подробнее

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

Подробнее

По окружности расположено несколько черных и белых фишек. Двое по очереди проделывают такую операцию: первый убирает все черные фишки, имеющие белого соседа (хотя бы с одной стороны), а второй после этого убирает все белые фишки, имеющие черного соседа. Так они делают до тех пор, пока не останутся все фишки одного цвета.
а) Пусть вначале было 40 фишек. Может ли случиться, что после того, как каждый сделает два хода, на окружности останется одна фишка?
б)* На окружности сначала было 1000 фишек. Через какое наименьшее число ходов на окружности может остаться одна фишка?

Подробнее

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

Подробнее

Написан многочлен $x^{10} + \ast x^9 + \ast x^8 + \cdots + \ast x^2 + \ast x + 1$. Двое играют в такую игру. Сначала первый заменяет любую из звездочек некоторым числом, затем второй заменяет числом любую из оставшихся звездочек, затем снова первый заменяет одну из звездочек числом и т. д. (всего 9 ходов). Если у полученного многочлена не будет действительных корней, то выигрывает первый игрок, а если будет хотя бы один корень - выигрывает второй. Может ли второй игрок выиграть при любой игре первого?

Подробнее