朝日新聞2005年12月2日のパズル横丁問題

問題

1,2,3,4,5,6,7,8,10の9個の数字をX,Yの箱に別々に分けて入れる。

それぞれの箱毎に任意の3つの数字を取り出すと差が異なるように分けるにはどうすれば良いか？

解答への道(ヒント)

9個の数字の組合せは全部で2⁹(=512)通り。この組合せをXに割り当て，残りの数字をYに割り当てる。

事前に3個の数字の組合せで問題ないかどうか計算しておく。

プログラムは以下のような感じになる。

#include "puzutl.h"

YesNo ok[1024];
int num[9] = {1,2,3,4, 5, 6, 7,  8, 10}; // 使われる数字
int bit[9] = {1,2,4,8,16,32,64,128,256}; // それらをビットに割り当てる

void create_okng()
{
  // 1,2,3,4,5,6,7,8,10 から任意の3個を取り出す場合の組合せと，その組合せで問題ないか事前に調べておく。
  for( int a=0; a< 9; a++) {
    for( int b=a+1; b< 9; b++) {
      for( int c=b+1; c< 9; c++) {
        int v = bit[a]|bit[b]|bit[c]; // 3個を取り出したときの数値
        if( num[c] - num[b] == num[b] - num[a]) ok[v] = NO;
        else                                    ok[v] = YES;
      }
    }
  }
}

YesNo checkOk( int x)
{
  任意の3個の組合せが全てOKかどうか調べる。
}

int main( int argc, cstring argv[])
{
  create_okng();
  // Box X に入れる組合せは全部で512通りある。
  // Box Y は Box X に入れた数字以外の数字を入れる。
  int X, Y;
  for( int i=0; i< 512; i++) {
    X = i;
    Y = ~X;
    if( checkOk(X) && checkOk(Y)) {
      見つかった
    }
  }
  return    0;
}

答えは2件出力されますが，X,Yの組合せが逆になるだけなので，実質1件です。

科学衛星はやぶさ君おめでとう。私の名前も小惑星イトカワに打ち込まれたってわけだ。

無事帰ってきて欲しいね。

今年もいよいよ最終月。歳をとると１年が経つのが速いこと，速いこと。

解速度

即