I'm trying to find a solution to the following problem without resorting to brute force:
\begin{equation} \text{maximize } \binom{n}{x} \times \binom{n}{y} \end{equation}
subject to the constraints:
\begin{align} 0 \leq x \leq n, \\ 0 \leq y \leq n, \\ ax + y = b \end{align}
where $a, b \in \mathbb{N}$.
A brute force approach I considered was defining:
\begin{equation} f(x) = \binom{n}{x} \times \binom{n}{b - ax} \end{equation}
Then, I would find the smallest value of $x$ such that the ratio $\frac{f(x+1)}{f(x)} \leq 1$. However, I am looking for a more elegant and efficient solution.
To give some context, this problem arose from a scenario involving two types of fair coins, $A$ and $B$. There are $500$ coins of type $A$ and $500$ of type $B$. For every head from an $A$ coin, I earn 1 dollar, and for every head from a $B$ coin, I earn 4 dollars. If I know that I have won $1200$ dollars in total, what is the most probable configuration of heads?
Using brute force, I derived the answer to be $238$ heads from the $A$ coins. However, the teacher indicated that we shouldn't resort to the brute force method, as there's a clever trick to address this problem. Is there another method to obtain this result?
PS: I suspect the teacher is hinting at a solution that leverages symmetry. For instance, to maximize $\binom{n}{x} \times \binom{n}{b - x}$, the optimal value would be $x = b/2$. If $a > 1$, it introduces an asymmetry between $A$ and $B$.
It reminds me of a similar trick used to maximize $x^3 (9 - 2x)$ without using calculus. We can express this as $2x^3 \left(\frac{9}{2} - x\right) = \frac{2}{3} x^3 (\frac{27}{2} - 3x)$, recognizing that $x + x + x + \left(\frac{27}{2} - 3x\right) = \frac{27}{2} $, which is constant. Equating the terms gives $ x = x = x = \frac{27}{2} - 3x $, which implies $ x = \frac{27}{8} $.
Using algebra, it would be simpler to solve $$\log(f(x+1))-\log(f(x))=0$$ and to write, in Mathematica syntax
F[x_]:=2*LogGamma[1 + n]-Log*Gamma[1 - b + n + a*x] - LogGamma[1 + n - x] - LogGamma[1 + x] - LogGamma[1 + b - a*x]and then
FindRoot[F[x]==F[x+1],{x,x0}]where (to be defined somewhere)
x0=(2*b - n)/(2*a)Without any solver and coding Newton method, the iterates will be (using your values for $(a,b,n)$ $$\left( \begin{array}{cc} p & x_p \\ 0 & 237.500000000 \\ 1 & 237.735764976 \\ 2 & 237.735757882 \\ \end{array} \right)$$