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?
Hoping for reasonable run time, I made a version of Charlies program in C. It solved the three color case in under a second, but the four color case looks like it will take much longer.
#include <stdio.h>
// change just this line to change amount searched (and recompile)
#define COLORS 4
#if COLORS==4
#define LIMIT 70
#define PRINTLIM 66 // decrease this number for shorter solutions printed
#elseif COLORS==3
#define LIMIT 24
#define PRINTLIM 23 // decrease this number for shorter solutions printed
#else // COLORS==2
#define LIMIT 9
#define PRINTLIM 8 // decrease this number for shorter solutions printed
#endif
// known lengths for certain number of colors: (2,8), (3,23), (4,66)
int working_array[LIMIT];
void extend(int current_length) {
int colors_taken[COLORS];
int x, half=current_length/2 - 1;
for (x=0; x<COLORS; x++) { colors_taken[x]=0; }
for (x=0; x<=half; x++) {
if (working_array[x] == working_array[current_length-x-1]) {
colors_taken[working_array[x]] = 1;
}
}
if (colors_taken[0]==0) {
working_array[current_length]=0;
extend(current_length+1);
}
if (colors_taken[1]==0) {
working_array[current_length]=1;
extend(current_length+1);
}
#if COLORS>2
if (colors_taken[2]==0) {
working_array[current_length]=2;
extend(current_length+1);
}
#endif
#if COLORS>3
if (colors_taken[3]==0) {
working_array[current_length]=3;
extend(current_length+1);
}
#endif
if (current_length>=(PRINTLIM)) {
for (x=0; x<current_length; x++) {
switch (working_array[x]) {
case 0:
printf ("r");
break;
case 1:
printf ("b");
break;
case 2:
printf ("g");
break;
case 3:
printf ("y");
break;
default:
printf ("?");
} // end switch
}
printf(" ");
}
return;
}
int main () {
int x;
for (x=0; x<LIMIT; x++) { working_array[x]=0; }
printf("Starting: ");
extend(2); // start r,r
working_array[1]=1;
extend(2); // start r,b
printf(" Done ");
}
Edited on October 15, 2009, 3:31 pm
C program
