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

[prrrr]

arseniiv
Спасибо за отличную идею! Не уверен, что правильно, но пока родилось такое решение:


Пусть гири разложены по двум группам, обозначенным А и Б. Пусть в группе А $m$ гирь, причем $n\geqslant m\geqslant2$, тогда в группе Б будет $n-m$ гирь. Запомним, что веса гирь представляют собой последовательность натуральных чисел от $1$ до $n$.

Рассмотрим вариант, когда $m=2$. Тогда в группе Б будет $n-2$ гири. Пусть гиря максимального веса $n$ также будет в группе А, тогда вторая гиря в группе А может иметь вес от $1$ до $n-1$, обозначим его $k$.
Рассмотрим три варианта: $k=1$, $k=n-1$ и $n-2\geqslant k\geqslant2$.
1. $k=1$. Тогда гири в группе Б могут иметь вес от $2$ до $n-1$. Значит в группе Б точно находятся гири с весом $2$ и $n-2$, суммарный вес которых равен $n$.
2. $k=n-1$. Тогда гири в группе Б могут иметь вес от $1$ до $n-2$. Значит, аналогично пункту 1, в группе Б точно находятся гири с весом 2 и n-2, суммарный вес которых равен $n$.
3. $n-2\geqslant k\geqslant2$. В этом случае для любого $k$ в группе Б точно находятся гири с весом $1$ и $n-1$, суммарный вес которых так же равен $n$.

Таким образом мы доказали возможность привести весы в равновесие с помощью гирь из группы А, положенных на одну чашу весов, и гирь из группы Б, положенных на вторую чашу весов.

Теперь рассмотрим случай, когда $m>2$.
Чтобы доказать возможность привести весы в равновесие, мы можем воспользоваться способом описанным выше. Для этого нам нужно будет привести группы гирь А и Б в вид, когда гиря с максимальным весом находится в группе, в которой только две гири. Для этого отложим в сторону последовательно по одной гире, начиная с максимального веса $n$, затем $n-1$, $n-2$ и т.д. до тех пор, пока в одной из групп (пусть это будет группа А) не останется только две гири, одна из которых будет иметь максимальный вес из оставшихся в группах А и Б. Обозначим вес этой гири как $p$, тогда все оставшиеся гири будут иметь вес от $1$ до $p$.

Воспользовавшись рассуждениями, приведенными выше, учитывая, что вторая гиря в группе А может иметь вес от $1$ до $p-1$, рассмотрим варианты веса второй гири $l=1$, $l=p-1$, $p-2\geqslant l\geqslant2$. Получим аналогичное приведенному выше доказательство возможности привести весы в равновесие.

Аналогичным способом можно доказать возможность привести весы в равновесие, когда в одной из групп (например группе А) находятся 2 гири, но гиря максимального веса $n$ находится в другой группе Б.

[EUgeneUS]

prrrr
Доказательство неполное, а значит неверное.
Пропущен важный специальный случай.

Вам уже на него указывали. Вот тут:

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

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

[prrrr]

EUgeneUS в сообщении #1507573 писал(а):

prrrr
Доказательство неполное, а значит неверное.
Пропущен важный специальный случай.

Вам уже на него указывали. Вот тут:

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

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

Подскажите пожалуйста, это же следует из условия задачи?
Ведь веса гирь представляют собой последовательный ряд натуральных чисел $1, 2, 3, 4, .... n$. Очевидно, что эти числа попарно различны. Следовательно, если в группе слева две гири весом $n$ и $1$, то в правой группе будет $n-2$ гирь весом от $2$ до $n-1$, а значит в правой группе будут гири весом $2$ и $n-2$. Аналогично для веса $n-1$.

[EUgeneUS]

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

Подскажите пожалуйста, это же следует из условия задачи?

Из условия задачи следует, что веса всех гирь попарно различны. Это требование.
А из Вашего построения отнюдь не следует, что четыре важных значения $\left\lbrace1, 2, n-1, n-2\right\rbrace$ будут попарно различны.

[prrrr]

EUgeneUS в сообщении #1507585 писал(а):

Из условия задачи следует, что веса всех гирь попарно различны. Это требование.
А из Вашего построения отнюдь не следует, что четыре важных значения $\left\lbrace1, 2, n-1, n-2\right\rbrace$ будут попарно различны.

Минимальное $n$ (при котором выполняется условие о том, что в каждой группе не меньше двух гирь) равно $4$. Следовательно, в этом случае, попарно различными будут числа $\left\lbrace1, 2, n-1, n\right\rbrace$.
Числа $\left\lbrace1, 2, n-1, n-2\right\rbrace$ будут попарно различны для любого $n\geqslant5$, так как веса всех гирь представляют собой непрерывный последовательный ряд натуральных чисел $N$ от $1$ до $n$ в котором каждое последующее число образовано прибавлением $1$: $N_{i+1}=N_{i}+1$ .

[prrrr]

Действительно, $n=4$ - это особый случай.. Получается вот такое решение.

Пусть гири разложены по двум группам, обозначенным А и Б. Пусть в группе А $m$ гирь, причем $n\geqslant m\geqslant2$, тогда в группе Б будет $n-m$ гирь. Запомним, что веса гирь представляют собой непрерывную последовательность попарно различных натуральных чисел от $1$ до $n$ (обозначим ее $N$), в которой $N_{1}=1$, а каждое следующее $N_{i+1}=N_{i}+1$ и так до $N_{n}=n$.

Рассмотрим вариант, когда $m=2$ и $n\geqslant5$. Тогда в группе Б будет $n-2$ гирь различного веса. Пусть гиря максимального веса $n$ также будет в группе А, тогда вторая гиря в группе А может иметь вес от $1$ до $n-1$, обозначим его $k$.
Рассмотрим три варианта: $k=1$, $k=n-1$ и $n-2\geqslant k\geqslant2$.

1. $k=1$. Тогда в группе Б будут находится $n-2$ гирь различного веса от $2$ до $n-1$. Следовательно, так как веса всех гирь в группах А и Б представляют собой непрерывное множество попарно различных натуральных чисел от $1$ до $n$, в группе Б точно находятся гири с весом $2$ и $n-2$, это будут разные гири, суммарный вес которых равен $n$.
2. $k=n-1$. Тогда в группе Б будут все гири весом от $1$ до $n-2$. Следовательно, аналогично пункту 1, в группе Б точно находятся различные гири с весом $2$ и $n-2$, суммарный вес которых равен $n$.
3. $n-2\geqslant k\geqslant2$. В этом случае для любого $k$ в группе Б точно находятся две различные гири с весом $1$ и $n-1$, суммарный вес которых так же равен $n$.

Веса гирь $\left\lbrace1, 2, n-1, n-2\right\rbrace$ будут попарно различны для любого $n\geqslant5$ и, следовательно, мы сможем разместить на весах различные гири.

Однако, условиям задачи также удовлетворяет значение $n=4$. В этом случае, в группах А и Б будет по две гири и попарно различными будут веса гирь $\left\lbrace1, 2, n-1=3, n=4\right\rbrace$. При этом:
1. Если в одну группу А с гирей весом $n=4$ попадает гиря весом $1$, то в группе Б будут гири с весом $2$ и $n-1=3$ и суммарный вес гирь в группе А будет равен суммарному весу гирь в группе Б и равен $n+1=5$.
2. Если в одну группу А с гирей весом $n=4$ попадает гиря весом $n-1=3$, то в группе Б будут гири с весом $1$ и $2$. Сумма гирь в группе Б будет равна $1+2=3$ и равна весу гири $n-1=3$ в группе А.
3. Если в одну группу А с гирей весом $n=4$ попадает гиря весом $n-2=2$, то в группе Б будут гири с весом $1$ и $n-1=3$ и суммарный вес гирь в группе Б будет равен $1+(n-1)$ и равен весу гири $n$ из группы А.

Таким образом мы доказали возможность привести весы в равновесие с помощью гирь из группы А, положенных на одну чашу весов, и гирь из группы Б, положенных на вторую чашу весов в случае, когда в одной из групп находится только две гири и гиря максимального веса $n$.

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

Теперь рассмотрим случай, когда $m>2$.
Чтобы доказать возможность привести весы в равновесие, мы можем воспользоваться способом описанным выше. Для этого нам нужно будет привести группы гирь А и Б в вид, когда гиря с максимальным весом находится в группе, в которой только две гири. Для этого отложим в сторону последовательно по одной гире, начиная с максимального веса $n$, затем $n-1$, $n-2$ и т.д. до тех пор, пока в одной из групп (пусть это будет группа А) не останется только две гири, одна из которых будет иметь максимальный вес из оставшихся в группах А и Б. Обозначим вес этой гири как $p$, тогда все оставшиеся гири будут иметь вес от $1$ до $p$.

Воспользовавшись рассуждениями, приведенными выше, учитывая, что вторая гиря в группе А может иметь вес от $1$ до $p-1$, рассмотрим варианты веса второй гири $l=1$, $l=p-1$, $p-2\geqslant l\geqslant2$. Получим аналогичное приведенному выше доказательство возможности привести весы в равновесие.

Аналогичным способом можно доказать возможность привести весы в равновесие, когда в одной из групп (например группе А) находятся 2 гири, но гиря максимального веса $n$ находится в другой группе Б.

[mihaild]

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

Рассмотрим вариант, когда $m=2$ и $n\geqslant5$. Тогда в группе Б будет $n-2$ гирь различного веса. Пусть гиря максимального веса $n$ также будет в группе А

Вот так писать не очень хорошо - лучше явно написать, что рассматриваем вариант $m = 2$ и самая тяжелая гиря в А, и потом не забыть про вариант $m = 2$ и самая тяжелая в Б.
Но на самом деле это и не нужно, лучше сразу объявить группой А ту, в которой самая тяжелая гиря.

[EUgeneUS]

prrrr
ИМХО, проще рассмотреть случай $n=4$ отдельно и просто выписать все варианты. Их не много, с учетом симметрии всего три:
1. $\left\lbrace 4, 1 \right\rbrace$, $\left\lbrace 2, 3\right\rbrace$ - уравновешиваются целиком пары
2. $\left\lbrace 4, 2 \right\rbrace$, $\left\lbrace 3, 1\right\rbrace$ - уравновешивается $4$ парой $\left\lbrace 3, 1\right\rbrace$
3. $\left\lbrace 4, 3 \right\rbrace$, $\left\lbrace 2, 1\right\rbrace$ - уравновешивается $3$ парой $\left\lbrace 2, 1\right\rbrace$

Итого, убирая на каждом шаге самую тяжелую гирю, мы обязательно придем к одному из таких вариантов:

а) Самая тяжелая гиря в группе, где ровно две гири. В другой группе более двух гирь. Достигли при $n>4$.
б) Самая тяжелая гиря в группе, где ровно две гири. В другой группе тоже ровно две гири. Достигли при $n=4$.

[prrrr]

EUgeneUS
mihaild

Да, Вы правы так намного элегантнее! У меня конечно очень громоздкая конструкция получилась..
Спасибо большое!

[marie-la]

Я бы строила так: 1 в какой-то группе. В ней обязательно есть еще какое-то $k$. Возьмем минимальное из $k\ne 1$ в этой группе. Пытаясь построить такое разбиение, когда уравновешивание невозможно, получаем, что в этой же группе и $k+1, k+2, ..., n$. А во второй группе, соответственно, $2, 3, ..., k-1$ - не меньше двух чисел при этом. Ну и там еще чуть-чуть - и составится равновесие.

[prrrr]

marie-la
Интересный вариант рассуждений, спасибо!