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

 No Monochrome Sums (Posted on 2009-10-14)
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?

 See The Solution Submitted by Jer No Rating

Comments: ( Back to comment list | You must be logged in to post comments.)
 C program Comment 9 of 9 |

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
 Posted by Brian Smith on 2009-10-15 15:30:45

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

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