puzzleup 2016

newkid · 发表于 2016-8-19 00:41

solomon_007 发表于 2016-8-18 23:22
但是我只考虑有46张一种数字的也可以啊。。。

这样，至少2个数字，46+1张

那只是一种情形，不是严密的证明，你还得证明每种数都小于46的情况下，最后也是65。

首先证明65一定能覆盖5个数。反证法假设65不能覆盖5个数，则余下的35张就是不少于6种的所有的其它数字，其中必定有一种张数<6, 和第一个推论矛盾。
再来证明65是最小答案。假设有另一答案N<65, 只需举出一个反例：有6个数分别是6张牌，因为N是任取的，必定存在一种取法使得N避开了所有这6个数，所以这个N不符合要求。

solomon_007 · 发表于 2016-8-19 20:25

newkid 发表于 2016-8-19 00:41
那只是一种情形，不是严密的证明，你还得证明每种数都小于46的情况下，最后也是65。

首先证明65一 ...

证明65是最小答案，看了半天，没看懂。。。

newkid · 发表于 2016-8-19 21:18

solomon_007 发表于 2016-8-19 20:25
证明65是最小答案，看了半天，没看懂。。。

假设有另一答案N<65, 根据题设，无论这N个怎么取，无论N是什么样的组合，它必定要覆盖5个数，不能够存在一种情形，使得N只取到少于5个的数。
现在我们就来列举出一种情形，使得N可能取不到5个数。一个反例就足够。令数字1~6分别只有6张牌。剩下64张只能覆盖4个数字。那么，只要N取到的牌全在剩下的64张之中，这N张牌就只覆盖了4个数字，也即，这个N是不合格的。因为N<65, 这样取法的可能性是存在的。

所以N<65的假设是不成立的。

solomon_007 · 发表于 2016-8-19 22:10

newkid 发表于 2016-8-19 21:18
假设有另一答案N

多谢你耐心细致的解释，终于看懂了！

newkid · 发表于 2016-8-24 22:58

#5:
ONE HUNDRED COINS

In how many ways 100 gold coins can be divided into groups, so that the difference between any two groups is at most 2?

Note: Permutations are not considered as different.

Example: If the problem was asked for 6 coins, the answer would be 9:
(1,1,1,1,1,1), (1,1,1,1,2), (1,1,2,2), (1,1,1,3), (1,2,3), (2,2,2), (2,4), (3,3), (6).

在多少种方法可以将100个金币分组，使得任何两组之间的差异最多为2？

注意：不考虑排列的差异。

例如：如果问的是6个硬币，答案是9：
(1,1,1,1,1,1), (1,1,1,1,2), (1,1,2,2), (1,1,1,3), (1,2,3), (2,2,2), (2,4), (3,3), (6).

这题很简单吧？分析几个就看出规律了。

newkid · 发表于 2016-8-25 03:17

100个硬币分成不同组数的分法数量，请挑错：总和1325

GROUPS       CNT
---------- ----------
      1       1
      2       2
      3       2
      4       3
      5       3
      6       4
      7       4
      8       5
      9       5
      10       6
      11       6
      12       7
      13       7
      14       8
      15       8
      16       9
      17       9
      18       10
      19       10
      20       11
      21       11
      22       12
      23       12
      24       13
      25       13
      26       14
      27       14
      28       15
      29       15
      30       16
      31       16
      32       17
      33       17
      34       18
      35       18
      36       19
      37       19
      38       20
      39       20
      40       21
      41       21
      42       22
      43       22
      44       23
      45       23
      46       24
      47       24
      48       25
      49       25
      50       26
      51       25
      52       25
      53       24
      54       24
      55       23
      56       23
      57       22
      58       22
      59       21
      60       21
      61       20
      62       20
      63       19
      64       19
      65       18
      66       18
      67       17
      68       17
      69       16
      70       16
      71       15
      72       15
      73       14
      74       14
      75       13
      76       13
      77       12
      78       12
      79       11
      80       11
      81       10
      82       10
      83       9
      84       9
      85       8
      86       8
      87       7
      88       7
      89       6
      90       6
      91       5
      92       5
      93       4
      94       4
      95       3
      96       3
      97       2
      98       2
      99       1
   100       1

100 rows selected.