combinations

Let Cn be the answer for n points. We have C1 = p, C2 = p(p-1) and C3=p(p-1)(p-2).

For n + 1 points, if A1 and An have differenr colors, then A1, ..., An can be colored in Cn ways, while An+1 can be colored in p - 2 ways. If A1 and An have the same color, then A1, ..., An can be colored in Cn-1 ways and An+1 can be colored in p - 1 ways. So Cn+1 = (p-2)Cn +(p-1)Cn-1 with n > 2 (*)

(*) can be written as:  

     Cn+1 + Cn = (p - 1) (Cn + Cn-1)

=> Cn+1 + Cn = (p - 1)n-2 (C3 + C2) = p(p - 1)n.

By induction we infer that Cn = (p - 1)n + (-1)n (p - 1)

Let C_n be the answer for n points. We have C₁ = p, C₂ = p(p-1) and C₃=p(p-1)(p-2).

For n + 1 points, if A₁ and A_n have differenr colors, then A₁, ..., A_n can be colored in C_n ways, while A_n+1 can be colored in p - 2 ways. If A₁ and A_n have the same color, then A₁, ..., A_n can be colored in C_n-1 ways and A_n+1 can be colored in p - 1 ways. So C_n+1 = (p-2)C_n +(p-1)C_n-1 with n > 2 (*)

(*) can be written as:  

     C_n+1 + C_n = (p - 1) (C_n + C_n-1)

=> C_n+1 + C_n = (p - 1)^n-2 (C₃ + C₂) = p(p - 1)ⁿ.

By induction we infer that C_n = (p - 1)ⁿ + (-1)ⁿ (p - 1)

Let A0 be the subset of S = {1, 2, ...3000} containing all numbers of the form 4nk, where n is a nonnegative integer and k is an odd positive integer. Then no two elements of A0 have ratio 2. A simple count shows A0 has 1999 elements. Now for each x∈ A0, form a set Sx={x,3x}∩S. Note the union of all Sx's contains S,S0, by the Dirichlet principle, any subset of S having more than 1999 elements must contain a pair in some Sx, hence of ratio 2. So no subset of 2000 numbers in S has the property.

Let A₀ be the subset of S = {1, 2, ...3000} containing all numbers of the form 4ⁿk, where n is a nonnegative integer and k is an odd positive integer. Then no two elements of A₀ have ratio 2. A simple count shows A₀ has 1999 elements. Now for each \(x\in\) A_0, form a set \(S_x=\left\{x,3x\right\}\cap S\). Note the union of all \(S_x\)'s contains \(S,S_0\), by the Dirichlet principle, any subset of S having more than 1999 elements must contain a pair in some \(S_x\), hence of ratio 2. So no subset of 2000 numbers in S has the property.