数学オリンピック(1)

やや古い記事だが、
ここに、数学オリンピックの問題が載っていた。


http://d.hatena.ne.jp/hiroyukikojima/20080211

「ある世界的組織は6カ国のメンバーから構成される。組織のメンバーリストには1978人が登録し、各人が1,2,・・・,1978番と番号付けられている。このとき次のようなメンバーが少なくとも一人はいることを証明せよ。『その人の番号は同じ国の2人の人の番号の和であるか、あるいは同じ国のある人の番号のちょうど2倍である』」

何も思いつかないが、
この問題を次のように変えるとプログラミングの問題になる。

「ある世界的組織はmカ国のメンバーから構成される。組織のメンバーリストにはn人が登録し、各人が1,2,・・・,n番と番号付けられている。このとき次のようなメンバーがいない組合せがある最小のnを求めよ。『その人の番号は同じ国の2人の人の番号の和であるか、あるいは同じ国のある人の番号のちょうど2倍である』」

例えば、2カ国で考えると、
まず、1と2は別でなければならない。
また、2と4は別でなければならない。

1 4
2

すると、

1 4
2 3

このどちらにも5は付け加えられない。
よって、m=2の場合は、n=4。


m=3のとき、n=13。

1 4 7 10 13
2 3 11 12
5 6 8 9

m=4のとき、n=44。

1 3 5 15 17 19 26 28 40 42 44
2 7 8 18 21 24 27 33 37 38 43
4 6 13 20 22 23 25 30 32 39 41
9 10 11 12 14 16 29 31 34 35 36

m=5以降は組合せが膨大で求まりそうになかった。
ただ、1978ってことはなさそうだ。



#include
#include

using namespace std;

class cNation {
int nMembers;
vector members;
vector memberSpace;

public:
cNation(int n) {
nMembers = n;
memberSpace.resize(n + 1);
fill(memberSpace.begin(), memberSpace.end(), 0);
}
bool check(int iMember) const {
return memberSpace[iMember] == 0;
}
void addMember(int iMember) {
typedef vector::const_iterator CIT;
for(CIT p = members.begin(); p != members.end(); ++p) {
int n = *p + iMember;
if(n <= nMembers)
memberSpace[n]++;
memberSpace[abs(*p-iMember)]++;
}
memberSpace[iMember]++;
if(iMember * 2 <= nMembers)
memberSpace[iMember*2]++;

members.push_back(iMember);
}
void deleteMember(int iMember) {
if(iMember != members.back())
throw(1);
members.resize(members.size() - 1);

typedef vector::const_iterator CIT;
for(CIT p = members.begin(); p != members.end(); ++p) {
int n = *p + iMember;
if(n <= nMembers)
memberSpace[n]--;
memberSpace[abs(*p-iMember)]--;
}
memberSpace[iMember]--;
if(iMember * 2 <= nMembers)
memberSpace[iMember*2]--;
}
void print() const {
typedef vector::const_iterator CIT;
for(CIT p = members.begin(); p != members.end(); ++p) {
cout << *p << " ";
}
cout << endl;
}
};

int check(const vector& nations, int nMembers, int iMember);

int main() {
const int nMembers = 13;
const int nNations = 3;

vector posMember(nMembers+1);
vector space(nMembers+1);

vector nations(nNations, cNation(nMembers));
nations[0].addMember(1);
nations[1].addMember(2);

int iMember = 3;
int iNation = 0;
while(true) {
if(iNation < nNations) {
if(nations[iNation].check(iMember)) {
nations[iNation].addMember(iMember);
int iLimit = check(nations, nMembers, iMember);
if(iLimit != 0) {
nations[iNation].deleteMember(iMember);
iNation++;
continue;
}
posMember[iMember] = iNation;
if(iMember == nMembers)
break;
iMember++;
iNation = 0;
}
else {
iNation++;
}
}
else {
if(iMember == 3)
break;
iMember--;
iNation = posMember[iMember];
nations[iNation].deleteMember(iMember);
iNation++;
}
}

if(iMember == 3) {
cerr << "x" << endl;
}
else {
for(int i = 0; i < nNations; i++)
nations[i].print();
}

return 0;
}

int check(const vector& nations, int nMembers, int iMember) {
#if 1
if(iMember * 3 <= nMembers)
return 0;

typedef vector::const_iterator CIT;
for(int i = iMember + 1; i <= nMembers; i++) {
for(CIT p = nations.begin(); p != nations.end(); ++p) {
if(p->check(i))
goto packed;
}
return i;
packed:
;
}

#endif
return 0;
}