四个不被3整除的整数，它们能够用加减法得出一个9的倍数

hbghlyj

对于四个不被3整除的整数，它们能够用加减法得出一个9的倍数 等价于 不存在a使得其中恰好三个数模9在{a,9-a}里。
如1 4 7 8可以：-1+4+7+8=18
但1 1 2 8不行

hbghlyj

Python

1. from itertools import product
2. from collections import Counter
4. def is_valid_tuple(t):
5.     for signs in product([-1, 1], repeat=4):
6.         if sum(sign * num for sign, num in zip(signs, t)) % 9 == 0:
7.             return True
8.     return False
10. def has_one_number_appearing_three_times(t):
11.     transformed = [abs((x + 4) % 9 - 4) for x in t]
12.     counts = Counter(transformed)
13.     return 3 in counts.values() and len(counts) == 2
15. for t in product((1,2,4,5,7,8), repeat=4):
16.     if is_valid_tuple(t) == has_one_number_appearing_three_times(t):
17.         print(t, 'failed')
19. print('done')

Copy the Code

验证完毕！没有反例。

请问如何证明呢？

tommywong

題目限制了這四個數在{1,2,4,5,7,8}裡，{a,9-a}只可能是{1,8},{2,7},{4,5}。
因為有四個數，所以至少有兩個數在{a,9-a}裡。

一. 存在a使得其中恰好兩個數在{a,9-a}裡，另外兩個分別在{b,9-b}和{c,9-c}裡。
其中有三個數用加減法可以得到的結果將會是
{1,8}+{2,7}+{4,5}={1,3,6,8}+{4,5}={1,2,3,4,5,6,7,8}
所以其中一個結果必然可以跟第四個數用加減法得出一个9的倍數。

二. 存在a,b使得其中恰好兩個數在{a,9-a}裡，而另外兩個數在{b,9-b}裡。
{a,9-a}+{a,9-a}={-2a,0,2a}，所以這兩個數用加減法可以得出一個9的倍數。
另外兩個數也可以用加減法可以得出一個9的倍數，這兩個9的倍數加起來又是9的倍數。

三. 存在a使得其中恰好三個數在{a,9-a}裡。
{a,9-a}+{a,9-a}+{a,9-a}={-2a,0,2a}+{a,-a}={-3a,-a,a,3a}
最後一個數既不可以是3的倍數，也不在{a,9-a}裡，所以這四個數用加減法不可能得出一個9的倍數。

四. 存在a使得四個數都在{a,9-a}裡。
{a,9-a}+{a,9-a}={-2a,0,2a}
{-2a,0,2a}+{-2a,0,2a}={-4a,-2a,0,2a,4a}
所以這四個數用加減法可以得出一個9的倍數。

題目中的數似乎不方便換成其它數。