Problem 190
completed April 17, 2021Comments
This problem required me to dust off that old calculus book. I’ve been really wanting to brush up on it. I used to be so good at it plus I really loved the subject. I just haven’t used it at all since college. I’ve used the concepts – like the first and second derivatives corresponding to slope and acceleration respectively and the integral corresponding to the area under a curve – but never the calculation of these values directly. I’ve started taking a math course at a local university because I’ve been enjoying these problems so much. I’m hoping to take more courses and hopefully relearn some old skills and gain some new ones as well.
As far as this problem went, I knew I needed to take the derivative $\delta
x_i$ of the equation once for each value $1\leq i \leq m$. Replacing the value
of $x_1=m-x_2-x_3-\dotsb -x_{m-1}-x_m$ allowed me to remove one derivative, thus
leaving me we a system of linear equations. I then used matrix math and the
sympy package to do the rest.
I usually do most of my thinking with pen and paper, but this time I was so concerned with making errors that I transferred to writing it out on the computer. This way it was cleaner looking, easier to read, and I could edit it as I went and fix any problems. Once I did this I was able to get the correct answer pretty quickly. I’ve included my notes below.
Runs in 1.9 seconds with Pypy3 with half of the time going toward loading of
the sympy module alone.
Notes 
Given
\[y=x_1 x_2^2 x_3^3 \dotsm x_{m-1}^{m-1}x_m^m \text{ and } m=x_1+x_2+x_3+\dotsb+x_{m-1}+x_m\]Combining the two
\[x_1=m-x_2-x_3-\dotsb-x_{m-1}-x_m\] \[y=x_2^2 x_3^3 \dotsm x_{m-1}^{m-1}x_m^m(m-x_2-x_3-\dotsb-x_{m-1}-x_m)\]Let $R=x_2^2 x_3^3 \dotsm x_{m-1}^{m-1}x_m^m$
\[y= R(m-x_2-x_3-\dotsb-x_{m-1}-x_m)\] \[y=Rm-Rx_2-Rx_3-\dotsb-Rx_{m-1}-Rx_m\]Derivatives
\[y'=R'm-R-R'x_2-R'x_3-\dotsb-R'x_{m-1}-R'x_m=0\] \[y'=R'(m-x_2-x_3-\dotsb-x_{m-1}-x_m)-R=0\]System of equations
\[0=R\delta x_2(m-x_2-x_3-\dotsb-x_{m-1}-x_m)-R\] \[0=R\delta x_3(m-x_2-x_3-\dotsb-x_{m-1}-x_m)-R\] \[\dots\] \[0=R\delta x_{m-1}(m-x_2-x_3-\dotsb-x_{m-1}-x_m)-R\] \[0=R\delta x_m(m-x_2-x_3-\dotsb-x_{m-1}-x_m)-R\]Generic formula for $R\delta x_i$
\[R\delta x_i=\frac{iR}{x_i}\]This means that for every $x_i$
\[0=\frac{iR}{x_i}(m-x_2-x_3-\dotsb-x_{m-1}-x_m)-R\]Since $x_i>0$ for every $i\geq2$, divide both sides by $R$
\[0=\frac{i}{x_i}(m-x_2-x_3-\dotsb-x_{m-1}-x_m)-1\] \[0=i(m-x_2-x_3-\dotsb-x_{m-1}-x_m)-x_i\] \[0=im-ix_2-ix_3-\dotsb-ix_{m-1}-ix_m-x_i\]System of linear equations generically
\[0=im-ix_2-ix_3-\dotsb-ix_{m-1}-ix_m-x_i\]Specifically
\[i=2:\quad0=2m-2x_2-2x_3-\dotsb-2x_{m-1}-2x_m-x_2=2m-3x_2-2x_3-\dotsb-2x_{m-1}-2x_m\] \[i=3:\quad0=3m-3x_2-3x_3-\dotsb-3x_{m-1}-3x_m-x_3=3m-3x_2-4x_3-\dotsb-3x_{m-1}-3x_m\]As matrices
\[\begin{bmatrix} 3 & 2 & 2 & \dots & 2 & 2 \\ 3 & 4 & 3 & \dots & 3 & 3 \\ 4 & 4 & 5 & \dots & 4 & 4 \\ \vdots & \vdots & \vdots & \ddots & \vdots & \vdots \\ m-1 & m-1 & m-1 & \dots & m & m-1 \\ m & m & m & \dots & m & m+1 \end{bmatrix} \begin{bmatrix} x_2 \\ x_3 \\ x_4 \\ \vdots \\ x_{m-1} \\ x_m \end{bmatrix} = \begin{bmatrix} 2m \\ 3m \\ 4m \\ \vdots \\ (m-1)m \\ mm \end{bmatrix}\]Code
from sympy import Matrix as M
def P(m):
# AX = B or X = A^-1 B
A = M([
[
i + (i == j) for j in range(2, m + 1)
] for i in range(2, m + 1)
])
B = M([i * m for i in range(2, m + 1)])
X = A**-1 * B
val = m - sum(X)
for i, x in enumerate(X):
val *= x ** (i + 2)
return int(val)
def solve(n=None):
if n:
return P(n)
return sum(P(m) for m in range(2, 16))
if __name__ == '__main__':
import sys
n = eval(sys.argv[1]) if len(sys.argv) > 1 else None
print(solve(n))
Tests
import pytest
from problem import P
_test_P = (
(2, 1), # 1.185185185 or 32/27
(3, 1), # 1.6875
(10, 4112),
)
@pytest.mark.parametrize('n,expect', _test_P)
def test_P(n, expect):
assert expect == P(n)