PUZZLEUP 2015

lugionline

我并不要参加比赛啊，所以我完全可以自己定义一套适用的，另外你觉得从我的结果转换到比赛需要的答案会很麻烦吗？M最多一句话

倒数第二步完全没必要堵，因为你不能改变最终胜负结果，也不能改变比赛的下子数目，所以下在哪里并不重要，正是你们的题目中所说的

newkid

lugionline 发表于 2015-12-7 15:24
我并不要参加比赛啊，所以我完全可以自己定义一套适用的，另外你觉得从我的结果转换到比赛需要的答案会很麻 ...

确实在这个例子中X最后一个子并不重要，因为结果都一样。题目只要求给出胜者和步数，满足条件的下法有多种。
这个新版ITPUB真是太不给力了吧，以前的版本有很多贴都超过500楼了。

newkid

最后一题：

#20 POWERS OF THREE

7 students have selected some numbers which are powers of 3 (1, 3, 9, 27, 81,...). Interestingly, all the students have the same total when they add their numbers. Among all selected numbers if the mostly selected number has been selected X times, what can be the minimum value for X?

Note: A student may select a number more than once.

7个学生选择了一些数字，它们都是3的幂(1,3,9,27,81)。有趣的是，如果每个学生把他们的数字加起来，得到的总计都是相同的。在所有这些被选择的数字当中，如果选择次数最多的是X次，那么X可能的最小值是多少？

注意：一个学生可以多次选择同一个数字。

newkid

只能凑出X=5:
9
9
9
9
9
3+3+3
3+3+1+1+1

〇〇

newkid 发表于 2015-12-10 04:05
只能凑出X=5:
9
9

如果4次，要求另3个都用2次表示1个数，还不能全1样

lugionline

必须存在一个X=4的解啊，否则这题目也太差劲了

好吧，这题目可以证明不存在X=4的解

〇〇

lugionline 发表于 2015-12-10 10:33
必须存在一个X=4的解啊，否则这题目也太差劲了

编个程序

newkid

lugionline 发表于 2015-12-10 10:33
必须存在一个X=4的解啊，否则这题目也太差劲了

好吧，这题目可以证明不存在X=4的解

貌似证明也不难？要使得SUM一样就得拆，一个至少得拆成三个。

lugionline

newkid 发表于 2015-12-10 22:44
貌似证明也不难？要使得SUM一样就得拆，一个至少得拆成三个。

你这是猜测，不是证明，先算出一个解来：



然后来证明
记
    M 人数
    d  基数(实际值是3)
    K  指数，d^K 就是可以选择的数字
    X  可以选择的最大次数
假定最后选择的结果中最大的那个值是 d^(K+1)
因为这个值最多只能被选X次，也就是说最多只有X人能选择这个数字
那么剩下的 M - X 个人只能选择剩余的 (1, d, d^2, ... d^K) 这些数字，并且这些数字最多只能选择 X 次
但是他们每个人选择的总和 必然要比 d^(K+1)大，因为根据假定有人选择这个 d^(K+1)
这就要求
    X * (1 + d + d^2 + ... + d^K) >= (M - X) * d^(K + 1)
也就是要求
    X * (d^(K + 1) - 1) / (d - 1) >= (M - X) * d^(K + 1)
解出X
    X >= M * (d - 1) / (d - 1 / d^(K + 1))
代入 M = 7, d = 3 得到
    X >= 14/(3 - 1/3^(K+1)) >= 4.6
X 是整数，所以 X >= 5

〇〇

lugionline 发表于 2015-12-11 10:30
你这是猜测，不是证明，先算出一个解来：

你的矩阵是什么意思