A positive integer $n$ is $inverosimil$ if there exists $n$ integers not necessarily distinct such that the sum and the product of this integers are equal to $n$. How many positive integers less than or equal to $2022$ are $inverosimils$?
Problem
Source: 2022 Centroamerican and Caribbean Mathematical Olympiad, P6
Tags: number theory
01.12.2022 10:12
AlanLG wrote: A positive integer $n$ is $inverosimil$ if there exists $n$ integers not necessarily distinct such that the sum and the product of this integers are equal to $n$. How many positive integers less than or equal to $2022$ are $inverosimils$? "are equal to $n$" or "are equal"? The sum of n positive integers is equal to n if and only if they are all ones. Upd: I understood. The numbers can be negative
01.12.2022 18:31
We prove that $n$ works if and only if $4 \mid n$ and $n > 4$ or $n \equiv 1 \pmod{4}$, after which the problem reduces to a simple computation. First we prove that these work. If $n = 4m + 1$ just take $n$ together with $2m$ copies of $1$ and $2m$ copies of $-1$. If $n = 8m$ then take $4m, 2$ and then $6m - 2$ copies of $1$ and $2m$ copies of $-1$. Finally if $n = 4m$ with odd $m > 1$ then take $2m, -2$ along with $3m$ copies of $1$ and $m - 2$ copies of $-1$. These can be easily seen to all work, we now prove that others don't. In general, for an $n$ that works, let $b_1, b_2, \dots, b_k$ be the numbers with absolute value greater than $1$ that are used, so $n = |b_1b_2\dots b_k|$. Let $S = b_1 + b_2 + \dots + b_k$, and assume we use $x$ numbers equal to $1$, and $y$ numbers equal to $-1$. Then we have the conditions $x - y = n - S$ from the sum and $x + y = n - k$ from the total amount of numbers being $n$, which gives: \[x = n - \frac{S + k}{2} \qquad y = \frac{S - k}{2}\] We now have the setup for proving that the remaining cases don't work by contradiction. To discard $n = 4$, it's enough to do casework on the values of $b_1, b_2, \dots, b_k$, which are either $(4)$, $(-4)$, $(2, 2)$, $(2, -2)$ or $(-2, -2)$. All of these are easy to discard. Now if $n = 4m + 2$ then simply notice that exactly one of the terms $b_1, b_2, \dots, b_k$ must be even so $S$ and $k$ have a different parity, contradicting that $y = \frac{S - k}{2}$ is an integer. Finally assume that $n \equiv -1 \pmod{4}$, then an odd amount of the numbers $|b_1|, |b_2|, \dots, |b_k|$ are $-1 \pmod 4$. Notice then that \[|b_1| + |b_2| + \dots + |b_k| - k = (|b_1| - 1) + (|b_2| - 1) + \dots + (|b_k| - 1)\] has an odd number of terms that are $2 \bmod 4$ while the remaining ones are $0 \bmod 4$, so this whole sum is $2 \bmod 4$. Let $r$ be the amount of negative numbers among $b_1, b_2, \dots, b_k$, then this gives $S - k \equiv 2 - 2r \pmod {4}$ and thus $y = \frac{S - k}{2} \equiv 1 - r \equiv 1 + r\pmod{2}$. However this implies that an odd number of terms altogether are negative and thus the product of all terms is negative, which is impossible since it must be $n$.
01.12.2022 19:39
.
02.12.2022 21:33
We claim the answer is $n \equiv 0,1 \pmod 4$. Assume $n \equiv 2 \pmod 4$. This means that exactly one of $a_1,a_2, \ldots, a_{n}$ is even. So, $a_1+a_2+ \cdots +a_n$ is odd and thus cannot be $n$. Assume $n \equiv 3 \pmod 4$. Notice that $a_i$'s are odd. Suppose there are $p$ terms in the sequence $1 \pmod 4$ and $q$ terms $ 3 \pmod 4$. Notice that $n=p+q$. So, we get $p+3q \equiv n \equiv p+q \pmod{4}$. This implies that $(p+3q)-(p+q) \equiv 2q \equiv 0 \pmod{4}$ and so $2n \equiv 2p+4q \equiv 0 \pmod{4} $ so $n$ is even. Contradiction. Assume $n \equiv 1 \pmod{4}$ we get the construction \[ n+\underbrace{1-1+1- \cdots -1}_{n-1} = n = n+\underbrace{(1)(-1)(1) \cdots (-1)}_{n-1}\] Assume $n \equiv 0 \pmod{4}$ . Let $n=4k$ If $k$ is even we get \[ 2,2k, \underbrace{1,1, \ldots, 1}_{2k-2}, \underbrace{1,-1,1, \ldots -1}_{2k} \] If $k \equiv 1 \pmod{4}$ we get \[ -2,2,k, \underbrace{1,1, \ldots, 1}_{3k}, \underbrace{1,-1,1, \dots, -1}_{k-3} \] If $k \equiv 3 \pmod{4}$ we get \[ -2,-2,k, \underbrace{1,1, \ldots, 1}_{3k+4}, \underbrace{1,-1,1, \dots, -1}_{k-7} \]