Find the largest number $n$ that for which there exists $n$ positive integers such that non of them divides another one, but between every three of them, one divides the sum of the other two. Proposed by Morteza Saghafian
Problem
Source: 2017 Iran TST second exam day1 p2
Tags: Iran, Iranian TST, number theory, combinatorics
23.04.2017 21:22
The largest value of $n$ is $3$. For the sake of contradiction, let there exist a set with greater than equal to $4$ elements.We'll prove a lemma. Lemma: For a set of numbers with more than equal to 4 element, if $a,b$ are in these set of numbers, then $a | b$. Proof: Let $a,b,c,d$ be 4 numbers in that set. Then, $a | b+c$ and $a | c+d$ $\implies a | b-d $ , also $a | b+d$ $ \implies a | 2b$ as desired. $\square$ Let the set of numbers have more than equal to 4 elements. Let $a$ be the element such that the max power of $2$ that divides $a$ ( i.e., if it is $k$, then $2^k | a$ and $2^{k+1} \not | a$) is minimum. Let $a=a_12^k$ where $a_1$ is odd. Consider another element $b$ with $b=b_12^l$ where $b_1$ is odd. Also, $k \leq l$ We know by lemma that $a | 2b$ $\implies a_12^k | b_12^{l+1}$ $\implies a_1 | b_1$ as $k \leq l < l+1$ $\implies a=a_12^k | b_12^k|b_12^l=b$ which is a contradiction. EDIT:Oops, I I misunderstood the the problem
24.04.2017 15:22
The numbers $~2,~ 3,~ 7,~ 46,~ 683$ show that $n\ge5$.
24.04.2017 17:20
@test20 In your example, $2$ divides $46$
24.04.2017 17:42
$2,3,5,7,107$ is an example for $n=5$.
24.04.2017 17:49
laegolas wrote: $2,3,5,7,107$ is an example for $n=5$. What about $(5,7,107)$?
24.04.2017 17:49
$2,3,5,7,193$
24.04.2017 17:50
@bgn, $7\cdot 16=5+107$ .
01.05.2017 05:22
who can solve it? I only give an example for $n=5$. But I can't prove $n \leq 5$
01.05.2017 05:47
Maybe we should work the other way round ... find the smallest positive integer for which this cannot be true... it is the same problem but just in an easier way to think (?).
09.05.2017 05:55
I think $ {n}\mathrm{\leq}{6} $. Such as 2,3,5,7,107,10693
09.05.2017 06:06
The largest value of n is 6. 2,3,5,13,127,17267 works. Now we must show n=7 does not work. First we can reduce the problem to where the numbers do not all share a common factor as otherwise we could just divide out the common factor. Lemma 1: There are at most two even numbers. Proof: Assume there are three, $x_i,x_j,x_k$. Let $a$ be some odd number in your set of numbers. We know there's an odd cuz our numbers all shared a common factor. Consider the triples $a,x_i,x_j$, $a,x_i,x_k$, and $a,x_j,x_k$. In each of these triples we must have that $a$ divides the sum of the other two because the other cases have an even number dividing an odd number. Then $a|x_i+x_j,x_j+x_k,x_i+x_k$ s owe can get that $a|2x_i$. Since $a$ is odd, we have $a|x_i$, a contradiction. Lemma 2: If $x_i>x_j,x_k$, then $x_i|x_j+x_k$ if and only if $x_i=x_j+x_k$. Proof: $x_i>(x_j+x_k)/2$ so $x_i=x_j+x_k$. Lemma 3: If there are two evens, the larger even number is the maximal element in our set. Proof: Let the evens be $x_i$ and $x_j$, with $x_j>x_i$. If $x_j$ is not maximal, there is an odd number $a>x_j$ since there are only two evens, which are $x_i$ and $x_j$. Then $a|x_i+x_j$ since an even cannot divide an odd, but by Lemma 2 this implies $a=x_i+x_j$, a contradiction as $a$ is odd. Lemma 4: If there exists a working set with $n$ elements, there exists a working set with $n$ elements that contains 2. Proof: If there is only one even, we can replace it with 2 and the set still works (all triples containing it have 2 dividing the sum of the other two, as all others are odd). Now, we look at the case with two evens. I claim that we can replace the smaller even with 2 and then add the product of all the odd elements in the set to the larger even and still have a set that works. First, this process leaves all elements except 2 to be odd, so 2 does not divide any of the other elements. Moreover, if any of the odd elements divides the larger after modification, then it must have divided it before modification as well as the number we changed it by was a multiple of all the other odds. Moreover, any triple containing the smaller element still has one element dividing the sum of the other two, as 2 divides the sum of any two odds. Then it suffices to show that a triple containing the larger even still has an element dividing the sum of the other two. Let the larger even be $k$, and the new even be $k'$. Note that if $x_i|x_j+k$ for some $x_i,x_j$ in our set, we still have $x_i|x_j+k'$. I claim that these are the only cases that appeared in triples involving $k$ in our old set, meaning that there were no $x_i,x_j$ in our set such that $k|x_i+x_j$. Assume for the sake of contradiction that there were such a pair. let $m$ be the smaller even in our old set. Note that $x_i|m+k$ and $x_j|m+k$ so $lcm(x_i,x_j)|m+k$. However, $m+k$ is even and $lcm(x_i,x_j)$ is odd so $2*lcm(x_i,x_j)\leq m+k$. $m<k$, so this gives us $lcm(x_i,x_j)<k$. Moreover, by Lemma 3 $k$ is our maximal element so we can apply Lemma 2 and get that $k=x_i+x_j$. This implies that $lcm(x_i,x_j) \geq 2*x_j > k$ where $x_j$ is the larger of $x_i, x_j$, which gives us a contradiction. Then our transformed set still works and includes 2, proving the Lemma. Now we need to show that any set with 7 elements containing 2 doesn't work. Let the set of numbers be $2, x_1,x_2,x_3,x_4,x_5,x_6$, in order of size. Consider the triples $x_i,x_j,x_6$. There are 5 choose 2 = 10 of these triples, and in each triple either $x_6$ is not the number that divides the other two because $x_6$ cannot be the sum of the other two as all numbers except 2 must be odd and $x_6$ is greater than the other two so we can apply Lemma 2. I claim that there is some $x_i$ such that $x_i$ divides the sum of the other two in three of these triples. $x_5$ divides at most one of these triples because if it divided both $x_i+x_6$ and $x_j+x_6$, we would have $x_5|x_j-x_i$ which is a contradiction since $x_5>x_j,x_i$. Then $x_1,x_2,x_3,x_4$ divide 10-1=9 triples in total, so by pigeonhole one of them divides three of them. Say this number is $x_i$, and the sums it divides are $x_j+x_6,x_k+x_6,x_l+x_6$. $Let x_j<x_k<x_l$.Then $x_j=x_k=x_l$ modulo $x_i$, which also tells us that $x_i<x_k$ as well. Since $x_i$ is odd, we know that $x_i$ cannot divide $x_j+x_k,x_j+x_l,x_l+x_k$. Then by applying Lemma 2 and the fact that no two x's sum to each other since they are all odd, we get that $x_j|x_i+x_l$, $x_j|x_i+x_k$, and $x_k|x_i+x_l$. Now consider the triple $x_j,x_k,x_l$. If $x_j|x_k+x_l$, we would have $x_j|x_i+x_k,x_k+x_l,x_i+x_l$ which would lead to us getting that $x_j|x_k$, so we must have $x_k|x_j+x_l$ after using Lemma 2. Then we have $x_k|x_j+x_l,x_i+x_l$, which is also impossible because $x_k>x_j,x_i$ so $x_j$ cannot be congruent to $x_i$ mod $x_k$. Then we have proven that no set including 2 can work, so we are done after applying Lemma 4. God I hope this is right this took me forever to do