Color each of the numbers 1 through n either red or blue such that if a, b and c are consecutive numbers in an arithmetic sequence then they are not all the same color.
For example with n=6 the sequence
rbrbrb does not work because 1,3,5 are all red and 2,4,6 are all blue.
Whereas rbrbbr does work.
What is the largest value of n for which such a sequence exists?
Note: Since the colors can be swapped, make the number 1 red.
Add a third color (green.) What is the new maximum value of n?
Instead of a third color, add a fourth term (d) so that a, b, c, and d cannot all be the same color if they are in an arithmetic sequence.
These are the possible strings, given to the highest n value before running out of a suitable choice:
rrbrrbb
rrbrbb
rrbbrrbb n=8
rrbbrbr
rrbbrbb
rbrrbrb
rbrrbb
rbrbbrr
rbrbbrbr n=8
rbbrrbbr n=8
rbbrbr
rbbrbb
There are 3 that have the largest n value (n=8).
DECLARE SUB addOn ()
CLEAR , , 25000
DEFINT AZ
DIM SHARED s$, did
PRINT
s$ = "r": did = 1
addOn
END
SUB addOn
forbidR = 0: forbidB = 0
FOR diff = 1 TO did / 2
IF diff * 2 < did + 1 THEN
a = did + 1  2 * diff
b = did + 1  diff
IF MID$(s$, a, 1) = MID$(s$, b, 1) THEN
IF MID$(s$, a, 1) = "r" THEN
forbidR = 1
IF forbidB THEN EXIT FOR
ELSE
forbidB = 1
IF forbidR THEN EXIT FOR
END IF
END IF
END IF
NEXT diff
IF forbidR = 0 THEN
s$ = s$ + "r": did = did + 1: addOn: did = did  1: s$ = LEFT$(s$, did)
END IF
IF forbidB = 0 THEN
s$ = s$ + "b": did = did + 1: addOn: did = did  1: s$ = LEFT$(s$, did)
END IF
IF forbidR AND forbidB THEN PRINT s$
END SUB
With 3 colors, a string of length 26 is possible (n=26). There are 16 such (but this includes repetitions of the same patterns with blue and green reversed, so there are really only 8 patterns of this length):
rrbbrrbgbggrgrrbrbbgrggbgb
rrbbgrrgrgbbggbbgrgrrgbbrr
rrbgbrrgrgbbggbbgrgrrbgbrr
rrgbgrrbrbggbbggbrbrrgbgrr
rrggrrgbgbbrbrrgrggbrbbgbg
rrggbrrbrbggbbggbrbrrbggrr
rbrrbrbggbbggbrbrrbggrrgrg
rbrbbrrgbbgbgrrggrrgbgbbgr
rbrbbrrgbbgbgrrggrrgbgbbgb
rbrbbgbrrgrggbgbbrbrggrrgg
rbggbgbrrbbrrbgbggbrrggrgr
rgrrgrgbbggbbgrgrrgbbrrbrb
rgrggrrbggbgbrrbbrrbgbggbr
rgrggrrbggbgbrrbbrrbgbggbg
rgrggbgrrbrbbgbggrgrbbrrbb
rgbbgbgrrggrrgbgbbgrrbbrbr
DECLARE SUB addOn ()
CLEAR , , 25000
DEFINT AZ
DIM SHARED s$, did, max, maxS$(30), maxCt, strCT#
PRINT
s$ = "r": did = 1
addOn
PRINT strCT#
FOR i = 1 TO maxCt
PRINT max, maxS$(i)
NEXT
PRINT maxCt
END
SUB addOn
forbidR = 0: forbidB = 0: forbidG = 0
FOR diff = 1 TO did / 2
IF diff * 2 < did + 1 THEN
a = did + 1  2 * diff
b = did + 1  diff
IF MID$(s$, a, 1) = MID$(s$, b, 1) THEN
IF MID$(s$, a, 1) = "r" THEN
forbidR = 1
IF forbidB AND forbidG THEN EXIT FOR
ELSEIF MID$(s$, a, 1) = "b" THEN
forbidB = 1
IF forbidR AND forbidG THEN EXIT FOR
ELSE
forbidG = 1
IF forbidR AND forbidB THEN EXIT FOR
END IF
END IF
END IF
NEXT diff
IF forbidR = 0 THEN
s$ = s$ + "r": did = did + 1: addOn: did = did  1: s$ = LEFT$(s$, did)
END IF
IF forbidB = 0 THEN
s$ = s$ + "b": did = did + 1: addOn: did = did  1: s$ = LEFT$(s$, did)
END IF
IF forbidG = 0 THEN
s$ = s$ + "g": did = did + 1: addOn: did = did  1: s$ = LEFT$(s$, did)
END IF
IF forbidR AND forbidB AND forbidG THEN
PRINT s$
strCT# = strCT# + 1
IF did > max THEN
max = did: maxCt = 1: maxS$(1) = s$
ELSEIF did = max THEN
maxCt = maxCt + 1: maxS$(maxCt) = s$
END IF
END IF
END SUB
If the fourth term option is used instead of a third color, there are 14 sequences with n=34, which is the maximum.
rrbrrrbbbrbrrbrrrbbbrbrrbrrrbbbrbb
rrbrrrbbbrbrrbrrrbbbrbbrbrrrbbbrbr
rrbrrrbbbrbrrbrrrbbbrbbrbrrrbbbrbb
rrbrrrbbbrbbrbrrrbbbrbrrbrrrbbbrbr
rrbrrrbbbrbbrbrrrbbbrbrrbrrrbbbrbb
rrbrrrbbbrbbrbrrrbbbrbbrbrrrbbbrbr
rrbrrrbbbrbbrbrrrbbbrbbrbrrrbbbrbb
rbrbbbrrrbrrbrbbbrrrbrrbrbbbrrrbrb
rbrbbbrrrbrrbrbbbrrrbrbbrbbbrrrbrr
rbrbbbrrrbrrbrbbbrrrbrbbrbbbrrrbrb
rbrbbbrrrbrbbrbbbrrrbrrbrbbbrrrbrr
rbrbbbrrrbrbbrbbbrrrbrrbrbbbrrrbrb
rbrbbbrrrbrbbrbbbrrrbrbbrbbbrrrbrr
rbrbbbrrrbrbbrbbbrrrbrbbrbbbrrrbrb
DECLARE SUB addOn ()
CLEAR , , 25000
DEFINT AZ
DIM SHARED s$, did, max, mList$(300), mCt
PRINT
s$ = "r": did = 1
addOn
FOR i = 1 TO mCt
PRINT max, mList$(i)
NEXT
PRINT mCt
END
SUB addOn
forbidR = 0: forbidB = 0
FOR diff = 1 TO did / 2
IF diff * 3 < did + 1 THEN
a = did + 1  3 * diff
b = did + 1  2 * diff
c = did + 1  diff
IF MID$(s$, a, 1) = MID$(s$, b, 1) AND MID$(s$, c, 1) = MID$(s$, b, 1) THEN
IF MID$(s$, a, 1) = "r" THEN
forbidR = 1
IF forbidB THEN EXIT FOR
ELSE
forbidB = 1
IF forbidR THEN EXIT FOR
END IF
END IF
END IF
NEXT diff
IF forbidR = 0 THEN
s$ = s$ + "r": did = did + 1: addOn: did = did  1: s$ = LEFT$(s$, did)
END IF
IF forbidB = 0 THEN
s$ = s$ + "b": did = did + 1: addOn: did = did  1: s$ = LEFT$(s$, did)
END IF
IF forbidR AND forbidB THEN
PRINT s$
IF LEN(s$) >= max THEN
IF LEN(s$) > max THEN mCt = 0
max = LEN(s$): mCt = mCt + 1
mList$(mCt) = s$
END IF
END IF
END SUB

Posted by Charlie
on 20091019 18:21:33 