Puzzleup 2010 比赛快开始了，大家用SQL解答啊

〇〇

又见抽屉原则

lastwinner

原帖由 newkid 于 10-10-7 02:05 发表
对啊，我本来是想着颜色编号，后来糊涂了，竟然用5作为盒子数去算。应该用11, 这样我的两个答案就是 CEIL(107/11)=10 和 CEIL(23/11)=3

对，是应该是10，我算的6不满足题意

nlrte13

原帖由 newkid 于 2010-9-30 23:40 发表
奥数哥还在不？为了不让你国庆闲得慌，挑战这个难题怎么样？
http://tieba.baidu.com/f?kz=883265251
作者：生肖迷宫

一种极端抽象的模型，虽然其难度已经早就不适合普通智力题玩家，但对数学家或者软件高手来说，这是一道非常难得的好题：
假设从6种神经元中挑出6个（有可能是1到6种），用神经纤维连接两两之间，使这6个神经元之间的连接符合某种规则，（比如说A-B、B-C、C-A、 A-E、D-A、D-F）就形成了一个特点的记忆元，多联少联都不对。当然神经元与这6个外其它神经元的连接并不影响这6个内部之间组合。假设现在有足够的神经元，尚无神经纤维连接，请问你至少需要多少个纤维才能保证形成过某种特定的记忆元？（形成过的意思就是包括在放纤维过程中形成过，后来又可能多联了而失去的情况。）

举个例子，假设现有某个连接如下：
A-B
| |
B-C-C-D
当再加一个神经变成
A-B
|/|
B-C-C-D
就是另一个记忆体，
当与别的神经元相连，如图
A-B
|/|
B-C-C-D
|
F
那么前一个记忆体依然有效，并且同时产生多个新的记忆体，如
A-B
|/|
B-C-C
|
F
或
A
|
B-C-C-D
|
F
等等。

涉及到图论、拓扑学，估计有了答案我也看不懂。

把这道题的第一步先简化一下，看看SQL能否搞定：
四个神经元（可以相同也可以不同）可以组成多少种不同的记忆体？

汗，“奥数哥”这名字太囧了。。。
咋会闲得慌呢，妹妹结婚，朋友生娃，同学庆生，忙都忙不转哦 - -#

话说这个题目我以前做过类似的，连接各种逻辑门产生不同的逻辑电路单元
貌似可以用迭代求解，小块组大块，中间消去
比如两块的 A-A A-B B-B，可以消去 A-B 变成 A-A-B-B

nlrte13

原帖由 newkid 于 2010-10-6 21:52 发表
#13 Colored Balls


You have 111 balls of five different colors. There is at least one ball of each color. You are placing these balls randomly into 11 boxes, on the condition that each box contains at least one ball. You can deduce that in any such placement at least one of the boxes must contain at least X balls of the same color.

What is the maximum possible value for X?

你有五种不同颜色的111个球，每种颜色至少一个。你把球随机放到11个盒子里，每个盒子至少一个球。你可以推断出，不管如何摆放，至少有一个盒子具有相同颜色的X个球。X可能的最大值是多少？

老外的题目还是一如既往的简单呐^^

[(111-1) / 5] + 1 = 23
[(23-1) / 11] + 1 = 3
注：“[]”这里表示取整，哈哈

newkid

原帖由 nlrte13 于 2010-10-8 10:40 发表

汗，“奥数哥”这名字太囧了。。。
咋会闲得慌呢，妹妹结婚，朋友生娃，同学庆生，忙都忙不转哦 - -#

话说这个题目我以前做过类似的，连接各种逻辑门产生不同的逻辑电路单元
貌似可以用迭代求解，小块组大块，中间消去
比如两块的 A-A A-B B-B，可以消去 A-B 变成 A-A-B-B

哈哈，这名号响亮得很，你就从了吧！
这个迭代算法具体是什么样的？因为题目是要求搭建过程中形成过某种记忆体（后来可能失去），所以不是简单的大图包含小图的问题，变复杂了很多。在新生成一条边时，不仅可以用旧的顶点，还可以生成新顶点，要穷举几乎是不可能的。

以四个神经元，而且四个都是同一种为例，需要7条边：

*-*
| |
* *

*-*       *-*
| |\  新:   |\
* * *       * *

*-*       *-*
| |\  新: | |
*-* *     *-*

*-*        *-*       *-*  
|\|\  新： |\|        \|\
*-* *      *-*         * *

*-*          *-*
|X|\  新:    |X|
*-* *        *-*
你先帮我核实一下四种神经元是不是可以构成566种图？

nlrte13

原帖由 newkid 于 2010-10-8 22:08 发表




哈哈，这名号响亮得很，你就从了吧！
这个迭代算法具体是什么样的？因为题目是要求搭建过程中形成过某种记忆体（后来可能失去），所以不是简单的大图包含小图的问题，变复杂了很多。在新生成一条边时，不仅可以用旧的顶点，还可以生成新顶点，要穷举几乎是不可能的。

以四个神经元，而且四个都是同一种为例，需要7条边：

*-*
| |
* *

*-*       *-*
| |\  新:   |\
* * *       * *

*-*       *-*
| |\  新: | |
*-* *     *-*

*-*        *-*       *-*  
|\|\  新： |\|        \|\
*-* *      *-*         * *

*-*          *-*
|X|\  新:    |X|
*-* *        *-*
你先帮我核实一下四种神经元是不是可以构成566种图？

难就难在这个“过程中”也算，不然就和那个电路题一样了
这里应该需要一个巧妙的新思路
迭代是说：
6 = 5 + 1
5 = 4 + 1
4 = 3 + 1
。。。
2 = 1 + 1

[ 本帖最后由 nlrte13 于 2010-10-9 10:22 编辑 ]

nlrte13

3个神经元组成一个记忆体的情况比较好算（这样不用考虑“过程中”）
若有x种神经元，则需要 ( x^2 + x ) * 3 / 2 条神经纤维

[ 本帖最后由 nlrte13 于 2010-10-9 10:57 编辑 ]

nlrte13

若不考虑“过程中”（存在就算），
4个神经元组成一个记忆体的情况，
若有x种神经元，则需要 3*( x^2 + x ) 条神经纤维

[ 本帖最后由 nlrte13 于 2010-10-9 15:07 编辑 ]

nlrte13

把以前电路题的公式推导出来了 - -#
相当于这道题不考虑“过程中”的情况

若一个记忆体由 n 个神经元组成，
且有 x 种神经元，则最少需要 Y 条神经纤维，
Y = n*(n-1)*x*(x+1)/4

这样算 n=6, x=6 时
Y = 315

[ 本帖最后由 nlrte13 于 2010-10-9 15:23 编辑 ]

newkid

又是图论相关，奥数哥大显身手的时候到了：

Airports

In a country there is a total of 20 airports. Each one of these airports are linked to all the others, either through direct or indirect (ie. connecting) flights. There are at most two direct flights among any randomly chosen three airports.

What is the maximum possible number of direct flights among these 20 airports?

Note: If there is a flight between A and B, it can be used in both directions and it will be counted as one flight.

20个机场，它们之间之间或间接可达，任意三个机场之间只能有两个直飞航班。所有机场之间最多可以有多少个直飞航班？注意如果A到B有直飞航班，则为双向，而且只算作一个航班。

20个顶点的连通无向图，任意三个顶点之间只能有两条边，最多可以有多少条边？因为三角形不允许存在，必须画出尽可能多的四边形。