求A⊆{1,2,3,...,111},|A|=6∧∀B⊆{1,2,3,...,111},|B|=6⟹∃P⊆A∃Q⊆B∑P=∑Q>0
本帖最后由 l4m2 于 2024-1-20 01:10 编辑求A⊆{1,2,3,...,111}, |A|=6 ∧ ∀B⊆{1,2,3,...,111}, |B|=6 ⟹ ∃P⊆A ∃Q⊆B ∑P=∑Q>0
在QQ群讨论过，BeerRabbit推翻了
∀A⊆{1,2,3,...,111}, ∀B⊆{1,2,3,...,111}, |A|=6 ∧ |B|=6 ⟹ ∃P⊆A ∃Q⊆B ∑P=∑Q>0
，证明了
∀B⊆{1,2,3,...,111}, |B|=6 ⟹ ∃A⊆{1,2,3,...,111}, |A|=6 ∧ ∃P⊆A ∃Q⊆B ∑P=∑Q>0
但是这俩都与原问题无关
为了避免有人混淆概念，给出参数使得下面的函数返回1：int Check(int a, int b, int c, int d, int e, int f) {
if (a<1 || a>111) return 0;
if (b<1 || b>111) return 0;
if (c<1 || c>111) return 0;
if (d<1 || d>111) return 0;
if (e<1 || e>111) return 0;
if (f<1 || f>111) return 0;
for (int i=1; i<=111; ++i)
for (int j=1+i; j<=111; ++j)
for (int k=1+j; k<=111; ++k)
for (int l=1+k; l<=111; ++l)
for (int m=1+l; m<=111; ++m)
for (int n=1+m; n<=111; ++n) {
for (int x=1; x<4096; ++x) {
int s = 0;
if (x & 1) s += a;
if (x & 2) s += b;
if (x & 4) s += c;
if (x & 8) s += d;
if (x & 16) s += e;
if (x & 32) s += f;
if (x & 64) s -= i;
if (x & 128) s -= j;
if (x & 256) s -= k;
if (x & 512) s -= l;
if (x & 1024) s -= m;
if (x & 2048) s -= n;
if (s == 0) goto OK;
}
return 0;
OK:;}
return 1;
}
出题人事后介绍：
This puzzle was from Ali Gurel, where the idea is you want to select k numbers from {1 ... n} such that every other way to select k numbers would get a subset sum collision with you. His original version had k = 5. I did a very similar search as you you did to solve this problem using a naive O((n choose k)^2) way, and I realized with pruning you can do it much faster, so I could do k = 6. I noted that the solution is easier to verify than it is to compute and that's how I came up with this puzzle.
页:
[1]