Математическая задачка

[Анюткин]

Одна моя знакомая попросила помочь с задачкой. Т.к. я не особо сильна в математике, то прошу помощи у вас.

Вот сама задачка:

определить количество целочисленных решений уравнения x+y+z=40
2<=x<=12
9<=y<=18
6<=z<=15

[Рыжик]

Возможно математики предложат более рациональное решение, но я бы на уровне школьной программы решил так.
y и z могут принимать по 10 значений, х - 11. Значит ограничение скорее всего будет по х.
Для простоты принимаем y+z=а. И тогда имеем:
1.
x= 40-a
2<=40-a<=12
28<=a<=38

2.
Сложив второе и третье неравенства, получаем
15<=a<=33

3.
Решив систему неравенств по а, имеем
28<=a<=33
Получили диапазон значений суммы y+z, при которых х находится в заданном диапазоне

4. учитывая, что а= 40 -х, получаем
7<=х<=12

Таким образом имеем шесть значений х, при которых y и z могут принимать любое из десяти заданных значений в зависимости друг от друга.
В итоге уравнение x+y+z=40 имеет 60 целочисленных решений.

[basil0]

Тупой перебор дает 21 решение.
Интересно, что при
х=7 - 1 решение
х=8 - 2
х=9 - 3
х=10 - 4
х=11 - 5
х=12 - 6 решений

[Рыжик]

упс!
малость перемудрил
y и z тоже имеют ограничения по наименьшему значению от 13 до 18 и от 10 до 15, соответственно

[Анюткин]

basil0, а Вы можете написать алгоритм решения?

у подружки получилось то же число, что и у вас (перебором), а как написать алгоритм?

Заранее, спасибо

[molch64]

*перед прочтением моего решения советую выпить некоторое количество (в литрах) водки.

Итак, надо пересечь параллелепипед, заданный неравенствами, плоскостью x+y+z=40. Представили себе этот параллелепипед и плоскость в трехмерном пространстве? Я так смог только минут за 5 когда мозг вскипел

Чтобы представить, какую фигуру плоскость отсекает от параллелепипеда, надо понять, сколько граней из 6 оно пересекает.
Так вот, грань, лежащую в плоскости x=2 наша плоскость не пересекает, т.к. x=2 в нашей системе неравенств при x+y+z=40 быть не может (получается, x+y+z<=2+18+15=35).
Аналогично со всеми "нижними" гранями - итого, плоскость отсекает треугольник "сверху" параллелепипеда. И это хорошо, что получается именно треугольник. Он равносторонний, вида n x n x n, где в узлах лежат целые точки (это примерно, как шарики в равносторонний треугольник n x n x n складывать). Узлов (они же целые точки) - n(n+1)/2, (т.н. треугольное число), осталось найти n.
Для этого возьмем z по максимуму - 15, нужно найти количество целых решений x+y=25, где x<=12, y <=18. (нижние границы, как выяснили ранее, роли не играют) Решив эту штуку, получаем, n=12+18-25 +1 = 6, а общий ответ в задаче - 6*7/2 = 21


Что касаемо алгоритма - тут все зависит от этой фигуры сечения параллелепипеда плоскостью x+y+z=const. В этой задаче это - треугольник. Но это может быть любая фигура от 3х до 6-ти угольника (чем больше - тем сложнее считать). Но общюю формулу в принципе попробовать привести можно, но выпить для этого придется на порядок больше

[basil0]

basil0, а Вы можете написать алгоритм решения?

Понятно, что по сумме двух максимумов можно определить нижнее значение 3-его элемента:
х не меньше 7, у - 13 z - 10,
ну а дальше почти тупой перебор
Увы неравенства в школе я не понимал.

[Atson]

Хочу еще и свой полунаучный метод предложить.
Поскольку z <= 15, x + y >= 25. (нижнее ограничение на z здесь роли не играет, хотя могло бы)
Каждому решению последнего неравенства соответствует единственное значение z. Далее, из полученного неравенства и ограничения на x получаем ограничение снизу на y и наоборот. Получаем систему:
x + y >= 25
7 <= x <= 12
13 <= y <= 18
Выясним, сколько значений y соответствует каждому из целочисленных значений x (всего их 6). Для x = 7 только 1 значение y = 18, для x = 8 - два значения y = 18, 17 и т.д.
1 + 2 + 3 + 4 + 5 + 6 = 21 целочисленное решение.

[Dendr]

Раз уж пошло, так сказать, "соревнование" по разным решениям, то и свои 5 капель доложу.
(хотя оно очень похоже на решение с умозрительным кубом)
Итак.
x+y+z=40
2<=x<=12
9<=y<=18
6<=z<=15

Видно, что ограничение снизу - бессмысленно!
Например, z=5, тогда x+y=35, но x+y<=30 по неравенствам.
Аналогично - x+z<=27, т.е. y>=13;
y+z<=33, x>=7.
ПОэтому условия можно переписать так:
x<=12
y<=18
z<=15

Почему так удобно? Вот смотрите.
Рассмотрим суммы x+y+z.
Максимум есть 12+18+15=45. То есть, ровно 1 вариант.

*лирическое отсупление, поможет понять логику*
Следующая ступень - 44. Мы можем уменьшить одно из трех чисел на 1. - 3 варианта.
Далее - 43. Либо одно число на 2, либо пару, каждое из которых - на 1. - 6 вариантов.

Заметили тенденцию? 1, 1+2, 1+2+3...
*конец лирического отсупления*

Теперь - 40. Нужно отнять от суммы 5 единиц. Точнее, отнимать их у чисел x y z. (можно отнимать не от всех, либо вообще только от одного)
Фактически, нам надо здесь определить, сколько вариантов разбиения пятерки на сумму трех неотрицательных чисел. Или, лучше сказать так:
У нас есть 5 шариков и три баночки краски. Сколько у нас есть вариантов покраски шариков?

Решаем теперь эту задачу. Она просто интереснее
Единый цвет- один вариант разбиения * 3 (выбор краски) =3
Два цвета - два варианта (1+4 и 2+3) * 6 (выбор краски большинства и меньшинства) = 12
Три цвета - значит, три шарика будут иметь разный цвет. Оставшиеся два шарика:
- единый цвет - один вариант * 3 (выбор краски) = 3
- разный цвет - один вариант * 3 (выбор неиспользованной краски) = 3.

Итого: 3+12+(3+3)=21.

P.S. Задачку с шариками, возможно, можно решить еще проще... думаю над этим.

[basil0]

5 камешков разложить по трем ямкам.
А комбинаторика тут не причем? Типа размещений, сочетаний, перестановок, краем уха слышал, что есть формулы для сочетаний с повторами

[Анюткин]

Спасибо всем огромное за помощь от меня лично и от моей знакомой.

Передаю дословно ее слова:

огромное спасибо всем, кто откликнулся! Мне это все очень пригодилось и помогло! И я даже поняла решение!!! Спасибо огромное!)