Задача о гирях

[prrrr]

Даны $n$ гирь, веса которых равны $1, 2, …, n$. Их разделили на две группы так, что в каждой группе оказалось больше одной гири. Докажите, что можно положить на одну чашу весов несколько гирь из первой группы, а на другую чашу - несколько гирь из второй группы так, чтобы весы оказались в равновесии.

Пока решение было таким:
Так как в каждой группе не меньше одной гири, то ситуация при которой нельзя уравновесить весы (в одной из групп только одна гиря весом 1 или весом 2) невозможна.
При этом в каждой из групп может быть от $2$ до $(n-2)$ гирь, и гири с весом 1 и 2 будут находится в одной из групп или в разных группах .
Поэтому всегда можно выбрать как минимум одну гирю весом k в одной группе, которая будет уравновешена гирями из другой группы. А именно:
$1+(k-1)$, если $k$ - нечетное и $2+(k-2)$, если $k$ - чётное.

Это решение не верное, дальше застрял на том, что вес любой гири описывается как:
$1+2t$ для гирь нечетного веса ($t=0, 1, 2, 3, ..., \frac {(n-1)} {2}$).
$2+2t$ для гирь четного веса ($t=0, 1, 2, 3, ..., \frac {(n-2)} {2}$).

Куда двигаться дальше не понимаю. Помогите пожалуйста, всю голову уже сломал..

[EUgeneUS]

0. Формулы тут принято набирать в LaTeX

1. Что значит "несколько"?

2. Если "несколько" - это строго больше одного, то утверждение просто неверное. Контрпример строится моментально (постройте его).
3. Если "несколько" - это один или больше. То начните раскладывать числа по двум кучкам, начиная с $n=4$. На каждом шаге добавляется следующее число, и вычеркиваются запрещенные комбинации. Очень быстро обнаружится закономерность, из которой получится доказательство.

[arseniiv]

prrrr в сообщении #1507219 писал(а):

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

Почему это? Нам разрешено положить сколько угодно (только не ноль) гирь из каждой группы, так что мы кладём 1 и 2 на одну чашу, а на другую чашу кладём 3, которая обязательно должна быть в другой группе, если в первой только 1 и 2.

[Pphantom]

Тема перемещена из форума «Олимпиадные задачи (М)» в форум «Карантин»
по следующим причинам:

- неправильно набраны формулы (краткие инструкции: «Краткий FAQ по тегу [math]» и видеоролик Как записывать формулы);
- отсутствуют собственные содержательные попытки решения задачи.

Исправьте все Ваши ошибки и сообщите об этом в теме Сообщение в карантине исправлено.
Настоятельно рекомендуется ознакомиться с темами Что такое карантин и что нужно делать, чтобы там оказаться и Правила научного форума.

[Pphantom]

Тема перемещена из форума «Карантин» в форум «Помогите решить / разобраться (М)»

[mihaild]

Что-то непонятное, что такое $k$? И да, определение четного и нечетного числа вы написали правильно, но как это связано с задачей?

Попробуйте свести всё к случаю когда группа, содержащая самую тяжелую гирю, состоит всего из двух гирь, и посмотреть, как уравновесить в таком случае.

[prrrr]

$k$ это вес некой случайной гири в первой или второй группе.
Я пробовал подойти с точки зрения того, что известно достоверно:
- гиря максимального веса $n$ принадлежит к первой или второй группе;
- общее количество разниц весов равно $n-1$;
- общее количество гирь в каждой группе может быть от $2$ до $n-2$;
- общий вес гирь равен: $\frac{n(n+1)}{2}$.

Может быть подойти со стороны что количество способов распределить гири по группам $\leqslant\frac{n(n-1)}{2}$?

-- 02.03.2021, 16:20 --

mihaild в сообщении #1507397 писал(а):

Попробуйте свести всё к случаю когда группа, содержащая самую тяжелую гирю, состоит всего из двух гирь, и посмотреть, как уравновесить в таком случае.

Пробовал, но получается частный случай, когда эта гиря весом $n$ равна по весу гирям $1+(n-1), 2+(n-2), 3+(n-3)$ и т.д. в зависимости от того, какая гиря вторая в группе, содержащей самую тяжёлую гирю.

[mihaild]

Может быть можно что-то сообразить из числа способов (делим гири слева и справа на две группы, смотрим что там с разницами весов), но выглядит сложно.
Вы можете привести решение для случая, когда слева гиря $n$ и еще какая-то, а справа все остальные?

[arseniiv]

prrrr
Вот да, попробуйте подход скромности: искать наименьшие решения, искать их начиная с малого и не пытаться искать решение, представив всё множество возможных разбиений на группы (иногда это полезно, но раз вам ничего в данном случае не видно сразу, стоит отложить это занятие и подойти с других сторон). Вот я уже дал решение для четырёх гирь, попробуйте свести решение для $n + 1$ гири к какому-нибудь решению для $n$ гирь. mihaild то же самое пишет (и EUgeneUS, но я его с первого раза не понял), и самый хитрый случай тут именно когда тяжёлая гиря лежит в группе со всего одной другой гирей — тогда нам не свести к случаю $n$ гирь.

[prrrr]

Если слева гиря $n$, то второй гирей слева может быть гиря с весом от $1$ до $n-1$. Число возможных вариантов $n-1$.
В этом случае решение отличается только для варианта когда второй гирей слева будет гиря с весом $1$ или гиря с весом $n-1$. В этом случае гиря $n$ слева будет в равновесии с гирями весом $2+(n-2)$ справа.
В остальных случаях гиря весом $n$ слева будет в равновесии с гирями весом $1+(n-1)$ справа.

Получается такое решение для только двух гирь слева при условии, что гиря весом $n$ находится в этой группе.

[mihaild]

prrrr в сообщении #1507433 писал(а):

Если слева гиря $n$

prrrr в сообщении #1507433 писал(а):

слева лежит гиря с весом $1$ и с весом $n-1$

Как может быть слева две гири, при этом слева быть гири $n$, $1$ и $n - 1$?

prrrr в сообщении #1507433 писал(а):

гиря $n$ слева будет в равновесии с гирями весом $1+(n-2)$ справа

Это как?

[prrrr]

mihaild в сообщении #1507436 писал(а):

prrrr в сообщении #1507433 писал(а):

Если слева гиря $n$

prrrr в сообщении #1507433 писал(а):

слева лежит гиря с весом $1$ и с весом $n-1$

Как может быть слева две гири, при этом слева быть гири $n$, $1$ и $n - 1$?

prrrr в сообщении #1507433 писал(а):

гиря $n$ слева будет в равновесии с гирями весом $1+(n-2)$ справа

Это как?

Поправил опечатки, прошу прощения, не доглядел((

[mihaild]

Так лучше, но всё еще не совсем достаточно. Нужно показать, что если слева есть гиря с весом $1$ или $n - 1$, то справа есть гири с весами $2$ и $n - 2$, причем эти гири различные (нельзя же одну гирю положить два раза).

Пусть теперь в группе с самой тяжелой гирей больше двух гирь. Как этот случай свести к меньшему числу гирь?

[prrrr]

mihaild в сообщении #1507441 писал(а):

Так лучше, но всё еще не совсем достаточно. Нужно показать, что если слева есть гиря с весом $1$ или $n - 1$, то справа есть гири с весами $2$ и $n - 2$, причем эти гири различные (нельзя же одну гирю положить два раза).

Если слева гиря $n$, то второй гирей слева может быть гиря с весом от $1$ до $n-1$. Число возможных вариантов $n-1$.
В этом случае решение отличается только для варианта когда второй гирей слева будет гиря с весом $1$ или гиря с весом $n-1$. Так как веса гирь представляют собой последовательность натеральных чисел от $1$ до $n$, то имея слева гири весом $1$ и $n$ справа имеем гири с весом от $2$ до $n-1$. В этом случае гиря $n$ слева будет в равновесии с гирями весом $2+(n-2)$ справа.
В остальных случаях гиря весом $n$ слева будет в равновесии с гирями весом $1+(n-1)$ справа. Так как слева находятся две гири весом $n$ и произвольное $n-2\geqslant k \geqslant2$.

mihaild в сообщении #1507441 писал(а):

Пусть теперь в группе с самой тяжелой гирей больше двух гирь. Как этот случай свести к меньшему числу гирь?

Напрашивается вариант просуммировать гири с весом меньшим $n$, но тогда получается что-то совсем неправильное..

[arseniiv]

А если вы эту гирю выкинете, то что получится?