Find the minimum natural number $n$ with the following property: between any collection of $n$ distinct natural numbers in the set $\{1,2, \dots,999\}$ it is possible to choose four different $a,\ b,\ c,\ d$ such that: $a + 2b + 3c = d$.
Problem
Source: Spanish Communities
Tags: number theory unsolved, number theory
08.05.2006 18:49
Denote by M a set of numbers such that for any four different numbers we have $a+2b+3c\neq d$.Denote by m the number of its elements which are $a_1<a_2<....<a_m$. We will prove that the maximum value of $m$ is 833. We have that the sets $A=\{3a_1+2a_2+a_x: x\ge 3,a_x\le a_m-3a_1-2a_2\}$ and $B=\{a_x: a_x\ge a_m-3a_1-2a_2\}$ are disjoint, and their union is a subset of $(a_m-3a_1-2a_2,999] \cap \mathbb{N}$. We used the fact that $\min B>a_m-3a_1-2a_2$
23.08.2007 01:32
mmm... so wich is the minimun value of $ n$??
23.08.2007 12:04
@ElChapin: according to xirti the minimum value of $ n$ is $ 999-833 = 166$
24.08.2007 06:26
mmm... I don't have idea of wath he tried to do then... 166 non even in dreams... 833 the maximun without the property, but even 834 doesn't work... 835 seems to be the answer, but I can't prove that you can alwas find $ a$, $ b$, $ c$, $ d$.
24.08.2007 06:51
elchapin 835 is the answer see here
05.07.2012 20:44
Initially, will select the last $k$ integers so that when equality occurs above. Since the smallest element of the set, we have: $3a +2(a +1) +a+2 < 999 \iff a<166$ Thus, the set $\{165.166, ..., 999\}$, $k = 835$, satisfies the conditions of the utterance. Thus, $n \ge 835$. A good start would be to see if $835$ is the solution or if $n> 835$ ... divide the initial set into two subsets $A = \{1,2, ..., 166\}$ and $B = \{167,168, ..., 999\}$. Clearly, they are selected at least two elements of $A$, so suppose we have selected $n +2$ elements in $A$, which form a subset $A'= \{x_1, x_2, ..., x_ {n +2}\}$, and $833-n$ elements in $B$, forming the set $B'= \{y_1, y_2, ..., y_ {833-n}\}$, $n \ge 0$. Are $x_1, y_1$ the smallest elements in $A, B$, respectively. Note that $x_1 \le 167 - (n +2)$ and $167 + y_1 \le n$. Thus, $x_p$ is any element in $A$ and different from $x_1$, which follows: \[167 \le y_1+2x_p+3x_1 \le 167+n+2 \cdot 166+3(167-(n+2))\] \[167 \le y_1+2x_p+3x_1 \le 994-2n\] Thus, the expression $ y_1+2x_p+3x_1$ is always an element in $B$.Mas note that $x_p$ can take $n +1$ values. And $B'$ has $833-n$ elements, at least one of these $n + 1$ is in $B'$! Therefore, $835$ is the smallest value of n with this property.