bump on this

bump this

bump until get solution

We will prove by induction that $(n + 1)! - 1$ can be represented in at least $n!$ ways in the form: $x_1 + 2x_2 + 3x_3 + ... + nx_n$ where each $x_i$ is of the form $\frac{(n + 1)!}{d_i}$ and if we have that $d_{t_i} < d_{t_j}$ for each $1 \leq i < j \leq n$ then we have $d_{t_{1}} = t_1 + 1$ and $d_{t_{k + 1}} = (t_{k + 1} + 1)(d_{t_{k}})$ Base Case: $2! - 1 = 1 = 1 \times 1 = 1 \times \frac{2!}{2}$ Inductive Step: If the statement holds for some $k \geq 1$ then it also holds for $k + 1$. By the hypothesis, we have $k!$ solutions to: $x_1 + 2x_2 + ... + kx_k = (k + 1)! - 1$ where each $x_i$ is in the form that was described. Multiplying by $k + 2$ and adding $k + 1$ gives: $x_1(k + 2) + 2x_2(k + 2) + ... + kx_k(k + 2) + (k + 1)(1) = (k + 2)((k + 1)! - 1) + k + 1 = (k + 2)! - 1$ By the hypothesis, each $x_1 = \frac{(k + 1)!}{d_i}$. Define $y_i = (k + 2)x_i = \frac{(k + 2)!}{d_i}$ and $y_{k + 1} = \frac{(k + 2)!}{(k + 2)!}$ We have: $y_1 + 2y_2 + 3y_3 + ... + (k + 1)y_{k + 1} = (k + 2)! - 1$ Fix a solution to this (note there are $k!$ of them) and let $y_{t_{1}}$ with $y_{t_i} > y_{t_j}$ for $k + 1 \geq j > i \geq 1$ be the largest $y_i$. Note that: $y_{t_{1}} = \frac{(k + 2)!}{d_{t_{1}}}$ where $d_{t_{1}}$ is the smallest $d_i$ and so by the hypothesis, $d_{t_{1}} = t_{1} + 1$. Now let us multiply all the terms by $d_{t_{1}}$ apart from $y_{t_{1}}$ which we will turn into a $1$. In summary for every $i \neq t_1$, $y_{t_i}$ becomes $\frac{(k + 2)!}{\frac{d_{t_i}}{d_{t_{1}}}}$ and let this expression be equal to $z_{t_{i - 1}}$ and let $z_{t_{k + 1}} = 1$. We have: $z_1 + 2z_2 + 3z_3 + ... + (k + 1)z_{k + 1} = d_{t_{1}}(k + 2)! - d_{t_{1}} - ({t_{1}}(k + 2)! - {t_{1}}) = ({t_{1}} + 1)(k + 2)! - ({t_{1}} + 1) - ({t_{1}}(k + 2)! - {t_{1}}) = (k + 2)! - 1$. If we let $e_{t_i} = \frac{d_{t_{i + 1}}}{d_{t_1}}$ for $1 \leq i \leq k$ and have $e_{t_{k + 1}} = (k + 1)!$ then we have that for all $t_i$, $z_{t_i} = \frac{(k + 2)!}{e_{t_i}}$ and $e_{t_{k + 1}} = (t_{k + 1} + 1)(e_{t_{k}})$. And so we've created a new good set that meets the condition described in the hypothesis. We can keep on repeating this process (by taking the largest $z_i$) $k + 1$ times because at this point we will have cycled back to the solution we started with. If we do this with all $k!$ solutions we get a total of $k! \cdot (k + 1) = (k + 1)!$ solutions because each solution of length $k$ gives a cycle to work with for length $k + 1$. The solutions we've generated must all be distinct because if any two were the same in different cycles, we could cycle both of them to the solution where $x_{k + 1} = 1$ but by the hypothesis the original $k!$ solutions that were given were distinct so this is a contradiction. It is impossible for any two good sets in the same cycle to be equal since for each cycle, there is exactly one set where $x_1 = 1$ and where $x_2 = 1$ and so on. This completes our induction.

Use this one: https://artofproblemsolving.com/community/c6h1766320p11567481