2
$\begingroup$

Let $n$ be an even natural number. We divide the numbers $1, 2,\dots , n^2$ into two equal sets $A$ and $B$ (that is $|A|=|B|=n^2/2$), such that each of the $n^2$ numbers is exactly in one of the sets. Let $S_A$ and $S_B$ be the sum of all elements in $A$ and $B$. Determine all numbers $n$ so that there is a division satisfying$$\frac{S_A}{S_B}=\frac{39}{64}.$$

I found the value of $S_B$. $$ \begin{aligned} &\frac{S_A}{S_B}=\frac{39}{64}\\ &\begin{aligned} \frac{S_A+S_B}{S_B} & =\frac{39+64}{64} \\ \frac{\frac{\eta^2\left(n^2+1\right)}{2}}{S_B} & =\frac{103}{64} \\ S_B & =64 \cdot \frac{n^2\left(n^2+1\right)}{103 \cdot 2} \\ & =32 \cdot \frac{n^2\left(n^2+1\right)}{103} \end{aligned} \end{aligned} $$

Now this value should be smaller than or equal to sum of last n terms and greater than sum of first n terms.

$$ \begin{aligned} & \text { Sum of first in terms } \leq S_B \leqslant \text { sum of last ' } n \text { ' } \\ & \text { terms } \\ & \frac{n^2/2(n^2/2+1)}{2} \leq \frac{32}{103} n^2\left(n^2+1\right) \leq \\ & \frac{n^2\left(n^2+1\right)}{2}-\frac{n^2/2(n^2/2+1)}{2} \end{aligned} $$ I am not able to solve this inequality.Also I am not sure if this is correct direction. Because if I use geogebra then above inequality must have solution in between (0,3).

$\endgroup$
9
  • $\begingroup$ I would start by noting that $S_A+S_B$ must be a multiple of $103$. This is $\frac 12 n^2(n^2+1)$ so either $n^2$ or $n^2+1$ must be a multiple of $103$. The problem does not specify that all the small numbers go in $A$ and all the large ones go in $B$. Once the total is a multiple of $103$ you will have enough freedom to make the division. You should justify that, but it will never fail. $\endgroup$ Commented Apr 24, 2023 at 3:17
  • 1
    $\begingroup$ @user483801 FYI, using an Approach0 search, there's the AoPS thread Dividing 1,2,...,n^2 Into Equal Sets. Although currently unanswered, it indicates the problem is from the Swiss TST $2018$ P$4$. Also, it mistakenly states $\lvert A\rvert=\lvert B\rvert=n$, as you did initially, so I suspect your question came from there and/or the test paper had that mistake. $\endgroup$ Commented Apr 24, 2023 at 3:28
  • 2
    $\begingroup$ Your inequality fails because you do the sum of $n$ terms. You should be using the sun if $n^2/2$ terms though I expect it’ll be something that’s basically always true. You can do induction to show every integer between those two is achievable. $\endgroup$
    – Eric
    Commented Apr 24, 2023 at 3:30
  • $\begingroup$ @Eric I edited it but it does not change the answer! $\endgroup$
    – user483801
    Commented Apr 24, 2023 at 3:52
  • 1
    $\begingroup$ @JohnOmielan: Oops, sorry, missed that somehow, thanks! $\endgroup$
    – Brian Tung
    Commented Apr 24, 2023 at 18:34

1 Answer 1

1
$\begingroup$

You've made a good start. Note your result of

$$S_B = \frac{32n^2\left(n^2+1\right)}{103} \tag{1}\label{eq1A}$$

must be an integer. Thus, as Ross's comment indicates, the prime $103$ must divide $n^2(n^2+1)$ but, as Ross's other comment states, $n^2+1$ is never a multiple of $103$. Assume, otherwise, there's such an $n$. Then,

$$n^2 \equiv -1\pmod{103} \to (n^2)^{51} \equiv (-1)^{51}\pmod{103} \to n^{102} \equiv -1\pmod{103} \tag{2}\label{eq2A}$$

However, Fermat's little theorem states $n^{102} \equiv 1\pmod{103}$, contradicting \eqref{eq2A}. Thus, $n$ must be a multiple of $103$. Since $n$ is also even, then all potential $n$ are of the form

$$n = 206k, \;\; k \in \mathbb{N}, \;\; k \ge 1 \tag{3}\label{eq3A}$$

We should also confirm, as you indicated, that $S_B$ is within the possible bounds. For the lower bound, with $\frac{n^2/2(n^2/2+1)}{2} = n^2\left(\frac{n^2 + 2}{8}\right)$, we get

$$n^2\left(\frac{n^2 + 2}{8}\right) \le n^2\left(\frac{32\left(n^2 + 1\right)}{103}\right) \longleftrightarrow \frac{n^2 + 2}{8} \le \frac{32n^2 + 32}{103} \longleftrightarrow n^2 \ge -\frac{153}{50} \tag{4}\label{eq4A}$$

Similarly, for the upper bound, we have $n^2 \ge \frac{50}{53}$. Thus, neither bound restricts \eqref{eq3A}.

The only remaining issue is to show the value of $S_B$ in \eqref{eq1A} can be achieved as a sum of $\frac{n^2}{2}$ elements. Start with the smallest sum set of $1$ to $\frac{n^2}{2}$, inclusive. Then take the largest value, i.e., $\frac{n^2}{2}$, and increment it one by one until it becomes $n^2$. Then do the same thing for the next largest original value, i.e., $\frac{n^2}{2}-1$, until it becomes as large as it can be, i.e., $n^2 - 1$. Continue this procedure down to the smallest original value, i.e., $1$, going to $\frac{n^2}{2} + 1$. This finishes with the set then being the largest $\frac{n^2}{2}$ values and, thus, having the maximum possible sum. Since the sum has increased by $1$ at each increment, this has covered all possible valid sums, including $S_B$ in \eqref{eq1A}. This confirms \eqref{eq3A} gives all of the solutions for $n$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .