Color each of the numbers 1 through n either red or blue such that if a+b=c then a, b and c are not all the same color. The addends are distinct.
For example with n=6 the sequence
rbrbrb does not work because 2+4=6 but 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?
rrbrbbr
rrbrbbbr
rrbbrb
rrbbbr
rrbbbbr
rbrbr
rbrbbr
rbbr
rbbbr
are the possibilities, the longest of which is 8.
DECLARE SUB addOn ()
CLEAR , , 25000
DEFINT A-Z
DIM SHARED s$, did
PRINT
s$ = "r": did = 1
addOn
END
SUB addOn
forbidR = 0: forbidB = 0
FOR a = 1 TO (did + 1) / 2
b = did + 1 - a
IF MID$(s$, a, 1) = MID$(s$, b, 1) AND a <> b 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
NEXT a
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
For three colors there are 16,134 solutions altogether, of varying lengths; but this can be halved as half are just reversals of blue and green. The longest of these solutions has 23 members, of which there are six examples, but as noted, there are only three basic and the others interchange blue and green:
23 rrbrbbbrggrggggrggbgbrb
23 rrbrbbbrggrgggggrgbgbrb
23 rrbrbbbrggrgggggggbgbrb
23 rrgrgggrbbrbbbbrbbgbgrg
23 rrgrgggrbbrbbbbbrbgbgrg
23 rrgrgggrbbrbbbbbbbgbgrg
DECLARE SUB addOn ()
CLEAR , , 25000
DEFINT A-Z
DIM SHARED s$, did, max, maxS$(30), maxCt, solCt
PRINT
s$ = "r": did = 1
addOn
FOR i = 1 TO maxCt
PRINT max, maxS$(i)
NEXT
PRINT solCt
END
SUB addOn
forbidR = 0: forbidB = 0: forbidG = 0
FOR a = 1 TO (did + 1) / 2
b = did + 1 - a
IF MID$(s$, a, 1) = MID$(s$, b, 1) AND a <> b 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
NEXT a
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$
solCt = solCt + 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
|
|
Posted by Charlie
on 2009-10-14 15:09:47 |
computer solution
