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

Home > Numbers
No Monochrome Sums (Posted on 2009-10-14) Difficulty: 3 of 5
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 (4)
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