Волшебный конструктор.

[PWT]

Здравствуйте! Помогите, пожалуйста, разобраться.

В волшебном конструкторе есть детали массой $5,24,43$ грамма, поровну каждого вида. Все детали взвесили, их масса оказалась равной $606060....60$ грамм. Докажите, что в волшебном конструкторе потеряно более 10 деталей.

Мои идеи. Пусть детали массой $5,24,43$ грамм имеются в наличии в количестве $x,y,z$ соотвественно.

Тогда имеем уравнение $5x+24y+43z=606060...60$

Далее -- делимость будем исследовать.

Поделим обе части уравнения на $5$.

$x+4,8y+8,6z=121212...12$ (1)

Значит $0,8y+0,6z$ есть некое натуральное число, пусть $0,8y+0,6z=n$

Значит $4y+3z=5n$

Уравнение (1) переписывается в виде:

$x+4y+8z+n=121212...12$

Можно смело утверждать, что $x+n$ делится на $4$. $x+n=4m$

Дальше можно смотреть делимость на $3$, но это просто сводится к тому,что начинаются плодится все новые и новые буквы, не более того. Пока иных идей нет, может подскажете, за что можно зацепиться, пожалуйста!

[Sonic86]

PWT в сообщении #1253293 писал(а):

В волшебном конструкторе есть детали массой $5,24,43$ грамма, поровну каждого вида. Все детали взвесили, их масса оказалась равной $606060....60$ грамм. Докажите, что в волшебном конструкторе потеряно более 10 деталей.

PWT в сообщении #1253293 писал(а):

Тогда имеем уравнение $5x+24y+43z=606060...60$

Как-то не так формализовано

PWT в сообщении #1253293 писал(а):

поровну каждого вида

вот это явно не формализовано

PWT в сообщении #1253293 писал(а):

в волшебном конструкторе потеряно более 10 деталей.

а вот как это формализовать, еще подумать надо, но явно какое-то неравенство

[PWT]

Спасибо, хорошо. Попробую формализовать иначе.

Пусть изначально было деталей $x$. Пусть потеряно было $a,b,c$ деталей масс $5,24,43$ грамма соответственно.

Тогда получаем $5(x-a)+24(x-b)+43(x-c)=6060...60$, при этом нужно доказать, что $a+b+c>10$.

Раскрывая скобки, получаем $72x-(5a+24b+43c)=6060...60$

Таким образом, нам известно, что $5a+24b+43c$ кратно 12.

$5a+24b+43c=12n$, тогда $5a+43c$ делится на 12, значит, если $a=1$ и $c=1$, то как минимум две детали потеряно, дальнейший перебор только может увеличить значения а и с.

Нормальная ли формализация и ход решения правильный ли?

[Dmitriy40]

PWT в сообщении #1253327 писал(а):

Пусть изначально было деталей $x$.

Вообще-то удобнее взять что деталей было $3x$ - их ведь поровну каждого вида, а Вы этого так и не учли.

[ewert]

PWT в сообщении #1253327 писал(а):

ход решения правильный ли?

Да как сказать. А почему там вообще хоть что-то потеряно?...

[wrest]

PWT в сообщении #1253293 писал(а):

их масса оказалась равной $606060....60$ грамм.

Значит ли это что масса больше или равна $60606060$ грамм?

На случай $60$ грамм ответ однозначный: такую массу можно составить только из $12$ штук $5$-граммовых деталей, значит потеряно $12$ штук $43$-граммовых и $12$ штук $24$-граммовых, всего потеряно $24$ детали.

[ewert]

wrest в сообщении #1253436 писал(а):

Значит ли это что масса больше или равна $60606060$ грамм?

Это не имеет значения.

Sonic86 в сообщении #1253317 писал(а):

но явно какое-то неравенство

Не надо неравенств.

[PWT]

Хорошо, спасибо. Пусть всех деталей по $x$ штук каждого вида. (я так и имел ввиду во втором посту этой темы, но виноват, что криво выразился). Тогда всего $3x$ деталей. Если бы ничего не потерялось, было бы $5x+24x+43x=6060...60$, то есть $72x=6060...60$, но здесь равенство не может достигаться, ввиду того, что $x$ -- целое число, а правая часть не делится на $72$. Тогда можно сделать вывод, что хотя бы одна деталь потеряна.

Стало быть, что $72x$ больше $6060...60$.

Пусть потеряно $a,b,c$ деталей по 5, 24 и 43 грамма соответственно. Тогда из $72x мы вынуждены вычесть потерянный вес $5a+24b+43c$, чтобы получить $6060...60$.

Но тогда получается, что $72x-(5a+24b+43c)=6060...60$, но это опять я завел свою шарманку. Но я пока не вижу другого пути.

[ewert]

PWT в сообщении #1253526 писал(а):

но здесь равенство не может достигаться, ввиду того, что $x$ -- целое число, а правая часть не делится на $72$.

Совершенно верно. Но тогда немедленно возникает следующий вопрос, неизбежно возникает: а какими могут быть остатки от деления этих шестидесяток на $72$?...

Но после того, как этот вопрос возник -- неизбежно возникает ещё один предварительный: каков период этих остатков по мере наращивания числа шестидесяток?... (он довольно маленький)

[Sonic86]

PWT в сообщении #1253327 писал(а):

Раскрывая скобки, получаем $72x-(5a+24b+43c)=6060...60$

Таким образом, нам известно, что $5a+24b+43c$ кратно 12.

PWT в сообщении #1253526 писал(а):

Но тогда получается, что $72x-(5a+24b+43c)=6060...60$, но это опять я завел свою шарманку. Но я пока не вижу другого пути.

Так Вы же заводите не поломанную, а исправленную шарманку, а это уже хорошо, а не плохо Дальше у Вас на этом пути получится модуль $24$, из него можно получить неравенство посильнее, чем $a+c\geqslant 2$.... хотя и не особо сильнее...

Насчет формализации: вообще это некая задача целочисленной оптимизации в форме распознавания:
$\sum\limits_{j=1}^na_jx_j = N, \sum\limits_{j=2}^nx_j \leqslant B, a_j,x_j \in \mathbb{Z}, x_j \geqslant 0$
Для ее решения есть известные методы (типа такого: https://ru.wikipedia.org/wiki/%D0%90%D0 ... 1%80%D0%B8 (м.б. мы его здесь даже переоткрываем в кустарной форме)), просто они не особо приятные для решения руками вечером после работы.
Ну и геометрически тут можно немного подходить к решению.
Ах, да, ЕМНИП, она еще и $NP$-полная, будьте готовы.

[ewert]

Sonic86 в сообщении #1253531 писал(а):

Для ее решения есть известные методы

Ну к чему тут методы, тем более геометрии всякия, если всё на автомате решается тривиально -- просто по остаткам.

[Sonic86]

(Оффтоп)

ewert в сообщении #1253541 писал(а):

Ну к чему тут методы, тем более геометрии всякия, если всё на автомате решается тривиально -- просто по остаткам.

ИМХО, представлять картину в целом небесполезно в любом случае.

[ewert]

(Оффтоп)

Sonic86 в сообщении #1253544 писал(а):

представлять картину в целом небесполезно в любом случае

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

[PWT]

Спасибо.

Не знаю -- какой будет остаток, но знаю, что он будет кратен 12. Попробую доказать это

$6060...60=72n+r$, тогда $r=6060...60-72n=12(5050...05-6n)$.

Потенциально возможные значения для остатка, проверил для нескольких первых шестидесяток: $12,24,60$, интересно, что $36, 48$ не встречалось почему-то.

Но ведь из этого не следует, что минимум 12 деталей потерялись?

[ewert]

PWT в сообщении #1253550 писал(а):

Потенциально возможные значения для остатка, проверил для нескольких первых шестидесяток: $12,24,60$, интересно, что $36, 48$ не встречалось почему-то.

Интересно, что первые три остатка не совсем верны, и два последних -- аналогично. А это существенно для дальнейшего.

PWT в сообщении #1253550 писал(а):

Но ведь из этого не следует, что минимум 12 деталей потерялись?

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

А этот случай со случаем совпадения тех коэффициентов всё равно придётся различать.

-- Пт окт 06, 2017 00:18:52 --

(имелась в виду неверность утверждения об остатках, а не о 12-ти)