puzzleup 2016

newkid

棋盘尺寸的奇偶性还是有影响的，会影响到一个数是在黑色还是白色格子。
我是观察到每当两个数颜色相同而位置互换时，就会额外多一步。如果另外一种颜色也有这种情形，那么在解决当前颜色时也会顺便解决另外一种颜色，所以只需考虑解决一种颜色就行了。这样的话64中的一种颜色就是32个格子，即16对，就是那个公式中64/4的意思。

lugionline

给个证明，看看有没有漏洞 (要证明的公式写错了，重新改了下)

记 X(单数/双数，单数/双数位置) 表示 X 这个数是单数/双数，当前处于 单数/双数位置
如果 X 处于 X 的位置，那么就说 X 处于本位

归纳法证明

任何一个 N长度的 序列都可以经过 [(N + 1) / 4] + N - 1 次交换恢复到原始序列 (以下所有 [] 表示Floor)

对于 N = 1，2，3，4 显然

假设 N = k 时成立 (k >= 4)

对于 N = k + 1 (我们要证明交换次数不超过 [(k + 1 + 1) / 4] + k + 1 - 1 = [(k + 2) / 4] + k )

分以下几种情况

第一种：假设有一个数已经处于自己的位置了，那么把剩余的 k 个数重新标记
    只需要 [(k + 1) / 4] + k - 1 < [(k + 2) / 4] + k, 显然成立

第二种：假设有一个 X(单数，双数位置) (或者有一个 x(双数，单数位置))，
    那么只需要把 这个数和 X位置的这个数 Y(双数或者单数，单数位置) 交换
    就能让 X 处于本位，然后把剩余的 k 个数重新标记
    只需要 1 + [(k + 1) / 4] + k - 1 = [(k + 1) /4] + k < [(k + 2) / 4] + k, 成立

第三种：所有的数都是 (单数, 单数位置)，或者 (双数，双数位置)
    任取一个单数和一个双数 (一定能找到，因为 k + 1 >= 5)
    记为： X(单数, 单数位置) Y(双数，双数位置)
    对于： 处于X位置的那个数，记为 X'(单数，单数位置)
    对于： 处于Y位置的那个数，记为 Y'(双数，双数位置)
    显然 X, Y, X', Y' 是不同的数，否则就是第一种情况
    交换 X(单数, 单数位置), Y(双数，双数位置) --------这里使用了一步
    新的状态是
        X(单数，双数位置)
        Y(双数, 单数位置)
        X'(单数，单数位置)
        Y'(双数，双数位置)
        交换 X(单数，双数位置) 和 X'(单数，单数位置) -----这里使用了一步
    交换 Y(双数, 单数位置) 和 Y'(双数，双数位置) -----这里使用了一步
    新的状态是
        X(单数，单数位置) -- 处于自己的本位
        Y(双数, 双数位置) -- 处于自己的本位
        X'(单数，双数位置)
        Y'(双数，单数位置)

    现在 X, Y 已经处于自己的本位，考察 X', Y'，分两种情况：
第三1种：
    如果 X' 和 Y' 交换后能使 X', Y' 处于自己的本位，那么使用的总步数是
          3 + 1 + [(k - 3 + 1) / 4] + k - 3 - 1 -- 一共移动4步，剩余 k - 3 个
        = [(k - 2) / 4] + k < [(k + 2) / 4] + k
第三2种：
    否则 X'(单数，双数位置) 可以和 X'位置的那个数 X''(单数，单数位置) 交换
         Y'(双数, 单数位置) 可以和 Y'位置的那个书 Y''(双数, 双数位置) 交换
    同样使 X', Y' 处于自己的本位，使用的总步数是
          3 + 2 + [(k - 3 + 1) / 4] + k - 3 - 1
        = [(k - 2) / 4] + k + 1 = [(k + 2) / 4] + k
    成立

Q.E.D.

上面的过程其实也是一个构造需要  [(N + 1)  /  4] + N - 1 步序列的过程，所以这个就是答案

newkid

lugionline 发表于 2016-11-28 11:35
给个证明，看看有没有漏洞

记 X(单数/双数，单数/双数位置) 表示 X 这个数是单数/双数，当前处于 单数/ ...

最后一句话的意思是，这也是最少的步数？

lugionline

证明了使用步数最多不超过 [(N + 1)  /  4] + N - 1，然后 根据 第三2种 可以构造一个需要这些步的序列

〇〇

No: 19       November 30, 2016  



MIXTURES

MIXTURES

Mixtures will be obtained using a set of 18 different color paints.

-Every mixture should have 6 different colors.
-Every combination of 3 different colors should be contained in at least one mixture.

What is the minimum number of mixtures that can be formed according to these rules?

If the problem was asked for a set of 6 colors, 3 colors in each mixture and the combinations of 2 colors then the answer would be 6:

(1-2-4), (1-3-6), (1-4-5), (2-3-5), (2-5-6), (3-4-6)

没看懂英文

〇〇

〇〇 发表于 2016-11-30 22:22
No: 19       November 30, 2016  

不知道对不对
18种颜色进行混合,
规则
-每种混合含6个不同颜色
-每个3色组合至少出现在1个混合中
至少有几种混合
如果3色混合,2色组合至少出现1次,那么至少有6种

newkid

以前也出过类似的题，我没做出来。

newkid

这题可以用归纳法，用小集合推出大集合。

〇〇

先把18个分成3个1组,前3个混合,每个放2组
然后再分成另外3个1组...

newkid

〇〇 发表于 2016-12-1 07:53
先把18个分成3个1组,前3个混合,每个放2组
然后再分成另外3个1组...

看不懂，我猜测答案122。