No more fault

What is the least n , n 4 n ,n≥4 such that for any n n distinct integers one can find four distinct integers a , b , c , d a,b,c,d such that

20 a + b c d 20|a+b-c-d .


The answer is 9.

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.

2 solutions

Alapan Das
Oct 3, 2019

Let there are n , n 4 n,n\geq 4 numbers a 1 , a 2 , . . . . . a n 1 , a n a_1,a_2,.....a_{n-1},a_n , all are distinct. Now if for four distinct numbers a + c b d a+c-b-d is divisible by 20 then ,

( a b ) ( mod 20 ) = ( c d ) ( mod 20 ) |(a-b)(\text{mod} 20)|=|(c-d)(\text{mod} 20)| . 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 20 ) (a_i,a_j)=|(a_i-a_j)(mod 20)| . And we shall work with this pairs from now on.

So, our goal is to prevent four numbers from satisfying the given condition ( 20 a b + c d ) 20|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 ) (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 10 0\leq (a_p,a_k)=r\leq 10 . And let, all r r 's are used to prevent equality with the best effort. Without loss of generality we take ( a 1 , a 2 ) = 0 (a_1,a_2)=0 . Now, if any of the values ( a p , a q ) = 0 ; p , q = 3 , 4 , . . . . n 1 , n (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 a_1,a_2,a_k,a_l;k,l \in { 3 , 4 , . . . n 1 , n 3,4,...n-1,n } such that 20 a 1 a 2 + a k a l 20|a_1-a_2+a_k-a_l .

So, to prevent them from being 0 0 we should give them other 9 9 values ( 1 , 2...10 1,2...10 ). Now, there are A = A= ( n 2 ) ( n 3 ) 2 \frac{(n-2)(n-3)}{2} numbers of pairs with no a 1 a_1 , a 2 a_2 .

Now, if we have two equal-valued disjoint pairs in S = S= { ( a p , a q ) ; p , q = 3 , 4 , . . . . n 1 , n (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 ) (a_p,a_q)=(a_p,a_k) pair with a common element a p a_p are of equal values then ( a p , a q ) ( a p , a k ) = ( a q , a k ) = 0 (a_p,a_q)~(a_p,a_k)=(a_q,a_k)=0 or 2 r 2r ; as we had taken modulus ; ( a q , a k ) (a_q,a_k) surely may not be 0 0 but 2 r 2r or 2 r ( m o d 20 ) 2r(mod 20) . Then we are failed again.

So, we have ( n 2 ) ( n 3 ) 2 > 2 10 1 = 19 ( n 2 ) ( n 3 ) 2 20 n 2 7 n 9 \frac{(n-2)(n-3)}{2} > \bold {2*10-1=19} \Rightarrow \frac{(n-2)(n-3)}{2} \geq 20 \Rightarrow n-2 \geq 7 \Rightarrow n\geq 9 . We can take two non-disjointpairs equal \rightarrow 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_p,a_q)~(a_p,a_k) ( a q , a k ) = 0 \Rightarrow (a_q,a_k)=0 or 2 r 2r . But an extra equality fails our prevention.

So, the least such n n is equal to 9 \bold 9 .

Mark Hennings
Oct 3, 2019

If we have a set of numbers belonging to seven or more residue classes ( m o d 20 ) \pmod{20} then, since ( 7 2 ) = 21 > 20 \binom{7}{2} = 21 > 20 , we must be able to choose four distinct numbers a , b , c , d a,b,c,d , each with a different residue ( m o d 20 ) \pmod{20} , such that a + b c + d ( m o d 20 ) a + b \equiv c+d \pmod{20} .

If we have a set of numbers, and if four of them all belong to the same residue class ( m o d 20 ) \pmod{20} , then these four numbers a , b , c , d a,b,c,d are distinct numbers such that a + b c + d ( m o d 20 ) a+b\equiv c+d \pmod{20} .

If we have set of numbers, and if two pairs of numbers a , c a,c and b , d b,d exist such that a a and c c belong to the same residue class ( m o d 20 ) \pmod{20} , and such that b b and d d belong to the same residue class ( m o d 20 ) \pmod{20} , then a + b c + d ( m o d 20 ) a+b \equiv c+d \pmod{20} .

Thus, if our set of numbers has any of

  • 7 or more residue classes ( m o d 20 ) \pmod{20} ,
  • one residue class with four or more elements,
  • two residue classes with two or more elements,

then we can find distinct integers a , b , c , d a,b,c,d in the set such that a + b c + d ( m o d 20 ) a+b \equiv c+d \pmod{20} . If our set has 9 9 or more elements, then at least one of the above options must happen. Since it is possible to have a set of 8 8 elements comprising 6 6 residue classes, with one class containing 3 3 numbers, it may be possible to find a set with 8 8 elements that does not have the pair/sum/divisibility property. Indeed, the numbers 0 , 1 , 2 , 4 , 7 , 12 , 20 , 40 0,1,2,4,7,12,20,40 do the trick.

This makes the answer 9 \boxed{9} .

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...