What is the least n , n ≥ 4 such that for any n distinct integers one can find four distinct integers a , b , c , d such that
2 0 ∣ a + b − c − d .
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
If we have a set of numbers belonging to seven or more residue classes ( m o d 2 0 ) then, since ( 2 7 ) = 2 1 > 2 0 , we must be able to choose four distinct numbers a , b , c , d , each with a different residue ( m o d 2 0 ) , such that a + b ≡ c + d ( m o d 2 0 ) .
If we have a set of numbers, and if four of them all belong to the same residue class ( m o d 2 0 ) , then these four numbers a , b , c , d are distinct numbers such that a + b ≡ c + d ( m o d 2 0 ) .
If we have set of numbers, and if two pairs of numbers a , c and b , d exist such that a and c belong to the same residue class ( m o d 2 0 ) , and such that b and d belong to the same residue class ( m o d 2 0 ) , then a + b ≡ c + d ( m o d 2 0 ) .
Thus, if our set of numbers has any of
then we can find distinct integers a , b , c , d in the set such that a + b ≡ c + d ( m o d 2 0 ) . If our set has 9 or more elements, then at least one of the above options must happen. Since it is possible to have a set of 8 elements comprising 6 residue classes, with one class containing 3 numbers, it may be possible to find a set with 8 elements that does not have the pair/sum/divisibility property. Indeed, the numbers 0 , 1 , 2 , 4 , 7 , 1 2 , 2 0 , 4 0 do the trick.
This makes the answer 9 .
Problem Loading...
Note Loading...
Set Loading...
Let there are n , n ≥ 4 numbers a 1 , a 2 , . . . . . a n − 1 , a n , all are distinct. Now if for four distinct numbers a + c − b − d is divisible by 20 then ,
∣ ( a − b ) ( mod 2 0 ) ∣ = ∣ ( c − d ) ( mod 2 0 ) ∣ . Where the modulos vary from -9 to 10 over the integers. So, in sake of simplification we say that the order pair of two elements, let ( a i , a j ) = ∣ ( a i − a j ) ( m o d 2 0 ) ∣ . And we shall work with this pairs from now on.
So, our goal is to prevent four numbers from satisfying the given condition ( 2 0 ∣ a − b + c − d ) . So to do that we have put our maximum effort not to give any of those disjoint pairs ( ( a p , a q ) = ( a k , a l ) , p,q,k,l all are distinct) to be equal, namely . Intersecting pairs may be equal because we are asked for four distinct numbers. So, we shall proceed like this.
Let, 0 ≤ ( a p , a k ) = r ≤ 1 0 . And let, all r 's are used to prevent equality with the best effort. Without loss of generality we take ( a 1 , a 2 ) = 0 . Now, if any of the values ( a p , a q ) = 0 ; p , q = 3 , 4 , . . . . n − 1 , n , then we are failed (we will have for distinct numbers a 1 , a 2 , a k , a l ; k , l ∈ { 3 , 4 , . . . n − 1 , n } such that 2 0 ∣ a 1 − a 2 + a k − a l .
So, to prevent them from being 0 we should give them other 9 values ( 1 , 2 . . . 1 0 ). Now, there are A = 2 ( n − 2 ) ( n − 3 ) numbers of pairs with no a 1 , a 2 .
Now, if we have two equal-valued disjoint pairs in S = { ( a p , a q ) ; p , q = 3 , 4 , . . . . n − 1 , n } then we are failed. But if two intersecting ( a p , a q ) = ( a p , a k ) pair with a common element a p are of equal values then ( a p , a q ) ( a p , a k ) = ( a q , a k ) = 0 or 2 r ; as we had taken modulus ; ( a q , a k ) surely may not be 0 but 2 r or 2 r ( m o d 2 0 ) . Then we are failed again.
So, we have 2 ( n − 2 ) ( n − 3 ) > 2 ∗ 1 0 − 1 = 1 9 ⇒ 2 ( n − 2 ) ( n − 3 ) ≥ 2 0 ⇒ n − 2 ≥ 7 ⇒ n ≥ 9 . We can take two non-disjointpairs equal → at most "twice" because the equality of pairs does not imply the fail of our prevention as ( a p , a q ) ( a p , a k ) ⇒ ( a q , a k ) = 0 or 2 r . But an extra equality fails our prevention.
So, the least such n is equal to 9 .