Section 17.2 Algorithm
Acknowledgement and credit for Dr. Aaron Robertson who assisted me on this project by proposing this algorithm to solve this problem. In Dr.Robertson?s original words, the algorithm goes like this:
The most straightforward, but quick way to do this, is via a backtracking algorithm. Using the colours \(0\) and \(1\text{,}\) assume we have a colouring of \([1,n-1]\) that does not contain a monochromatic set of the form \(a,b,a+b,ab\text{.}\) We then attempt to colour integer \(n\text{.}\) We start by assigning integer \(n\) colour \(0\text{.}\) We then only need to check if our colouring of \([1,n]\) avoids monochromatic sets of the form \(a,b,a+b,ab\) where one of \(a+b\) or \(ab\) equals \(n\text{.}\) If no monochromatic set, we move on to colouring \([1,n+1]\text{.}\) If there is a monochromatic set, we change the colour of integer \(n\) to \(1\) and check again. If integer \(n\) being either colour \(0\) and \(1\) results in a monochromatic set, then we backtrack to integer \(n-1\text{.}\) If it is colour \(0\) then we change it to colour 1 and repeat the monochromatic check. If it is colour 1, then we backtrack again to \(n-2\text{.}\) This will eventually halt provided we are guaranteed a monochromatic set (which we are with 2 colours).
By the what is stated in the problem, for the case where \(a\not= b\text{,}\) the returned number will be \(252\text{,}\) with the case \(a = b\text{,}\) it is expected to return a number less than 252 which we do not know the exact value of.