perplexus.info :: Numbers : No Monochrome Arithmetic Sequence

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

Rating: 4.0000 (1 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)

computer solution

| Comment 1 of 2

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 A-Z
DIM SHARED s$, did

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 A-Z
DIM SHARED s$, did, max, maxS$(30), maxCt, strCT#

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 A-Z
DIM SHARED s$, did, max, mList$(300), mCt

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

Please log in:

Login:
Password:
Remember me:

Sign up! \| Forgot password

Search:

Search body:

Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (6)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:


perplexus dot info