Найти максимум в целых числах для n,m: n/(n+m) + (N-n)/(N-n + M-m)

Question

[lightcaster]

Что-то я забуксовал. Чувствую, что решение простое, но сходу не получается решить. Помоги, математик :).

Найти максимум f(n,m) для целых неотрицательных n,m: f(n,m) = n/(n+m) + (N-n)/(N-n + M-m)
где N>=n, M>=m, M,N>0

Спасибо.

Comments

[lightcaster]

M, N — некоторые положительные константы. Это НЕ переменные, относительно которых идет оптимизация.

Господа, за что минусы? Это не домашнее задание, гляньте в профиль, староват я для этого :)

Answer 1

[Arktos]

Сделал замену переменных (x = n, y = n + m, X = N, Y = N + M) и продиференцировал. В итоге максимум достигается при n + m = (N + M) / 2. В случае четного N + M максимум функции равен 2 * N / (N + M)

Comments

[vics001]

Пересчитайте. при N=M ваш максимум 1, а при m=0, можно получить значение больше 1.

[lightcaster]

Да, vics001 прав.
Но я и сам тут хорош, нужно было сразу четко обозначить границы.

[Arktos]

Если N = M, делаем n = m = N / 2. Получается N / (N + N) + (N — N / 2) / (2 * N — N) = 1. Можно лучше?
если m = 0, f(n, m) = n / n + (N — n) / (N — n + M) > 1

[Arktos]

Понял. Наверно я нашел минимум

[Arktos]

Но это же означает, что максимум достигается на граничных условиях. Перебирая все границы можно получить, что максимольное существующее значение получается при n = 1, m = 0, и он равен (2 * N + M — 2) / (N + M — 1)

[lightcaster]

Да, похоже это верное решение, большое спасибо.

Answer 2

[vics001]

Попробуйте расписать все честно и посчитать, верхняя часть дроби

— 2 n^2 + (2 N + M — 2 m) n + mN — > max (можно разложить на множители и найти максимум относительно n)
Нижняя часть (n + m) ((N+M) — (n+m)), естественно минимизируется при n+m = (N+M), хотя здесь и возникает деление на 0. То есть если верхняя часть максимум, а нижняя минимум и эти значения согласуется, тогда есть ответ :) Естественно что максимум по очевидным причинам меньше 2

Comments

[lightcaster]

Можно предположить, что n > 0. См. мой коммент выше.

[vics001]

Граничные условия очень важны! Определитесь m+n < M+ N? m =0? n=0? Какие значения имеют смысл m=M, n=N.

К примеру взяв m=0, получается интересное решение f(n) = 2 — M / (N +M — n). max = f(0) = 2 — M / (N+M). Ну или при f(1).

[vics001]

Вообще если зафиксировать к примеру m, то функция получается такая
f (n) = 2 — m/(n + m) — (M — m) / (-n + (N+M -m)), то есть искать надо минимум среди
m/(n+m) + (M — m) / ( -n + (N+M-m)) -> min
А потом среди минимумов параметров m, найти глобальный минимум.

[lightcaster]

Как я написал выше, это была «простая» задача из теории вероятностей: как можно разложить 100 черных и 100 белых шаров по двум корзинам, чтобы вероятность вытащить черный была максимальна. Хотел получить строгое формальное решение (плюс немного обобщил), но уперся в оптимизацию. Честно говоря, многое из матана позабывал, поэтому и задал вопрос.

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

[vics001]

Непонятно обобщение :) Расскажите с обобщением понятно, что если положить 100 черных в одну корзину и 100 белых в другую вероятность максимальная. Так же понятно если в одной корзине доминируют одни шары скажем с X%, то и вероятность вытащить их X% из этой корзины. Поэтому кладем по максимуму разные шары в разные корзины

[lightcaster]

Не понял ваш вывод. Разделять по максимуму — не оптимальный вариант.
Корзины после распределения шаров выбираются наугад. Далее, вытягивается наугад ОДИН шар. Формально, это будет так:

P(шар=черный) = P(шар=черный|корзина=1) P(корзина=1) + P(шар=черный|корзина=2) P(корзина=2)

Если обозначить n, m — количество черных и белых шаров в первой корзине соответственно, и учитывая P(корзина=1) = P(корзина=2) = 0.5, получаем:

P(шар=черный) = [ n/(n+m) + (100-n)/(200 — n — m) ] * 0.5

При n=0, m=100 (т.е. максимально разносим — все белые — в первую корзину, все черные — во вторую), получаем:

[0/(0+100) + (100-0)/(200-0-100)]* 0.5 = 0.5

При n=1, m=0 (т.е. в первую корзину кладем один черный шар, остальные 99 черных и 100 белых во вторую), получаем

[1/(1+0) + (100-1)/(200-1-0)]* 0.5 = 0.748

Т.е. дает большую вероятность, что и следует из аналитического решения (вы же сами это и предположили :) ).

Answer 3

[Cyapa]

Ну, если максимум что мы можем выжать из n/(n+m) это 1, при m = 0. Идем дальше, (N-n)/(N-n + M-m) тут лучшим случаем будет тот, где разность M — m минимальна, то есть 1. Следовательно, при M = 1, m = 0, n = 1, N = INF, предел (N-n)/(N-n + M-m) равен единице, а значит максимум функции стремится к 2.

Comments

[lightcaster]

Спасибо, но тут два момента.
1 — N,M — некие константы. Мы решаем относительно них.
2 — неясно, почему вы оптимизируете два элемента в сумме по-отдельности; мы имеем право это делать?

[jcmvbkbc]

От N и M ничего не зависит, т.к. оба слагаемых стремятся к максимуму (1) при неограниченном возрастании m и n, при условии неограниченного убывания m/n. Асимптотически максимум — 2.
Если областью определения было бы 0 < m < M и 0 < n < N, то решение было бы при m = [M/2], n = [N/2].

[Cyapa]

1, Ну тогда стояло условие поставить как: n <= N ^ m <= M ^ N, M > 0. А то немного сбивает с толку.
2. Я оптимизирую по частям, а не по отдельности, то есть сохраняю условия оптимизации первой части для второй и наоборот.

Ну при таком раскладе, можно пойти в лоб, и воспользоваться школьной математикой 9го класса, как вариант. Хотя решение и не самое удачное, наверное.

[vics001]

На самом деле частные производные тут совсем не помогут, условия поставлены не совсем корректно. При n +m -> 0 или n+m -> N+ M, получается любой бесконечно большое число. Так что тут задача в целочисленных ограничений, которые зачастую не имеют красивого решения.

Для целочисленных задач могу посоветовать построить графики в Mathematica или поискать для конкретных значений N, M экстремумы. Ну а вообще попытаться наложить больше ограничений на N, M.

Также можно посмотреть в сторону f (x, y) > или < f(x, y+1) и f (x +1, y) > или < f(x, y). Если функция монотонна (она квадратичная скорее всего будет 2 отрезка монотонности), то можно методом спуска определить целочисленный экстремум.

[lightcaster]

2 Суара,

сдается мне, это не математика 9-го класса. По крайней мере, здесь есть ограничения, которые нужно учитывать. И максимум будет как раз на границе. Я было через коеффициенты лагранжа пошел, но что-то запутался… забыл матан :)

2 vics001,

Согласен, не совсем корректно поставил условия. Тут можно смело положить, что n > 0 (строго больше нуля) чтобы отрезать ассимптотическое приближение. В исходной задачи N=M=100, так что я здесь немного обобщил.

Раз пошла такая пьянка — это была «простая» задача из теории вероятностей: как можно разложить 100 черных и 100 белых шаров по двум корзинам, чтобы вероятность вытащить черный была максимальна. Хотел получить строгое формальное решение, но уперся в оптимизацию. Честно говоря, многое из матана позабывал, поэтому и задал вопрос.