AP or No AP? Part (ii)

The solution to this problem becomes a bit cumbersome but I will try to explain it to the best of my abilities. I will only be providing an overview of what actually happens in the proof as the proof in itself is tedious.

Proof of the lower bound: To prove that $n \ge 124$ I just need to remove 11 numbers from { $1,2, \dots , 123$ } such that no AP of length 12 remains in the set. Let { $1,13,24,35, \dots, 112$ } be the 12 numbers removed. Since 11 is prime there can exist no AP of common difference and length 12 less than 11 and it is easy to note that there is no AP of common difference 11 and length 12. There obviously cannot be any AP of common difference 12 or more since there are not enough terms in the set. Thus we have $n \ge 124$ .

Proof of the upper bound: I will only mention the steps involved in the proof without going into the details. Let $a_i$ denote the difference between the $i^{th}$ and $(i+1)^{th}$ numbers that are removed from the set { $1,2, \dots , 123$ }. First we show that $a_i$ can be less than 11 or more than 12 at most once. This requires the use of some basic number theory and Pigeon Hole Principle. Once we have achieved this we can characterize the only valid removals and show that each of these will contain an AP of length 12 ending at 124.

There is no problem to provide fully explained solution but this could be long. One thing for sure is we cannot allow {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, and 12} to stay.

Best found examples of 11 taken: {12, 23, 34, 45, 56, 67, 78, 89, 100, 111, and 112} and {13, 24, 35, 46, 57, 68, 79, 90, 101, 112, 1}, where the order of arrangement doesn't matter.

Best particular answers shared [3, 14, 25, 36, 47, 58, 69, 80, 91, 102, 113, and 124].

Using computer algorithm, I changed my mind of 144 or 132 into 124. Then 23 < n <= 124 came to my mind. I first thought about 1~12, 13~24... 121~132, 133~144, and I found that {12, 23, 34, 45, 56, 67, 78, 89, 100, 111, 122} makes a good blockage. Using computer, I am able to check via T (n) = a + (n - 1) d for shortest fit. 1~11, 12~22 ... are compared.

{12, 23, 34, 45, 56, 67, 78, 89, 100, 111, and 122} just by guessing is not convincing. I add in a check by having generator of the 11 numbers and run for a check.

 {11 picked from IterConst generator begins}
 FOR i: =1 TO IterConst DO
     T[i]:=i;
 count:=0;
 REPEAT
       i:=RANDOM(IterConst)+1;
       IF T[i]<>0 THEN
       BEGIN
            T[i]:=0;
            INC(count)
       END
 UNTIL count=IterConst-11;
 count:=0;
 FOR i:=1 TO IterConst DO
     IF T[i]<>0 THEN
     BEGIN
          INC(count);
          n[count]:=T[i]
     END;
 {11 picked from IterConst generator ends}

Fill all T(i) = i with IterConst initially as 23, take away (IterConst-11) randomly, extract the 11 wanted as premium blockages into another continuous n[i].

Step by step, we can see that required terms shall always exceed space available when premium blockages are selected. If we don't add according to need, then no AP can be there. Example with {12, 23, 34, 45, 56, 67, 78, 89, 100, 111 ...} the next must need 122, 123 or 124. Before this {12, 23, 34, 45, 56, 67 ...} needs more than 67, {12, 23, 34, 45, 56, 67, 78 ...} needs more than 78 and etc. Computer simulation gives similar patterns to convince our guessing.

With generator above, you can write own algorithm to see. My computer scans with IterConst = 87, 88, 89 and 90 using a long time with random generator. 91 is still running while writing this; finally, blockages found as {8, 19, 30, 41, 48, 52, 63, 68, 70, 74, 85} which require 97 at least for [86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97], else example [1, 12, 23, 34, 45, 56, 67, 78, 89, 100, 111, 122]. 85 + 11 = 96 is next block required. {8, 19, 30, 41, 52, 63, 74, 85} are hits and {48, 68, 70} are miss hits. We can't rely onto computer's speed deficiency. Probability of hit is very little. By analysis, we can know for certain that 124 is the answer.