XXXIV Турнир Городов

[Ktina]

Уже выкладывали задачи десять дней тому назад состоявшегося Тургора?
Если ещё нет, то вот: http://www.uni.bsu.by/arrangements/imct ... osen34.pdf
Решайте на здоровье!

[arqady]

Странно как-то... Ведь условия задач ещё минимум десять дней не должны быть доступны для общего видения.
Впрочем, Ваша ссылка у меня всё равно не открывается.

[Ktina]

arqady в сообщении #632322 писал(а):

Странно как-то... Ведь условия задач ещё минимум десять дней не должны быть доступны для общего видения.
Впрочем, Ваша ссылка у меня всё равно не открывается.

Ну, во-вторых, как раз десять дней уже прошло (даже 11, я на часы не посмотрела, когда постила, а было уже за полночь). А во-первых, другой ссылки у меня, к сожалению, пока нет. Если найду, добавлю.

[longstreet]

Ссылка работает.

[Naf2000]

8-9 класс. задача 3.

(Оффтоп)

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

[DjD USB]

11 класс 4 а) Довольно простое. Пусть а=5p, b=p, где р простое большее 5 тогда все довольно легко получается. Думаю подобных примеров можно составить много.

[DjD USB]

Глухо здесь, как в танке...

[diwert]

DjD USB в сообщении #632894 писал(а):

11 класс 4 а) Довольно простое. Пусть а=5p, b=p, где р простое большее 5 тогда все довольно легко получается. Думаю подобных примеров можно составить много.

4 б) решается почти также, как я понимаю.

Возьмем произведение $P$ первых $n$ простых чисел (примориал вроде называется). Тогда
$P=2\cdot3\cdot5\cdot\ldots\cdot p_n = 1 + Q$. Так как $P$ - это наименьшее натуральное, которое имеет не менее, чем $n$ простых делителей и $Q<P$, то число простых делителей $Q$ меньше, чем $n$. Т.е. разложение на простые множители для $Q$ выглядит так: $Q=q_1^{\alpha_1}\cdot q_2^{\alpha_2}\cdot\ldots\cdot q_m^{\alpha_m}$ и $m<n$. Пусть $n-m=k>0$.

Теперь возьмем $k$ простых чисел $r_i$ таких что: $r_1,r_2,\ldots,r_k \notin$\{2,3,5,\ldots,p_n\}\cup\{q_1,q_2,\ldots,q_m\} и умножим уравнение $P=1+Q$ на число $R=r_1\cdot r_2\cdot\ldots\cdot r_k$. Получаем $RP=R+RQ$, где $c(RP)=c(R)+c(RQ)=n+k$. Т.е. выбрав достаточно большое $n$ можно построить нужую пару чисел a и b, таких что: $c(a+b)>1000$. А бесконечность таких пар вытекает хотя бы из того, что нужные $r_i$ можно выбирать бесконечным количество способов, т.к. множество простых чисел не ограничено (кстати можно брать и одни и те же $r_i$, но в разных степенях)

[DjD USB]

Про монеты в 11 классе, как решить? Какой подход, идея?

[dm]

Сложный вариант http://www.uni.bsu.by/arrangements/imct ... osen34.pdf

[Ktina]

DjD USB в сообщении #633128 писал(а):

Про монеты в 11 классе, как решить? Какой подход, идея?

У меня решение отличается от официального, поэтому, пожалуйста, проверьте на ошибки.

Итак, вешаем 119 и 119, одну оставляем (покамест) в сторонке.

а Если равновесие, берём одну из кучек в 119 и добавляем ту монетку, что оставили в сторонке. Получаем 120 и вешаем 60 и 60. Равновесие теперь невозможно, одна обязательно перетянет. Делим ту, что перетянула, на 2 кучки и вешаем 30 и 30. Если равно, фальшивая легче, если не равно -- тяжелее.

б Если одна кучка перетянула, добавляем к ней ту монетку, что оставили в сторонке.
Получаем 120 и вешаем 60 и 60.

б1 Если равновесие, делим одну из кучек на 2 кучки и вешаем 30 и 30. Если опять равновесие, фальшивая легче. Если нет, тяжелее.

б2 Если одна из кучек в 60 перетянула, берём ту, что не перетянула, делим на 2 и вешаем 30 и 30. Если равновесие, фальшивая тяжелее, если нет -- легче.

[Shadow]

У Вас правильное решение, Ktina.

[hippie]

Ещё одно решение задачи о 239 монетах.


Делим монеты на 3 кучки по 40 монет и одну 119 монет.
За 2 взвешивания сравниваем кучки по 40 (могут быть либо все 3 равного веса; либо 2 равных, а третья отличается).

Если 2 одинаковых легче третьей, то любую из равных делим на две полукучки по 20 монет, и сравниваем полукучки.
Если весят поровну, то равные кучки только из настоящих монет, а в тяжёлой есть фальшивая (тяжелее настоящей).
Если не поровну, то лёгкие кучки содержат по одной фальшивой (более лёгкой) монете, а тяжёлая состоит из настоящих.

Аналогично, если 2 одинаковых кучки тяжелее третьей.
Только теперь если полукучки весят поровну, то фальшивая легче, а если нет, то тяжелее.

Если все 3 кучки по 40 монет равного веса, то обе фальшивые монеты среди оставшихся 119.
Объединяем 40+40+40=120, откладываем одну монету и сравниваем с оставшимися 119.