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

Home > Numbers
No Monochrome Arithmetic Sequence (Posted on 2009-10-19) Difficulty: 3 of 5
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.)
Solution 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).

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 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#

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 A-Z
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 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 (9)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2017 by Animus Pactum Consulting. All rights reserved. Privacy Information