All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars
 perplexus dot info

 No Monochrome Arithmetic Sequence (Posted on 2009-10-19)
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.

 See The Solution Submitted by Jer No Rating

Comments: ( Back to comment list | You must be logged in to post comments.)
 computer solution Comment 1 of 1

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).

CLEAR , , 25000
DEFINT A-Z
DIM SHARED s\$, did

PRINT

s\$ = "r": did = 1

END

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

CLEAR , , 25000
DEFINT A-Z
DIM SHARED s\$, did, max, maxS\$(30), maxCt, strCT#

PRINT

s\$ = "r": did = 1

PRINT strCT#
FOR i = 1 TO maxCt
PRINT max, maxS\$(i)
NEXT
PRINT maxCt

END

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

CLEAR , , 25000
DEFINT A-Z
DIM SHARED s\$, did, max, mList\$(300), mCt

PRINT

s\$ = "r": did = 1

FOR i = 1 TO mCt
PRINT max, mList\$(i)
NEXT
PRINT mCt

END

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 2009-10-19 18:21:33

 Search: Search body:
Forums (0)