0

Problem: Let $S\subset[1989]={1,2,...,1989}$. If two elements of $S$ have that $a-b\neq4$ or $7$, find max$|S|$.

My solution is as follows: We first consider the first four integers $1,2,3,4$. Then if we add $4$ and $7$ to each of these numbers respectively, we would then have $5,6,7,8$ and $8,9,10,11$. So since we want the maximum number of elements of $S$, we should pick the next numbers right after $11$. These are $12,13,14,15$. Continuing this process, we have this sequence of vectors in $\mathbb R^4$; $a_n=(11(n-1)+1, 11(n-1)+2, 11(n-1)+3, 11(n-1)+4)$. So now, since the upper bound for this sequence is $\leq 1989$, we have to solve $11(n-1)+4 \leq 1989$. This yields the solution $1\leq n\leq 181$. Hence we have $max(|S|)$=$4(181)$=$724$. BUT WAIT! We overcounted! We over counted all of the times $(n+1)+7$=$(n+4)+4$. This happens in between every $a_{n-1}$ and $a_n$. But there $181$ such $n$. Hence there are $181$ such times when $(n+1)+7$=$(n+4)+4$. Thus we add back another $181$ and we have that (finally) $max(|S|)$=$4(181)+181$=$905$.

I would like to know if my solution is correct, because I feel as if my solution is not rigorous enough and I am afraid that I might be incorrect. If you see anything wrong with my proof, kindly please point out where I went wrong and maybe explain the strategies that would be needed so I wouldn't make the same mistake again. (I believe this is the 1989 AIME #13? Don't quote me on that)

DatBoi
  • 4,055
combinatorialist46Carey2
  • 401
  • Solution to what question? – saulspatz May 02 '21 at 16:22
  • Let $S$$\subset$[$1989$]={$1$,$2$,...,$1989$}. If two elements of $S$ have that $a$-$b$$\neq$$4$ or $7$, find max$|S|$. – combinatorialist46Carey2 May 02 '21 at 16:22
  • Sorry about that @saulspatz! :) – combinatorialist46Carey2 May 02 '21 at 16:22
  • If you would like the original, it is the 1989 AIME #13. – combinatorialist46Carey2 May 02 '21 at 16:23
  • Please edit your question to include this information at the beginning. Clarifications belong in the body of the question, not the comments. – saulspatz May 02 '21 at 16:23
  • Sorry @saulspatz. It has been a while since I have used MSE. (Not the best at latex either :P). – combinatorialist46Carey2 May 02 '21 at 16:24
  • Why would you want $1,2,3,4\in S$ from the start? – user10354138 May 02 '21 at 16:46
  • Because after some trial and error, I figured out that if $1,2,3,4$ were chosen first, it would maximize it. Choose any other number, and you would have less. It is a bit hard to explain. I was pretty tired when I started. – combinatorialist46Carey2 May 02 '21 at 16:47
  • No it wouldn't. For example, ${1,3,6,9,11}\subset[11]$. – user10354138 May 02 '21 at 16:57
  • @user10354138 YES! I suppose that could be another solution! We would have $11(n-1)+5 \leq 1989$, so that $1 \leq n \leq 181$, and since there are $5$ numbers, we would have $5(181)$=$905$! But, what about the instances when we overcount? For instance, $9+4$=$6+7$? Then we would be subtracting two of the same number per each $a_{n-1}$ and $a_n$. So we would have to add back $181$. Which would give $905$+$181$=$1086$. But since $1086$>$999$, (AIME), we would be false. Or am I doing something wrong by the "overcounting" part? – combinatorialist46Carey2 May 02 '21 at 18:12
  • 1
    Also, what would happen if we considered a smaller case? Maybe when instead of $1989$, we consider $26$, say. Then if we have {1,3,6,9,11}⊂[11], the next solution would be the set {$12,14,17,20,22$}. So a total of $10$ solutions with this method. But if we use ${1,2,3,4}$, we now have $12$ solutions. So either one of us is wrong. But I am awful at mathematics! (:P) And you have a lot of reputation, so you are probably right. Thank you though! I learned a lot of lessons from this problem! :D – combinatorialist46Carey2 May 02 '21 at 18:47
  • Well it actually seems using this method, that the answer maybe should be just $4(181)$=$734$. :/ But the solution says it is actually $905$. So was I right before? Or is the answer on aops incorrect? – combinatorialist46Carey2 May 02 '21 at 18:50
  • Your "but wait" makes no sense to me. You've chosen the $4\times 181$ numbers which are of the form $11(n-1) + i, 1 \leq i \leq 4, 1 \leq n \leq 181$. I don't understand what you've "overcounted", or which other 181 elements you have added in. $ \quad \quad$ Your solution is wrong, and we can indeed pick 905 elements from S. EG One can easily modify User1035... 's example (as you started doing) to get 904 elements (so it's not quite good enough). – Calvin Lin May 04 '21 at 08:36
  • @toolfan3 The reason why $[26]$ is such an anomaly, is because it is "too small". Essentially, for $[11n + k ]$, your way yields $ 4n + f(k)$ numbers and user's way yields $5n + g(k)$ solutions. Because $f(4) = 4, g(4) = 2$, hence for $[11\times 2 + 4]$, there is a tie (You forgot to add $22+1, 22+3$ to user's set). A better example would have been $[15]$, where your construction yields 1 more number. However, for large enough $n$ (like $ n \geq 5$), it's clear that your construction loses out since $ 4 \times 5 + 5 < 5 \times 5 + 0 $. – Calvin Lin May 04 '21 at 08:49
  • No I already solved it. Instead of $1,3,6,9,11$, start off with the base $1,3,4,6,9$. Now using same method, you have $905$. – combinatorialist46Carey2 May 04 '21 at 13:08
  • Count by $11$'s and then boom! $905$! – combinatorialist46Carey2 May 04 '21 at 13:08

0 Answers0