求A⊆{1,2,3,...,111},|A|=6∧∀B⊆{1,2,3,...,111},|B|=6⟹∃P⊆A∃Q⊆B∑P=∑Q>0

l4m2

求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：

1. int Check(int a, int b, int c, int d, int e, int f) {
   
2.     if (a<1 || a>111) return 0;
   
3.     if (b<1 || b>111) return 0;
   
4.     if (c<1 || c>111) return 0;
   
5.     if (d<1 || d>111) return 0;
   
6.     if (e<1 || e>111) return 0;
   
7.     if (f<1 || f>111) return 0;
   
8.     for (int i=1; i<=111; ++i)
   
9.     for (int j=1+i; j<=111; ++j)
   
10.     for (int k=1+j; k<=111; ++k)
    
11.     for (int l=1+k; l<=111; ++l)
    
12.     for (int m=1+l; m<=111; ++m)
    
13.     for (int n=1+m; n<=111; ++n) {
    
14.         for (int x=1; x<4096; ++x) {
    
15.             int s = 0;
    
16.             if (x & 1) s += a;
    
17.             if (x & 2) s += b;
    
18.             if (x & 4) s += c;
    
19.             if (x & 8) s += d;
    
20.             if (x & 16) s += e;
    
21.             if (x & 32) s += f;
    
22.             if (x & 64) s -= i;
    
23.             if (x & 128) s -= j;
    
24.             if (x & 256) s -= k;
    
25.             if (x & 512) s -= l;
    
26.             if (x & 1024) s -= m;
    
27.             if (x & 2048) s -= n;
    
28.             if (s == 0) goto OK;
    
29.         }
    
30.         return 0;
    
31. OK:;}
    
32.     return 1;
    
33. }

复制代码

l4m2

出题人事后介绍：
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.