Let $k>1$ be an integer, set $n=2^{k+1}$. Prove that for any positive integers $a_1<a_2<\cdots<a_n$, the number $\prod_{1\leq i<j\leq n}(a_i+a_j)$ has at least $k+1$ different prime divisors.
Problem
Source:
Tags: pigeonhole principle, ceiling function, number theory unsolved, number theory
01.10.2011 00:04
It's true for $n\ge 2^k + 1$ and $k\ge 1$ according to this paper of Erdős and Turán (their pigeonhole argument only depends on the lemma and $\lceil{n/2^{k-1}}\rceil \ge 3$).
23.09.2014 20:49
are there any soioution ?
03.03.2018 18:03
assume the contrary set Ap={n| n/(p^{vp(n)}) remainder divided by p is less than p/2} Bp={n| n/(p^{vp(n)}) remainder divided by p is greater than p/2} for odd p and A2={n| n/(2^{v2(n)}) =1(mod4)} B2={n| n/(2^{v2(n)}) =3(mod4)} then there are k such pairs of sets and by the pigeon hole principle two ai,aj are in the same set for all p and for each p(exept 2) vp(ai+aj)=min(vp(ai),vp(aj)), v2(ai+aj)<min(v2(ai),v2(aj))+2 so ai+aj has another prime factor different to the k prime factors we set as the divisors of the given product if not ai=aj a contradiction
22.07.2022 15:27
Really hard and nice problem. Here's a sketch of the solution I found in Canada IMO training site (might be similar to the above one, but still I think it's better phrased). Suppose the prime divisors are $p_1,...,p_k$. For each prime $p_t$, consider graph $G_t$ with vertices $1,2,...,2^{k+1}$, such that $ij$ is an edge iff $v_p(a_i+a_j)\geq min(v_p(a_i), v_p(a_j))+1$ for $p_t \neq 2$ and $v_2(a_i+a_j)\geq min(v_2(a_i), v_2(a_j))+2$ otherwise (let $p=p_t$ for short). We have the following claims: $\textbf{Claim 1:}$ There is an edge between $i$ and $j$ in at least one graph. $\textbf{Proof:}$ If not, then $a_i+a_j \leq 2min(a_i,a_j)$ using the $v_p$ conditions, done. $\blacksquare$ $\textbf{Claim 2:}$ Each graph $G_t$ is bipartite. $\textbf{Proof:}$ Suppose not, then we have an odd cycle $a_1, a_2,...,a_m$ in $G_t$ (let $p=p_t \neq 2$, the other case is similar). Note that then $v_p(a_1)=...=v_p(a_m)=N$, hence $\frac{a_i}{p^N} \equiv -\frac{a_{i+1}}{p^N} \pmod p$ for all $i=1,2,...,m$, so $v_p(a_1) \geq N+1$, contradiction. $\blacksquare$. Now we have that some pair $(i, j)$ are always in the same class in each bipartite graph $G_t$, which will be a final contradiction, since there won't be an edge between them. Indeed, associate with each vertex a binary $k$-tuple which corresponds to the classes the vertex is; then there are two identical $k$-tuples, since there are more than $2^k$ vertices, absurd (in fact, only $2^k+1$ numbers are needed, not $2^{k+1}$).
17.12.2024 08:13
Assume FTSOC that $S=\{p_1,p_2,\dots,p_k\}$ is a set of primes containing all prime factors of $\prod_{1\leq i<j\leq n}(a_i+a_j)$. For each $p \in S$, partition the positive integers into two sets $A_p$ and $B_p$ as follows: if $p \ne 2$, then $n \in A_p$ if $\tfrac{n}{p^{\nu_p(n)}} \mod p \in \{1,2,\dots,\tfrac{p-1}{2}\}$ and $n \in B_p$ otherwise if $p=2$, then $n \in A_p$ if $\tfrac{n}{p^{\nu_p(n)}} \mod 4=1$ and $n \in B_p$ otherwise. Each positive integer $n$ can be assigned a binary string $s_1s_2 \cdots s_n$, where $s_i=1$ if and only if $n \in A_{p_i}$. Since there are $2^k$ possible binary strings and $n>2^k$ elements in $\{a_1,\dots,a_n\}$, some two elements $x$ and $y$ have the same binary string. Claim: $x+y \mid 2\gcd(x,y)$. Proof: We prove that $\nu_p(x+y) \le \nu_p(2\gcd(x,y))$ for all primes $p$. We have three cases. Case 1: $p \in S$ and $p \ne 2$. If $\nu_p(x) \ne \nu_p(y)$, then \[\nu_p(x+y)=\min(\nu_p(x),\nu_p(y))=\nu_p(2\gcd(x,y)),\]so we are done. Otherwise, let $\nu_p(x)=\nu_p(y)=k$. Since $\tfrac{x}{p^k} \mod p$ and $\tfrac{y}{p^k} \mod p$ are either both in $\{1,2,\dots,\tfrac{p-1}{2}\}$ or both in $\{\tfrac{p+1}{2},\tfrac{p+3}{2},\dots,p-1\}$, we have $p \nmid \tfrac{x+y}{p^k}$. This means \[\nu_p(x+y)=\nu_p(2\gcd(x,y))=k,\]as desired. Case 2: $p \in S$ and $p=2$. If $\nu_2(x) \ne \nu_2(y)$, then \[\nu_2(x+y)=\min(\nu_2(x),\nu_2(y))=\nu_2(\gcd(x,y))<\nu_2(2\gcd(x,y)),\]so we are done. Otherwise, let $\nu_2(x)=\nu_2(y)=k$. Since $\tfrac{x}{2^k} \mod 2$ and $\tfrac{y}{2^k} \mod 2$ are either both $1$ or both $3$, we have $\nu_2(\tfrac{x+y}{2^k})=1$. This means \[\nu_2(x+y)=\nu_2(2\gcd(x,y))=k+1,\]as desired. Case 3: $p \notin S$. Then, $\nu_p(x+y)=0 \le \nu_p(2\gcd(x,y))$ by assumption. $\square$ However, we have $2\gcd(x,y) \le 2\min(x,y)<x+y$, contradiction. Therefore $\prod_{1\leq i<j\leq n}(a_i+a_j)$ has at least $k+1$ prime factors. $\blacksquare$