IX Всероссийский студенческий турнир математических боёв

6 тур, 19 апреля 2015 г.

1.  В каждой строке и каждом столбце определителя порядка n по две единицы, а остальные элементы равны 0. Какие значения может иметь определитель?

2.  Решите уравнение .

3.  В пространстве расположены n прямых, не лежащих в одной плоскости. Каждая прямая имеет ровно три точки пересечения с другими прямыми, и никакие три прямые не пересекаются в одной точке. Найдите наименьшее возможное значение n.

4.  В каждой клетке прямоугольной таблицы стоит стрелка, указывающая на одну из соседних по стороне клеток этой таблицы. На одну из клеток ставится фишка. Своим ходом фишка перемещается на соседнюю клетку, на которую указывает стрелка. Стрелка при этом поворачивается на 90° направо. Если она при этом не будет показывать на какую-нибудь клетку таблицы (если клетка была на краю таблицы), то стрелка поворачивается еще в том же направлении, пока не покажет на соседнюю клетку таблицы. Докажите, что через некоторое число ходов фишка обойдет все клетки таблицы.

5.  В группе из 6 человек каждый знаком ровно с тремя другими. Докажите, что всех можно разбить либо на две тройки, в каждой из которых все знакомы, либо на две тройки, в каждой из которых все незнакомы.

6.  Докажите, что при любом натуральном n > 1 число (n – 2)! – НОД(n, (n – 2)!) делится на n.

7.  На окружности заданы n точек, две из них отмечены. Многоугольники с вершинами в заданных точках разобьем на две группы. К первой отнесем многоугольники с одной отмеченной точкой, ко второй – остальные. В какой группе больше многоугольников?

НЕ нашли? Не то? Что вы ищете?

8.  Между двумя берегами реки расположены 6 островов, соединенных мостами, как показано на рисунке. В результате урагана часть мостов могла разрушиться. Для каждого моста вероятность быть разрушенным равна 0,5. Какова вероятность, что после урагана с одного берега реки на другой можно будет пройти по мостам?

9.  Про два треугольника известно, что для каждого из них сумма длин любых двух его сторон равна сумме длин двух каких-нибудь сторон другого треугольника. Можно ли утверждать, что треугольники равны?

6 тур, 19 апреля 2015 г.

Решения задач

1. () Обозначим определитель n-го порядка через dn. Нетрудно заметить, что d2 = 0, d3 = ±2. Для определителей более высокого порядка произведем перестановку строк и столбцов, приведя определитель к специальному виду. Переставим столбцы так, чтобы в первой строке единицы оказались на первых двух местах. Затем на второе место поставим строку, которая начинается с единицы. Если вторая единица второй строки окажется на втором месте, то вторая строка совпадет с первой, и определитель окажется равен нулю. В противном случае переставим столбцы, чтобы вторая единица второй строки оказалась на третьем месте. Продолжаем в том же плане, пока вторая единица очередной (k­-ой) строки не окажется в том же столбце, что и вторая единица предыдущей строки. В результате у определителя выделится блок вида, изображенного на рис а), здесь для примера представлен случай k = 5. С оставшейся частью определителя продолжим те же преобразования, в результате он будет представлен в виде нескольких (возможно, одного) блоков указанного вида, расположенных по диагонали. Получившийся определитель будет равен произведению соответствующих определителей. Исходный определитель либо равен ему, либо отличается знаком.

Для вычисления определителя dk из второй его строки вычтем первую, а к третьей прибавим получившуюся строку. В результате определитель приведется к виду на рис. б). Видим, что для этого определителя выполняется соотношение dk = –dk – 2, которое дает понижение порядка. Для четных k приходим к определителю второго порядка, и тогда dk = 0. Для нечетных k приходим к определителю третьего порядка, и тогда dk = ±2.

Таким образом, при n > 3 определитель dn равен либо нулю, либо некоторой степени числа 2 со знаком ±. Показатель степени равен числу нечетных слагаемых, больших 2, на которые можно разложить число n. Чтобы найти все возможные значения этого показателя, находим все представления n = 2a + 3b с положительным b и неотрицательным a. Здесь b – это возможное число блоков, на которые распадается определитель. Для каждого такого представления dn = ±2b.

В итоге получаем d2 = 0, d3 = ±2, d4 = 0. Для остальных значений n имеем либо dn = 0, либо dn = ±2b. Возможные значения b идут с шагом 2. Наибольшее возможное значение bmax = m при n = 3m и n = 3m + 2, bmax = m – 1 при n = 3m + 1.

2 () Уравнение преобразуется к виду , а затем к виду . Производим замену = y. Уравнение приводится к системе

.

Решаем ее графическим способом в системе координат Оxy.

График первого уравнения – синусоида, второго – окружность с центром в точке (2; 2) и радиусом 5. Из графика видим, что эти фигуры пересекаются в четырех точках с абсциссами 0, 1, 3, 4. Непосредственной проверкой убеждаемся, что все эти значения действительно являются корнями исходного уравнения. Проверим, что других корней нет. На отрезке [0; 1] синусоида выпукла вверх, а окружность вниз, поэтому у них не более двух точек пересечения. Та же ситуация на отрезке[3; 4]. В точке (1; 0) касательная к окружности имеет угловой коэффициент 0,5, окружность расположена выше этой касательной, а синусоида при 1 < x £ 2 ниже касательной. При 1 £ x < 2 такая же ситуация с касательной в точке (3; 0). Остальная часть окружности выше синусоиды, так как для нее y > 1.

3. () Можно построить 6 прямых, удовлетворяющих условию задачи. Рассмотрим однополостный гиперболоид. На его поверхности расположены две серии прямых. Прямые из одной серии скрещиваются, а две прямые из разных серий пересекаются или параллельны. Выберем по три прямых из каждой серии, среди которых нет параллельных. Тогда каждая прямая пересекается ровно с тремя прямыми из другой серии.

Покажем, что менее шести прямых недостаточно. Рассмотрим две пересекающиеся прямые. Они лежат в одной плоскости α, и на каждой из них должно быть еще по две точки пересечения с другими прямыми. Если эти прямые не лежат в плоскости α, то они все различны, и их количество не менее 4. Если же какая-то из этих прямых лежит в α, то рассмотрим прямую, не лежащую в α. На ней есть по меньшей мере две точки, не принадлежащие α, и через них проходят две прямые, отличные от уже рассмотренных. В любом случае набирается не менее 6 прямых.

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

5. ) Построим граф, вершины которого соответствуют членам группы. Свяжем ребрами пары незнакомых людей. Тогда каждая вершина графа имеет степень 2. Построим цепочку ребер от участника А к следующему и т. д. Эта цепочка обязательно замкнется на А и содержит не менее трех ребер. Если в цепочку вошли не все участники, то оставшиеся образуют новую цепочку, в которой также будет не менее трех ребер. Значит, в каждой цепочке будет по три ребра, соответствующие вершины и образуют две тройки попарно незнакомых людей. Если же в цепочку войдут все шесть участников, то две тройки попарно знакомых людей строим, выбирая их из цепочки через одного.

6. ( )Пусть n составное, n = ab, a > 1, b > 1. Если a ¹ b, то а и b являются множителями в произведении (n – 2)!, и (n – 2)! делится на n. Тогда НОД(n, (n – 2)!) = n, и утверждение задачи выполняется. Если a = b > 2, то числа а и 2а являются множителями в произведении (n – 2)!, и (n – 2)! делится на n. Если
a = b = 2, то n = 4, НОД(n, (n – 2)!) = 2, (n – 2)! – НОД(n, (n – 2)!) = 0 делится на 4.

Если же n простое, то НОД(n, (n – 2)!) = 1. По теореме Вильсона (n – 1)! º –1(mod n). А так как
(n – 1) º –1(mod n), то (n – 2)! º 1(mod n), и (n – 2)! – 1 º 0(mod n), что и требовалось доказать.

7. () Рассмотрим произвольный многоугольник с вершинами в неотмеченных точках, он принадлежит ко второй группе. Добавив одну из двух отмеченных точек, получим многоугольник из первой группы, таких многоугольников два. Добавив к исходному многоугольнику обе отмеченные точки, получим опять многоугольник из первой группы. Таким образом, получаем соответствие с одинаковым числом многоугольников из первой и второй групп. Но в первой группе есть многоугольники, не попавшие в описанные четверки: это треугольники. Чтобы задать любой из них, выбираем две неотмеченные точки (из n – 2) и добавляем к ним одну отмеченную. Получим два многоугольник из первой группы. Им соответствует один многоугольник из второй группы, полученный добавлением двух отмеченных точек к двум выбранным неотмеченным. Таким образом, в первой группе число многоугольников такого вида больше, чем во второй, на . Но во второй группе есть еще многоугольники, не попавшие в построенное соответствие: это треугольники с двумя отмеченными вершинами. Их число равно числу способов выбрать третью вершину, то есть n – 2. Таким образом, разность между числом многоугольников в первой и второй группах равна = . Отсюда при n > 5 больше многоугольников в первой группе, при n = 5 их количество одинаково, и при n < 5 больше многоугольников во второй группе.

8. Пусть вероятность перейти на другой берег равна p. Будем считать, что под разрушенным мостом лодка проплывет, а под целым не проплывет. Тогда лодка проплывет через систему мостов в том и только том случае, если перейти по мостам на другой берег невозможно. Вероятность этого равна 1 – p. С другой стороны, ситуация с проплытием лодки полностью совпадает с переходом по мостам, когда роль островов выполняют участки, на которые мосты с островами поделили реку. Поэтому вероятность проплыть лодке под мостами также равна p. Отсюда p = 1 – p, и p = 0,5.

9. Нельзя. Пример: треугольники со сторонами 4, 4, 6 и 3, 5, 5.