ОММО 2019
Условия и ответы ОММО (все варианты).
info@olympiads.biz - почта для подключения следующих олимпиад.

Очный тур олимпиады школьников СПбГУ 2015-2016 по математике / Задания и решения
  • Пропуск.
  • Задача №1 (вариант 6).
    В черных клетках шахматной доски `8`х`8` расставлены числа `1,2,3,...,32` так, что сумма чисел, расположенных в любом квадратике `2`х`2`, не превосходит `S`. Найдите наименьшее возможное значение `S`.
    Решение:
    Т.к. расматриваются все возможные квадраты `2`x`2`, то найдется хотя бы один квадрат в котором есть число `32`.
    Каждый квадрат накрывает `2` черные клетки, поэтому в этом квадрате обязательно будет еще одно число не меньшее чем `1 => S>=33`.
    Покажем расстановку чисел на доске для `S=33`.
    image
    Ответ: `33`.

    Задача №2 (вариант 6).
    Даны числа `a,b,c,d,e,f`, причем `b^2>=a^2+c^2`. Докажите неравенство `(af-cd)^2<=(ae-bd)^2+(bf-ce)^2`.
    Решение:
    Рассмотрим выражение `F=(ae-bd)^2+(bf-ce)^2-(af-cd)^2`.
    Замена, `ae-bd=x, bf-ce=y`.
    `F*b^2=x^2b^2+y^2b^2-(abf-bcd)^2`.
    Заметим, что `xc+ya=aec-bdc+abf-aec=abf-bdc`.
    Значит, `F*b^2=x^2b^2+y^2b^2-(xc+ya)^2`.
    `F*b^2=x^2(b^2-c^2)+y^2(b^2-a^2)-2xyac`.
    По условию, `b^2-c^2>=a^2, b^2-a^2>=c^2`.
    Тогда, `F*b^2>=x^2a^2+y^2c^2-2xyac=(xa-yc)^2>=0`.
    Следовательно, `F>=0`, что и требовалось доказать.
    Ответ: доказано.

    Задача №3 (вариант 6).
    Треугольник `ABC` с углом `/_ABC=135^0` вписан в окружность `omega`. Прямые, касающиеся `omega` в точках `A` и `C`, пересекаются в точке `D`. Найдите угол `/_ABD`, если известно, что `AB` делит отрезок `CD` пополам.
    Решение:
    image
    Т.к. `/_ABC=(3pi)/4` - вписанный угол и тупой, то центральный `/_AOC=2*(pi-/_ABC)=2*(pi-(3pi)/4)=pi/2`.
    `AO=OC=r` - радиусы окружности.
    `AO_|_AD, CO_|_CD` - т.к. касательные `_|_` радиусу.
    Тогда `OADC` - квадрат со стороной `r`.
    `CK=KD=r/2`.
    `tan(/_BAD)=(KD)/(AD)=(r/2)/r=1/2`.
    `1/cos^2(/_BAD)=1+tan^2(/_BAD)`,
    `1/cos^2(/_BAD)=1+1/4`,
    `cos^2(/_BAD)=4/5`,
    `cos(/_BAD)=2/sqrt(5)`,
    `sin(/_BAD)=cos(/_BAD)*tan(/_BAD)=1/sqrt(5)`.
    Треугольник `AOB` - равнобедренный, тогда `AB=2*AO*cos(/_OAB)=2r*cos(pi/2-/_BAD)=2*r*sin(/_BAD)=(2r)/sqrt(5)`.
    `(AB)/(AD)=((2r)/sqrt(5))/(r)=2/sqrt(5)` - т.к. отношение сторон `AB` к `AD` равно косинусу угла заключенного между этими сторонами, то треугольник `ABD` - прямоугольный `=> /_ABD=pi/2`.
    Ответ: `/_ABD=pi/2`.

    Задача №4 (вариант 6).
    На складе хранится `1500` тонн различных товаров в контейнерах. Вес любого контейнера кратен тонне и не превосходит `k` тонн. К складу подан состав из `25` платформ, грузоподъемность которых по `80` тонн. При каком максимальном `k` этим составом можно гарантированно вывезти весь товар?
    Решение:
    Пусть `k=27`.
    Положим, что в `55` контейнерах по `27` тонн груза, итого `1485` тонн. Еще `1500-1485=15` тонн в остальных контейнерах, их можем не учитывать.
    На одну платформу можно погрузить не более двух контейнеров (`3*27>80`), значит, всего нужно минимум `[55/2]+1=28` платформ. По условию, состав состоит из `25` платформ, поэтому груз нельзя увезти этим составом.
    Если `k>=28`, то строим аналогичный пример.
    Пусть `k<=26`.  
    `a_i` - вес `i`-го контейнера, `n` - число контейнеров.
    По условию, `a_1+a_2+...+a_n=1500, a_i<=26` для всех `i in [1;n]`, при этом `a_i in NN`.
    При `n<=75` все контейнеры гарантированно можно погрузить на состав, поскольку каждая платформа вмещает минимум три контейнера (`3*26<80`).
    Будем считать, что грузили контейнеры в порядке убывания веса (на любую свободную платформу) и `a_i` упорядочены по убыванию.
    Пусть нашелся такой `i>=76`, что `a_i` не влез на платформу. Тогда, `a_i>a`, где `a` - максимальное свободное место на любой из платформ.
    Общее свободное место равно `2000-1500=500`, поэтому `a>=500/25=20 => a_i>=21`.
    Тогда, `1500>=a_1+...+a_i>=21i => i<=[1500/21]=71`. Противоречие.
    Итак, при `k<=26` гарантированно можно увезти все грузы.
    Ответ: `k=26`.

    Задача №5 (вариант 6).
    Дано натуральное число `x=8^n-1`, где `n` - натуральное число. Известно, что `x` имеет ровно три различных простых делителя, один из которых равен `31`. Найдите `x`.
    Решение:
    Заметим, что `2^5-1=31`. Тогда, `8^5-1` делится на `2^5-1=31`.
    Пусть `n` дает остаток `d` при делении на `31`. Тогда `x=(8^5)^k*8^d-1` дает остаток `8^d-1` при делении на `31`.
    Подойдет только `d=0`, поэтому `n` делится на `5`.
    В таком случае, `x` делится на `8^5-1=7*31*151`. Значит, `7,31,151` являются всеми простыми делителями `x`.
    `x=(2^n-1)(4^n+2^n+1)=7^a*31^b*151^c`, где `a,b,c in NN`.
    Пусть `p` - общий простой делитель выражений `2^n-1` и `4^n+2^n+1`.
    Тогда, `4^n+2^n+1-(2^n-1)^2=3*2^n` делится на `p`.
    `p!=2 => p=3`. Но `x` делится только на `7,31,151`, поэтому выражения взаимно-простые.
    `2^n-1=32^k-1 vdots 31`.
    Если `n` четно, то `4^n+2^n+1=(3+1)^n+(3-1)^n+1` дает остаток `0` при делении на `3`. Противоречие.
    `1` случай: `2^n-1=31^b`.
    `(2^k-1)(16^k+8^k+4^k+2^k+1)=31^b`.
    Пусть `2^k-1` делится на `31`. Тогда, `2^k` дает остаток `1` при делении на `31`.
    Значит, `16^k+8^k+4^k+2^k+1` дает остаток `5` при делении на `31`. Противоречие.
    Тогда, `2^k-1=1 => k=1, n=5, x=32767`.
    `2` случай: `2^n-1=31^b*7^a`.
    `(2^k-1)(16^k+8^k+4^k+2^k+1)=31^b*7^a`.
    `k>1`, поэтому `2^k-1` делится на `7` или на `31`.
    Если `2^k` дает остаток `1` при делении на `7` или на `11`, то `16^k+8^k+4^k+2^k+1` дает остаток `5`.
    Поэтому возможны два случая: `2^k-1=7^a` или `2^k-1=31^b`.
    В первом случае получим, что `k` кратен `3` и уравнение `(2^m-1)(4^m+2^m+1)=7^a`.
    Есть решение `m=1`, а при `m>1` получим противоречие по делимости второго сомножителя на `7`.
    В уравнении `2^k-1=31^b` все аналогично, только `k` кратен `5`. Решений нет.
    `3` случай: `2^n-1=31^b*151^c, 4^n+2^n+1=7^a`.
    `(2^k-1)(16^k+8^k+4^k+2^k+1)=31^b*151^a`.
    Аналогично, `2^k-1` делится на `31` или на `151`. Первый случай уже разобран.
    Пусть `2^k-1=151^c`. Мы уже знаем, что `2^15-1=8^5-1` делится на `151`.
    Перебором остатков покажем, что `2^k-1` делится на `151` только при `k=15m` и получим аналогичное противоречие.
    Или немного проще: `4^n+2^n+1` делится на `7` только если `2^n` дает остаток `2` при делении на `7`.
    `2^n-2 vdots 7 => 2^(n-1)-1 vdots 7 => n-1 vdots 3`.
    Но тогда `2^n-1` не делится на `151`, поскольку `n` не кратен `3`, а значит не делится и на `15`.
    Ответ: `x=32767`.
  • Задача №1 (вариант 1).
    При каком наименьшем `k` можно отметить `k` клеток доски `10`х`11` так, что при любом размещении на доске трехклеточного уголка он задевает хотя бы одну отмеченную клетку?
    Решение:
    Под "задеванием" будет считать любое соприкоснование отмеченной клетки с трехклеточным уголком (по стороне клетки, по угловой точке, наложение уголка на клетку).
    Приведем пример c `k=10`. Отмеченные клетки оранжевого цвета. На красные области и черные линии внимания не обращаем.
    image
    Пусть `k=9`.
    Разобьем доску на три части (`3`х`10`, `5`х`10`, `3`х`10`).
    В каждой части должно быть минимум `3` отмеченные клетки. Это легко следует из того, что мы указываем `9` уголков - по углам доски, в серединах боковых сторон и в центре доски.
    `k=9`, поэтому в каждую часть попадет ровно три отмеченные клетки.
    Пусть в верхней части все три отмеченные клетки находятся на третьей строке.
    Тогда между некоторыми двумя из них расстояние составит минимум три клетки, и найдется уголок между ними (примыкающий к верхней границе доски), не удовлетворяющий условию задачи. Если же расстояния между ними не превышает двух клеток, то один из угловых уголков не будет задевать отмеченную клетку.
    Итак, максимум две отмеченные клетки могут находиться на третьей строке. Аналогично, в нижней части максимум две клетки могут находиться на девятой строке.
    Значит, минимум две клетки находятся на `1`-`2` и `10`-`11` строках.
    Рассмотрим центральную часть `5`х`10` с тремя отмеченными клетками.
    Разобьем ее на два квадрата `5`х`5`. В одном из этих квадратов находится одна отмеченная клетка (`0` не может быть). На рисунке правый квадрат (на оранжевые клетки не обращаем внимания).
    Если эта клетка находится на `4` или `5` столбце (считая от края доски), то примыкающий к краю доски уголок не будет задет. Аналогично для `1` или `5` строки.
    Также не подходит случай расположения клетки на `1` столбце и `2`-`4` строк, поскольку найдется уголок внутри квадрата, который не будет задет.
    Тогда остаются только две клетки, которые могут быть отмеченными (обведен красным на рисунке).
    `1` случай: пусть отмечена правая (ближе к границе) клетка.
    Тогда однозначно определяется положение центральной клетки и пары (верхняя + нижняя). От этой пары определяются области из двух клеток, где могут находиться другие две клетки.
    Отсюда однозначно располагаются еще две клетки. Остается одна отмеченная клетка в другом квадрате `5` на `5`. Как бы эту клетку не поставить, всегда вылезает уголок (на `1`-`2` столбцах), который не задевает никакую отмеченную клетку. Противоречие.
    `2` случай: пусть отмечена центральная клетка.
    Тогда также можно задать точные места или области для остальных клеток и получить противоречие в левом квадрате.
    Итак, при `k=9` всегда есть уголок, который не задевает ни одну отмеченную клетку.
    Ответ: `10`.

    Задача №1 (вариант 2).
    При каком наименьшем `k` можно отметить `k` клеток доски `9`х`9` так, что при любом размещении на доске трехклеточного уголка он задевает хотя бы две отмеченные клетки?
    Решение:
    image
    Поскольку мы рассматриваем все возможные размещения уголка на доске, то поместим его последовательно в `4` угла доски, как показано на рисунке `1`. Тогда чтобы при этих размещениях уголка он задевал не менее двух отмеченных клеток, необходимо чтобы в кажой из заштрихованных зон I,II,III и IV находилось не менее чем по две отмеченные клетки. Получили что `k` не меньше `8`.
    Теперь разместим уголок как показано на рисунке `2`.
    Если отмеченные ни одной отмеченной клетки не стоит на пересечении зоны I и V(VI), то в зоне V(VI) нужно отметить еще `2` клетки.
    Если на пересечении зоны I и зоны V отмечена `1` клетка, на пересечении зоны I и зоны VI отмечена `1` клетка, то нам придется как минимум отметить либо еще одну клетку на пересечении зоны V и VI, либо отметить по одной клетке в зонах V и VI.
    Тогда рассматривая эту ситуацию для каждого угла доски, получим что нам придется отметить не менее `4` дополнительных клеток.
    Значит `k` не меньше `12`.
    Покажем, что `12` отмеченных клеток будет достаточно.
    Отметим клетки как показано на рисунке `3`, тогда легко видеть, что как бы мы не располагали уголок - он всегда будет задевать не менее двух отмеченных клеток `=> k=12`.
    Ответ: `k=12`.

    Задача №1 (вариант 4).
    При каком наименьшем `k` можно так отметить `k` клеток доски `8`х`9` так, что при любом размещении на доске четырехклеточной фигурки (см. файл с фото варианта) она задевает хотя бы одну отмеченную клетку? (Фигурку можно поворачивать и переворачивать.)
    Решение:
    image
    Поскольку мы рассматриваем все возможные размещения фигуры на доске, то поместим ее последовательно в `4` угла доски, как показано на рисунке `1`. Тогда чтобы при этих размещениях фигуры она задевала не менее одной отмеченной клетки, необходимо чтобы в кажой из заштрихованных зон I,II,III и IV находилось не менее чем по одной отмеченной клетке.
    Покажем, что четырех отмеченных клеток будет достаточно.
    Отметим клетки как показано на рисунке 2, тогда легко видеть, что как бы мы не располагали фигуру - она всегда будет задевать не менее одной клетка `=> k=4`.
    Ответ: `k=4`.
  • Задача №1 (вариант 5).
    В клетках доски `10`х`10` расставлены числа `1,2,3,...,100` так, что сумма чисел, расположенных в любом квадратике `2`х`2`, не превосходит `S`. Найдите наименьшее возможное значение `S`.
    Решение:
    Сумма всех чисел равна `(1+2+...+100)=(100*101)/2=50*101`.
    Разобьем доску на `25` квадратиков `2`х`2`. По принципу Дирихле, сумма чисел хотя бы в одном квадратике не меньше `(50*101)/25=202`.
    Следовательно, `S>=202`.
    Построим пример для `S=202`. Для этого сумма чисел внутри любого квадратика должна равняться `202`.
    Раскрасим доску с шахматном порядке. На клетках одного цвета, начиная с верхнего левого угла, начнем вправо размещать числа `1,2,3,...` .
    Как строка закончится, переходим вниз (на клетку такого же цвета) и идем по следущей строке в обратную сторону. Таким образом, змейкой выпишем все числа от `1` до `50`.
    На клетках другого цвета, начиная с верхнего правого угла, начнем влево размещать числа `100,99,98,...` . Принцип аналогичный.
    Получим следующую таблицу.
    image
    Сумма одного из квадратиков равна `202`.
    Сумма следующего (вправо-влево) квадратика останется такой же, поскольку два элемента остались такими же, один элемент увеличился на `1`, а другой уменьшился на `1`.
    Сумма следующего (вниз-верх) квадратика также осталась неизменной, поскольку два элемента остались такими же, один элемент увеличился на `11`, а другой уменьшился на `11`.
    Значит, сумма любого квадратика равна `202`.
    Ответ: `202`.

    Задача №2 (вариант 5).
    Даны числа `a,b,c,d,e,f`, причем `b^2<=ac`. Докажите неравенство `(af-cd)^2>=(ae-bd)*(bf-ce)`.
    Решение:
    Рассмотрим выражение `F=(af-cd)^2-(ae-bd)*(bf-ce)`.
    Замена, `ae-bd=x, bf-ce=y`.
    `F*b^2=(abf-bcd)^2-xy`.
    Заметим, что `xc+ya=aec-bdc+abf-aec=abf-bdc`.
    Значит, `F*b^2=(xc+ya)^2-b^2xy`.
    Пусть `xy<0 => -b^2xy>=0 => b^2*F>=0`.
    Пусть `xy>0 => b^2xy<=acxy`.
    Значит, `b^2*F>=(xc+ya)^2-acxy=x^2c^2+acxy+y^2a^2`.
    `x^2c^2+acxy+y^2a^2=1/2(xc+ya)^2+1/2(x^2c^2+y^2a^2)>=0`.
    Следовательно, `b^2*F>=0 => F>=0`, что и требовалось доказать.
    В условии могут быть неточности, но алгоритм сохраняется. Сомножители правой части обозначаем через `x,y`, тогда выражение внутри квадрата левой части будет равно `1/b*(xc+ya)`.
    Ответ: доказано.

    Задача №3 (вариант 5).

    Дан остроугольный треугольник `ABC`. На продолжении стороны `BC` выбрана точка `D` так, что прямая `AD` - касательная к описанной окружности omega треугольника `ABC`. Прямая `AC` пересекает описанную окружность треугольника `ABD` в точке `E`. Оказалось, что биссектриса `/_ADE` касается окружности `omega`. В каком отношении точка `C` делит отрезок `AE`?
    Решение:
    В условии не хватает данных по треугольнику `ABC`. Скорее всего даны углы или иные условия, например, отношение сторон.
    Решение будет почти идентично решениям третьих задач первого и второго вариантов.
    Возможно, что уточним условие и выложим решение, но скорее всего нет.

    Задача №4 (вариант 5).

    В школе `920` учеников, причем в каждом классе не более `k` учеников. На автобусную экскурсию было заказано `16` автобусов, по `71` мест в каждом. При каком наибольшем `k` гарантированно можно разместить людей по автобусом так, чтобы ученики одного класса были в одном автобусе?
    Решение:
    Пусть `k=18`. `51` класс по `18` учеников дают `918` учеников. В последнем классе `2` ученика.
    В каждый автобус можно разместить только три класса по `18` учеников (`4*18>71`). Тогда потребуется `51/3=17` автобусов для размещения всех учеников (последний класс можно посадить в любой автобус).
    Следовательно, при `k=18` нельзя гарантированно рассадить всех учеников согласно условиям задачи (целыми классами).
    При `k>=19` подойдет такой же контрпример.
    Пусть `k<=17`. В каждый автобус можно разместить не менее четырех классов (`4*17<71`).
    Всего `16` автобусов, поэтому если общее количество классов не превосходит `16*4=64`, то учеников всегда можно разместить классами.
    Пусть в школе больше `64` классов. Все классы упорядочили по убыванию численности учеников и начали рассаживать в автобусы, начиная с самых больших классов.
    Предположим, что некоторый класс не поместился целиком. Понятно, что его номер `65` или больше, а первые `64` классов заведомо поместились.
    Следовательно, численность учеников этого класса превосходит количество пустых мест в любом автобусе.
    Всего пустых мест не менее `16*71-920=216`. Автобусов `16`, поэтому есть автобус, в котором не меньше `[216/16]+1=14` свободных мест.
    Значит, число учеников этого класса не меньше `15`. Число учеников любого из первых `64` классов также не меньше `15`.
    Тогда, `920>=65*15=975` - противоречие.
    Итак, при `k<=17` всегда можно разместить всех учеников целыми классами.
    Ответ: `k=17`.

    Задача №5 (вариант 5).
    Дано натуральное число `x=5^n-1`, где `n` - натуральное число. Известно, что `x` имеет ровно три различных простых делителя, один из которых равен `11`. Найдите `x`.
    Решение:
    Заметим, что `5^5-1=25*125-1=(22+3)(121+4)-1` дает остаток `12-1=11` (или `0`) при делении на `11`.
    `n=5k+d => 5^n-1=(5^5)^k*5^d-1` дает остаток `5^d-1` при делении на `11`. Подходит только `d=0`.
    Итак, `n=5k`, где `k in NN`.
    Тогда, `5^n-1 vdots 5^5-1=3124=11*284=2^2*11*71`.
    По условию, `x` имеет ровно три различных делителя, поэтому `x=2^a*11^b*71^c`, где `a,b,c in NN`, причем `a>=2`.
    `x=(5^k-1)(5^(4k)+5^(3k)+5^(2k)+5^k+1)`.
    Заметим, что выражение во второй скобке нечетно, как сумма `5` нечетных чисел.
    Значит, `5^k-1 vdots 2^a`.
    Пусть `5^k` дает остаток `1` при делении на простое число `p`.
    Тогда, выражение во второй скобке дает остаток `5` при делении на `p`. Следовательно, если `p!=5`, то сомножители не имеют общих делителей.
    Пусть `5^k-1 vdots 11 => 5^(4k)+5^(3k)+5^(2k)+5^k+1=71^c`, иначе это выражение равно `1`, чего не может быть.
    По доказаному ранее, `k vdots 5 => 5^k-1 vdots 5^5-1 vdots 71`, противоречие.
    Пусть `5^k-1 vdots 71 => 5^(4k)+5^(3k)+5^(2k)+5^k+1=11^b`.
    `5^5-1 vdots 71`, перебором остатков показываем, что `k vdots 5`, тогда `5^k-1 vdots 11`, противоречие.
    Следовательно, `5^k-1=2^a, 5^(4k)+5^(3k)+5^(2k)+5^k+1=11^b*71^c`.
    `a=2 => k=1, x=5^5-1=3124`.
    Пусть `a>=3 => 5^k-1 vdots 8`.
    При нечетном k выражение `5^k-1` дает остаток `5-1=4` при делении на `4`.
    `k=2m => (5^m-1)(5^m+1)=2^a`.
    `5^m-1=2^(a_1), 5^m+1=2^(a_2) => 2^(a_2)-2^(a_1)=2`.
    `a_2=2, a_1=1` - решений нет.
    Итак, единственное решение `x=3124`.
    Ответ: `x=3124`.
  • Вариант 5.

    Задача №1.
    В клетках доски `10`х`10` расставлены числа `1,2,3,...,100` так, что сумма чисел, расположенных в любом квадратике `2`х`2`, не превосходит `S`. Найдите наименьшее возможное значение `S`.

    Задача №2.
    Даны числа `a,b,c,d,e,f`, причем `b^2<=ac`. Докажите неравенство `(af-cd)^2>=(ae-bd)*(bf-ce)`.

    Задача №3.
    Дан остроугольный треугольник `ABC`, где `/_ABC=alpha`. На продолжении стороны `BC` выбрана точка `D` так, что прямая `AD` - касательная к описанной окружности omega треугольника `ABC`. Прямая `AC` пересекает описанную окружность треугольника `ABD` в точке `E`. Оказалось, что биссектриса `/_ADE` касается окружности `omega`. В каком отношении точка `C` делит отрезок `AE`?

    Задача №4.
    В школе `920` учеников, причем в каждом классе не более `k` учеников. На автобусную экскурсию было заказано `16` автобусов, по `71` мест в каждом. При каком наибольшем `k` гарантированно можно разместить людей по автобусом так, чтобы ученики одного класса были в одном автобусе?

    Задача №5.
    Дано натуральное число `x=5^n-1`, где `n` - натуральное число. Известно, что `x` имеет ровно три различных простых делителя, один из которых равен `11`. Найдите `x`.

    Задача №6.
    Три конуса с вершиной в точке `A` касаются друг друга внешним образом. Два из них одинаковы и имеют угол при вершине `pi/6`. Каждый из трех конусов касается внешним образом четвертого в точке `A`, с углом при вершине `pi/3`. Найти угол при вершине третьего конуса.
  • Задача №1 (вариант 8).
    Петя с Васей играют в следующую игру. Петя отмечает `k` клеток доски `13`x`13`, после чего Вася кладет на доску прямоугольник `1`х`6` и сообщает Пете, какие из отмеченных клеток он накрыл (прямоугольник можно поворачивать). Вася выигрывает, если Петя не сможет однозначно определить положение прямоугольника. При каком наименьшем `k` Петя может так отметить клетки, что Васе не удастся выиграть?
    Решение:
    Рассмотрим одну из плиток и сдвинем её на одну клетку вдоль того направления, в котором она лежит.
    Если окажется, что набор отмеченных клеток, накрываемых плиткой, не изменился, то Вася выигрывает.
    Значит, Петя должен отметить хотя бы одну из двух клеток, расстояние между которыми вдоль линии равно `6`.
    Из этого следует, что в каждой строке должно быть отмечено не менее `6` клеток. Кроме того, в `1`-й и `7`-й строке в сумме должно быть отмечено не менее `13` клеток.
    Действительно, если `j`-я клетка 1-й строки не отмечена, то отмечена `j`-я клетка `7`-й строки.
    То же самое верно для `2`-й и `8`-й строк, ... , для `6`-й и `12`-й.
    Это даёт не менее `13`х`6=78` отмеченных клеток, и вместе с шестью из `13`-й строки получается не менее `84` (это почти половина от общего числа).
    Остаётся построить пример с таким количеством клеток. Его проще описать словесно. Проверка там достаточно очевидная.
    Рассмотрим множество `X={2,4,6,7,9,11}`. Пусть `Y={1,3,5,8,10,12,13}` - его дополнение.
    Оба множества обладают тем свойством, что из чисел вида `i;i+6` в пределах от `1` до `13`, хотя бы одно принадлежит как `X`, так и `Y`.
    Таблица будет симметрична относительно главной диагонали, а числа в строках или столбцах отмечаются или по типу `X`, или по типу `Y`.
    Правило такое: если номер строки принадлежит `X`, то отмечаем её клетки с номерами из `Y`, и наоборот.
    Легко проверить, что при этом получается именно `84` клетки, а положение любой плитки однозначно определяется теми отмеченными элементами, которые она накрывает. Это прямо следует из описанных выше свойств.
    Ответ: `84`.

    Задача №1 (вариант 7).
    Петя с Васей играют в следующую игру. Петя отмечает `k` клеток доски `9`x`9`, после чего Вася кладет на доску прямоугольник `1`х`4` и сообщает Пете, какие из отмеченных клеток он накрыл (прямоугольник можно поворачивать). Вася выигрывает, если Петя не сможет однозначно определить положение прямоугольника. При каком наименьшем `k` Петя может так отметить клетки, что Васе не удастся выиграть?
    Решение:
    Рассмотрим одну из плиток и сдвинем её на одну клетку вдоль того направления, в котором она лежит.
    Если окажется, что набор отмеченных клеток, накрываемых плиткой, не изменился, то Вася выигрывает.
    Значит, Петя должен отметить хотя бы одну из двух клеток, расстояние между которыми вдоль линии равно `4`.
    Из этого следует, что в каждой строке должно быть отмечено не менее `4` клеток. Кроме того, в `1`-й и `5`-й строке в сумме должно быть отмечено не менее `9` клеток.
    Действительно, если `j`-я клетка 1-й строки не отмечена, то отмечена `j`-я клетка `5`-й строки.
    То же самое верно для `2`-й и `6`-й строк, ... , для `4`-й и `8`-й.
    Это даёт не менее `9`х`4=36` отмеченных клеток, и вместе с четырьмя из `9`-й строки получается не менее `40` (это почти половина от общего числа).
    Остаётся построить пример с таким количеством клеток. Его проще описать словесно. Проверка там достаточно очевидная.
    Рассмотрим множество `X={2,4,5,7}`. Пусть `Y={1,3,6,8,9}` - его дополнение.
    Оба множества обладают тем свойством, что из чисел вида `i;i+4` в пределах от `1` до `9`, хотя бы одно принадлежит как `X`, так и `Y`.
    Таблица будет симметрична относительно главной диагонали, а числа в строках или столбцах отмечаются или по типу `X`, или по типу `Y`.
    Правило такое: если номер строки принадлежит `X`, то отмечаем её клетки с номерами из `Y`, и наоборот.
    Легко проверить, что при этом получается именно `40` клеток, а положение любой плитки однозначно определяется теми отмеченными элементами, которые она накрывает. Это прямо следует из описанных выше свойств.
    Ответ: `40`.

Рассылка решений заочных туров олимпиад по математике