やや古い記事だが、
ここに、数学オリンピックの問題が載っていた。
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
#includeusing namespace std;
class cNation {
int nMembers;
vectormembers;
vectormemberSpace;
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;
vectorposMember(nMembers+1);
vectorspace(nMembers+1);
vectornations(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;
}