Kvant Math Problem 1112

Verified: no
Verdicts: SKIP + SKIP
Solve time: 8m02s
Source on kvant.digital

Problem

Two numbers, 1 and 2, are written on the board. One may append new numbers according to the following rule: if the numbers $a$ and $b$ are on the board, then one may write the number $ab+a+b$. Can one obtain in this way

the number 13121;
the number 12131?

Prove that there exist infinitely many natural numbers that cannot be represented in the form

$x+y+xy$;
$x+y+2xy$

with natural $x$ and $y$.

A. A. Berzinsh, V. G. Ilyichev

Exploration

Starting with the numbers $1$ and $2$ on the board, the rule allows us to produce $ab + a + b$ whenever $a$ and $b$ are present. Denoting this operation as $a \oplus b = ab + a + b$, we first compute small values. From $1$ and $2$, we get $1 \oplus 2 = 1 \cdot 2 + 1 + 2 = 5$. Combining $1$ and $5$ gives $1 \oplus 5 = 1 \cdot 5 + 1 + 5 = 11$. Similarly, $2 \oplus 5 = 2 \cdot 5 + 2 + 5 = 17$. Continuing this process produces numbers like $1 \oplus 11 = 13$, $5 \oplus 11 = 71$, etc. Observing the pattern, each new number can be expressed as $a \oplus b = (a+1)(b+1) - 1$. This factorization suggests that the sequence grows multiplicatively in the shifted variables $a+1$, $b+1$.

Testing the given numbers, $13121$ and $12131$, modulo small primes like $2$, $3$, $5$, $7$, and $11$ reveals constraints. Notably, the $\oplus$ operation preserves parity: $(a+1)(b+1)-1$ is odd when both $a$ and $b$ are odd, which is compatible with the initial numbers. Considering $x+y+xy$ and $x+y+2xy$, rewriting as $(x+1)(y+1)-1$ and $(2x+1)(2y+1)-1$ shows that certain residue classes modulo small integers are never attained. Thus, there appear to be numbers that cannot be generated, and the second part of the problem hints at infinite families with this property.

Problem Understanding

The problem asks whether certain integers can be generated from initial numbers $1$ and $2$ using the operation $a \oplus b = ab + a + b$, and more generally, whether infinitely many integers cannot be represented in forms $x+y+xy$ and $x+y+2xy$ with natural $x, y$. This is a Type A problem for the first part: classify which numbers can appear, and Type D for the second: construct infinitely many numbers outside the representation. The core difficulty lies in translating the $\oplus$ operation into a form that allows arithmetic characterization, then proving impossibility for certain numbers, especially for the infinite families.

Proof Architecture

Lemma 1: The operation $a \oplus b$ can be rewritten as $a \oplus b = (a+1)(b+1)-1$. This is true by direct expansion of $(a+1)(b+1) - 1 = ab + a + b$.

Lemma 2: Every number obtained from $1$ and $2$ using $\oplus$ corresponds to a product of numbers greater than 1 in the form $(a+1)$. The sketch is to define $S = {1,2}$ and recursively $T = {a+1 : a \in S}$, then every number generated maps to a product of elements of $T$ minus 1.

Lemma 3: If $N$ can be represented as $(a+1)(b+1)-1$, then $N+1$ is a product of integers greater than 1. Therefore, any number whose $N+1$ is prime cannot appear. Verification: $13121 + 1 = 13122$ and $12131 + 1 = 12132$ must be factorized.

Lemma 4: To generate infinitely many numbers not of the form $x+y+xy$, it suffices to choose primes larger than 2 for $N+1$, ensuring no factorization $(x+1)(y+1)$ exists. Similarly, for $x+y+2xy$, represent as $(2x+1)(2y+1)-1$, and select $N$ such that $N+1$ has a prime factor congruent to $3$ modulo $4$ or exceeds a product of the form $2x+1$. The hardest step is proving the infinite family in Lemma 4, ensuring no accidental factorization arises.

Solution

We first rewrite the operation in a more tractable form. Define $a \oplus b = ab + a + b$. Expanding $(a+1)(b+1) - 1 = ab + a + b$ shows that

$$a \oplus b = (a+1)(b+1) - 1.$$

Denote by $S$ the set of numbers that can be written on the board starting with $1$ and $2$. Define the shifted set $S' = {s+1 : s \in S}$. Initially, $S' = {2,3}$. Under $\oplus$, if $a,b \in S$, then $(a+1)(b+1) = a \oplus b + 1 \in S'$. Thus, $S'$ is the multiplicative closure of ${2,3}$. Hence, $S' = {2^i 3^j : i,j \ge 0}$, and $S = {2^i 3^j - 1 : i,j \ge 0}$.

To determine if $13121$ can appear, consider $13121 + 1 = 13122$. Factorizing $13122$, we find $13122 = 2 \cdot 3^2 \cdot 729$. Observing carefully, $729 = 3^6$, so $13122 = 2 \cdot 3^7$, which is of the form $2^1 3^7$, consistent with $S'$. Therefore, $13121 \in S$.

Next, for $12131$, $12131 + 1 = 12132$. Factorizing, $12132$ is divisible by $2$: $12132/2 = 6066$, again divisible by $2$: $6066/2 = 3033$, divisible by $3$: $3033/3 = 1011$, divisible by $3$: $1011/3 = 337$, which is prime. Therefore, $12132 = 2^2 \cdot 3^2 \cdot 337$. Since $337$ is not $2$ or $3$, it cannot be written as $2^i 3^j$, hence $12131 \notin S$.

For the second part, the general form $x+y+xy = (x+1)(y+1)-1$ shows that $N+1$ must factor into two integers greater than $1$. Any prime $p$ larger than $2$ cannot be so represented; thus, infinitely many natural numbers, namely the primes greater than $2$, cannot be written as $x+y+xy$ with natural $x,y$.

Similarly, $x+y+2xy = (2x+1)(2y+1)-1$. Let $N+1 = 2x+1 \cdot 2y+1$. Each factor $2x+1$ and $2y+1$ is odd and greater than $1$. Therefore, if $N+1$ has a prime factor congruent to $3$ modulo $4$ larger than $1$, or if $N+1$ is prime, then $N$ cannot be represented in this form. The sequence of numbers $N$ such that $N+1$ is an odd prime gives infinitely many natural numbers not of the form $x+y+2xy$.

This completes the proof.

∎

Verification of Key Steps

The crucial step is the identification $a \oplus b = (a+1)(b+1)-1$. Expanding $(a+1)(b+1)-1$ yields $ab + a + b$, confirming equality in all cases. Another delicate step is factorization: $12132 = 2^2 \cdot 3^2 \cdot 337$, showing $337 \neq 2^i3^j$, which correctly excludes $12131$. Finally, the infinitude argument relies on the infinitude of primes, which is classical and guarantees that infinitely many numbers cannot be represented as $x+y+xy$ or $x+y+2xy$.

Alternative Approaches

One could directly attempt to build $13121$ and $12131$ by recursively applying $\oplus$ starting from $1$ and $2$, but this quickly becomes computationally intensive. Another approach is modular arithmetic, observing that $S$ modulo $2$ or $3$ exhibits predictable patterns, which can exclude certain numbers; however, this is less general than the multiplicative closure method. The main approach using the identity $a \oplus b = (a+1)(b+1)-1$ is preferable because it reduces the problem to prime factorization, allowing explicit verification and a clear infinite-family argument.