b***e
发帖数: 1419 | 1 有一群学生组织了一些俱乐部。每个俱乐部至少有两个成员。每两个俱乐部至少有一个
公共成员。现在给每个学生发一个帽子。帽子只有三种颜色：白色，黑色或红色。证明
存在一种分发的方式似的每一个俱乐部至少有两个成员拿到不同颜色的帽子。 |
t*******r
发帖数: 22634 | 2 哪个超级小学 GT 有 proof on any natural number on any number of sets with
any number of intersections？。。。
版上 140+ 还有 220+ 的 GT 班娃家长献身说法一下？
【在 b***e 的大作中提到】
: 有一群学生组织了一些俱乐部。每个俱乐部至少有两个成员。每两个俱乐部至少有一个
: 公共成员。现在给每个学生发一个帽子。帽子只有三种颜色：白色，黑色或红色。证明
: 存在一种分发的方式似的每一个俱乐部至少有两个成员拿到不同颜色的帽子。
|
t*******r
发帖数: 22634 | 3 I think a graph-based BFS constructive traversal & coloring algorithm can
proof this. The theoretical base is binary logic on graph construction's "
wave front".
【在 b***e 的大作中提到】
: 有一群学生组织了一些俱乐部。每个俱乐部至少有两个成员。每两个俱乐部至少有一个
: 公共成员。现在给每个学生发一个帽子。帽子只有三种颜色：白色，黑色或红色。证明
: 存在一种分发的方式似的每一个俱乐部至少有两个成员拿到不同颜色的帽子。
|
d******e
发帖数: 2265 | 4 这个不是马工面试题目嘛
【在 b***e 的大作中提到】
: 有一群学生组织了一些俱乐部。每个俱乐部至少有两个成员。每两个俱乐部至少有一个
: 公共成员。现在给每个学生发一个帽子。帽子只有三种颜色：白色，黑色或红色。证明
: 存在一种分发的方式似的每一个俱乐部至少有两个成员拿到不同颜色的帽子。
|
l*****e
发帖数: 2447 | 5 缺限制条件？
【在 b***e 的大作中提到】
: 有一群学生组织了一些俱乐部。每个俱乐部至少有两个成员。每两个俱乐部至少有一个
: 公共成员。现在给每个学生发一个帽子。帽子只有三种颜色：白色，黑色或红色。证明
: 存在一种分发的方式似的每一个俱乐部至少有两个成员拿到不同颜色的帽子。
|
b***e
发帖数: 1419 | 6 愿闻其详。
【在 l*****e 的大作中提到】
: 缺限制条件？
|
b***e
发帖数: 1419 | 7 You can you up, LOL.
【在 d******e 的大作中提到】
: 这个不是马工面试题目嘛
|
l*****e
发帖数: 2447 | 8 哦，没有，原来想的对的，后来自己绕了一下，老了。
【在 b***e 的大作中提到】
: 愿闻其详。
|
b***e
发帖数: 1419 | 9 三个半个小时的竞赛，四道题。其它三道都是渣。这题太牛逼了。你这路子说的是正的
，但是要真构造起来还不是那么简单。反正要考我我当场是做不出来的。
【在 t*******r 的大作中提到】
: I think a graph-based BFS constructive traversal & coloring algorithm can
: proof this. The theoretical base is binary logic on graph construction's "
: wave front".
|
t*******r
发帖数: 22634 | 10 我晚上写个详细的。俺现在有事忙。
【在 b***e 的大作中提到】
: 三个半个小时的竞赛，四道题。其它三道都是渣。这题太牛逼了。你这路子说的是正的
: ，但是要真构造起来还不是那么简单。反正要考我我当场是做不出来的。
|
|
|
b***e
发帖数: 1419 | 11 Sure. 愿闻其详。
【在 t*******r 的大作中提到】
: 我晚上写个详细的。俺现在有事忙。
|
f**e
发帖数: 890 | 12 没看懂，帽子数量没限制，这个不是随便发吗？公共人员统一一个颜色，其他人随意用
其他剩下颜色不久可以了？有什么东西我漏了？看来有必要重回小学了。
【在 b***e 的大作中提到】
: 有一群学生组织了一些俱乐部。每个俱乐部至少有两个成员。每两个俱乐部至少有一个
: 公共成员。现在给每个学生发一个帽子。帽子只有三种颜色：白色，黑色或红色。证明
: 存在一种分发的方式似的每一个俱乐部至少有两个成员拿到不同颜色的帽子。
|
z***e
发帖数: 1757 | 13 如果没有“其他人”呢？
【在 f**e 的大作中提到】
: 没看懂，帽子数量没限制，这个不是随便发吗？公共人员统一一个颜色，其他人随意用
: 其他剩下颜色不久可以了？有什么东西我漏了？看来有必要重回小学了。
|
f**e
发帖数: 890 | 14 公共人员多余一个的话，两个人用不一样颜色的。还漏了什么？
【在 z***e 的大作中提到】
: 如果没有“其他人”呢？
|
z***e
发帖数: 1757 | 15 什么叫“公共人员多余一个"?
【在 f**e 的大作中提到】
: 公共人员多余一个的话，两个人用不一样颜色的。还漏了什么？
|
t*******r
发帖数: 22634 | 16 我就快速写一个概念，用自然语言小学娃能看懂的。具体严格证明
要花点时间。
概念上很简单，也就是最关键的核心问题，是只有两个娃的俱乐部，
并且那两个娃还隶属其他只有两个娃俱乐部。
这个问题很简单，图景上其实就是共享顶点（拓扑）三角形问题：
顶点对应娃，某条边对应俱乐部。
（1）找第一个顶点着色 0，然后连接的第二个顶点着色 1。
（2）然后把第一个和第二个顶点都有连接的顶点着色 2。
（3）然后从所有颜色 2 的顶点开始，把所有跟颜色 0 和颜色 2
有连接的顶点，都着成颜色 1。
（4）重复以上（3）过程，把所有颜色 0 有连接的都搞完。
（5）然后从“波前”开始，找一个颜色 1，继续搞。
（6）因为三角形限制最大，所以多边形（两个娃以上）就不是问题。
非共享顶点也不是问题。
两分钟就概念证明完毕了。。。当然要整理一下思路写成严格证明
。。。俺娃喊俺吃饭。。。严格证明以后再说。。。
【在 b***e 的大作中提到】
: Sure. 愿闻其详。
|
f**e
发帖数: 890 | 17 错字，“公共人员多于一个人”。大概是这样考虑到你说的漏掉的情况：
1.公共人员的第一个人选一个颜色的帽子。
2.公共人员的第二个人选第二个颜色的帽子。
3.。。。
4.如果没有公共人员的话，把那个帽子给同组的其他人，没有的话给另一个组的人，重
复。
【在 z***e 的大作中提到】
: 什么叫“公共人员多余一个"?
|
f**e
发帖数: 890 | 18 你这个是overkill 了，只有三个颜色，要求只要有两个颜色就可以。不需要遍历每个
人，遍历每个俱乐部两次足以。如果每个俱乐部一亿人，你这就多做很多无用功了。
【在 t*******r 的大作中提到】
: 我就快速写一个概念，用自然语言小学娃能看懂的。具体严格证明
: 要花点时间。
: 概念上很简单，也就是最关键的核心问题，是只有两个娃的俱乐部，
: 并且那两个娃还隶属其他只有两个娃俱乐部。
: 这个问题很简单，图景上其实就是共享顶点（拓扑）三角形问题：
: 顶点对应娃，某条边对应俱乐部。
: （1）找第一个顶点着色 0，然后连接的第二个顶点着色 1。
: （2）然后把第一个和第二个顶点都有连接的顶点着色 2。
: （3）然后从所有颜色 2 的顶点开始，把所有跟颜色 0 和颜色 2
: 有连接的顶点，都着成颜色 1。
|
b***e
发帖数: 1419 | 19 你这个构造的问题在于以前染过的点有可能被重染，破坏以前的已经做好的set。我的
直观想法和你这个类似，但是严格证明的时候漏洞无法弥补。 我最终的方法是要保证
染过的点就定下来了，在以后的算法过程中不会被重染。
【在 t*******r 的大作中提到】
: 我就快速写一个概念，用自然语言小学娃能看懂的。具体严格证明
: 要花点时间。
: 概念上很简单，也就是最关键的核心问题，是只有两个娃的俱乐部，
: 并且那两个娃还隶属其他只有两个娃俱乐部。
: 这个问题很简单，图景上其实就是共享顶点（拓扑）三角形问题：
: 顶点对应娃，某条边对应俱乐部。
: （1）找第一个顶点着色 0，然后连接的第二个顶点着色 1。
: （2）然后把第一个和第二个顶点都有连接的顶点着色 2。
: （3）然后从所有颜色 2 的顶点开始，把所有跟颜色 0 和颜色 2
: 有连接的顶点，都着成颜色 1。
|
t*******r
发帖数: 22634 | 20 我刚才真的去证明了一下。。。我觉得这道题是不是错了。。。
比如这个反例：
如果我们用这个拓扑图形来表示：
（1）把 “顶点” 认为是娃
（2）“边” 认为是俱乐部
那对于正方形加两对角线，这个三种颜色漆不出来吧。我待会儿
上个图。 |
|
|
t*******r
发帖数: 22634 | 21 见附图，三色不能保证任意一边上的顶点不出现同色。
【在 t*******r 的大作中提到】
: 我刚才真的去证明了一下。。。我觉得这道题是不是错了。。。
: 比如这个反例：
: 如果我们用这个拓扑图形来表示：
: （1）把 “顶点” 认为是娃
: （2）“边” 认为是俱乐部
: 那对于正方形加两对角线，这个三种颜色漆不出来吧。我待会儿
: 上个图。
|
z***e
发帖数: 1757 | 22 注意："每两个俱乐部至少有一个公共成员"
【在 t*******r 的大作中提到】
: 我刚才真的去证明了一下。。。我觉得这道题是不是错了。。。
: 比如这个反例：
: 如果我们用这个拓扑图形来表示：
: （1）把 “顶点” 认为是娃
: （2）“边” 认为是俱乐部
: 那对于正方形加两对角线，这个三种颜色漆不出来吧。我待会儿
: 上个图。
|
t*******r
发帖数: 22634 | 23 这个不会导致重染，而是证明过程把你的这道题目直接给证伪了。看我
上面给的反例。
实际上你给再多的颜色都没用，因为如果你给 n 种颜色，我可以用 N+1
个点，构造一个全部由 2-point edge 构成的 complete graph，这个
graph 只能用 N+1 中颜色着色（因为是 complete graph）。
【在 b***e 的大作中提到】
: 你这个构造的问题在于以前染过的点有可能被重染，破坏以前的已经做好的set。我的
: 直观想法和你这个类似，但是严格证明的时候漏洞无法弥补。 我最终的方法是要保证
: 染过的点就定下来了，在以后的算法过程中不会被重染。
|
t*******r
发帖数: 22634 | 24 哦，忘了这个。那应该就证明了。。。
【在 z***e 的大作中提到】
: 注意："每两个俱乐部至少有一个公共成员"
|
b***e
发帖数: 1419 | 25 那你严格的证明吧，虽然我不看好你这个路子。
【在 t*******r 的大作中提到】
: 哦，忘了这个。那应该就证明了。。。
|
t*******r
发帖数: 22634 | 26 哈哈俺太粗心看错题了。。。有了这个限制条件，那证明也太简单了。。。这么反过来
映射到图论:
把俱乐部映射成 vertex，把娃映射成 edge（edge 的 degree 允许 > 2）。。。因为
有这个限制条件，所以这是个 complete graph。。。直接两步将死。。。
【在 z***e 的大作中提到】
: 注意："每两个俱乐部至少有一个公共成员"
|
t*******r
发帖数: 22634 | 27 我上面证明啦。。。因为你这个是 complete graph，我图论建模时逆向思维一下。。
。这么简单的特例 graph，俺真希望上班时蹦一个特例出来。。。
【在 b***e 的大作中提到】
: 那你严格的证明吧，虽然我不看好你这个路子。
|
b***e
发帖数: 1419 | 28 恕我愚钝，没懂。在图论里，边是没有degree的，只有两个顶点。你顶多是建一个二分
图，一边是人，一边是俱乐部，然后用边来表示从属关系。然后呢？
【在 t*******r 的大作中提到】
: 哈哈俺太粗心看错题了。。。有了这个限制条件，那证明也太简单了。。。这么反过来
: 映射到图论:
: 把俱乐部映射成 vertex，把娃映射成 edge（edge 的 degree 允许 > 2）。。。因为
: 有这个限制条件，所以这是个 complete graph。。。直接两步将死。。。
|
t*******r
发帖数: 22634 | 29 图论里的 edge 是可以有 degree，因为那个是 topological 的，
可以不是一条线段。
图论是建立在集合论之上的，所谓 edge，其实是一个 set，该 set
告诉这个 edge 连接到那些 vertex，可以包括两个以上的 vertex。
我吃完饭了，我马上写一个严格证明，你稍稍等一下。
【在 b***e 的大作中提到】
: 恕我愚钝，没懂。在图论里，边是没有degree的，只有两个顶点。你顶多是建一个二分
: 图，一边是人，一边是俱乐部，然后用边来表示从属关系。然后呢？
|
b***e
发帖数: 1419 | 30 不捉急，我看你也是个严肃的讨论者。我也是想看看有没有直观的解法。我没有见过边
带drgree的图论。不过我很业余，没有受过正规的数学训练。你这个拓扑意义上的图论
里的完全图概念我不是很理解。
【在 t*******r 的大作中提到】
: 图论里的 edge 是可以有 degree，因为那个是 topological 的，
: 可以不是一条线段。
: 图论是建立在集合论之上的，所谓 edge，其实是一个 set，该 set
: 告诉这个 edge 连接到那些 vertex，可以包括两个以上的 vertex。
: 我吃完饭了，我马上写一个严格证明，你稍稍等一下。
|
|
|
t*******r
发帖数: 22634 | 31 因为这个是 word problem，我现在先写严格证明的第一步，
数学建模：把题目建模成图论表述。
A: 映射：
（1）把 “俱乐部” 映射 成图论里的 vertex。
（2）把 “娃” 映射 成图论里的 edge。
（3）把 “戴帽子” 映射 成图论里对 edge 的 着色。
B: 题目条件：
（1）任何 vertex 的 degree >= 2
（2）任何 edge 的 degree >= 1
（3）任何两个 vertex 之间，至少存在一条 edge（complete graph）
（4）存在三种颜色，{ 0, 1, 2 }，任何 edge 最终上某一种颜色。
C: 题目要求：
求一种着色算法，使得任何 vertex 所连接的 edge，至少出现两种
不同的颜色。
-------------------------
我下个帖子写解法
【在 b***e 的大作中提到】
: 恕我愚钝，没懂。在图论里，边是没有degree的，只有两个顶点。你顶多是建一个二分
: 图，一边是人，一边是俱乐部，然后用边来表示从属关系。然后呢？
|
b***e
发帖数: 1419 | 32 模型很清晰，虽然我对那个边上有degree的图论表示怀疑。
【在 t*******r 的大作中提到】
: 因为这个是 word problem，我现在先写严格证明的第一步，
: 数学建模：把题目建模成图论表述。
: A: 映射：
: （1）把 “俱乐部” 映射 成图论里的 vertex。
: （2）把 “娃” 映射 成图论里的 edge。
: （3）把 “戴帽子” 映射 成图论里对 edge 的 着色。
: B: 题目条件：
: （1）任何 vertex 的 degree >= 2
: （2）任何 edge 的 degree >= 1
: （3）任何两个 vertex 之间，至少存在一条 edge（complete graph）
|
t*******r
发帖数: 22634 | 33 现在我写解法，因为我已经把题目映射成图论符号（自然语言表述），
所以现在开始我只用图论符号（自然语言表示）。
（1）寻找任何一条 degree >= 2 的 edge，记为 e1。
（2）如果找不到 e1，该问题里所有的 edge 的 degree 都是 1。
这样是个 trivial 的问题。
（3）如果找到 e1，先把 e1 着色为颜色 0。
（4）从 e1 所连接 vertex 里面，选出两个，记录为 v1 和 v2。
（5）从 v1 找连接 v1 的所有 edge e，如果 e 还没有被着色，
那就把 e 着色为颜色 1。
（6）从 v2 找连接 v2 的所有 edge e，如果 e 还没有着色，
那就把 e 着色为颜色 2。
（7）最后对 degree 为 1 的所有 edge 着色，着色成其连接
的 v 所连接的 e 的不同颜色（如果 v 已经连接两种颜色的
e 了，那么随便着一种色）。
我待会儿再写证明。现在有事。
因为这个是 word problem，我现在先写严格证明的第一步，
数学建模：把题目建模成图论表述。
A: 映射：
（1）把 “俱乐部” 映射 成图论里的 vertex。
（2）把 “娃” 映射 成图论里的 edge。
（3）把 “戴帽子” 映射 成图论里对 edge 的 着色。
B: 题目条件：
（1）任何 vertex 的 degree >= 2
（2）任何 edge 的 degree >= 1
（3）任何两个 vertex 之间，至少存在一条 edge（complete graph）
（4）存在三种颜色，{ 0, 1, 2 }，任何 edge 最终上某一种颜色。
C: 题目要求：
求一种着色算法，使得任何 vertex 所连接的 edge，至少出现两种
不同的颜色。
【在 t*******r 的大作中提到】
: 因为这个是 word problem，我现在先写严格证明的第一步，
: 数学建模：把题目建模成图论表述。
: A: 映射：
: （1）把 “俱乐部” 映射 成图论里的 vertex。
: （2）把 “娃” 映射 成图论里的 edge。
: （3）把 “戴帽子” 映射 成图论里对 edge 的 着色。
: B: 题目条件：
: （1）任何 vertex 的 degree >= 2
: （2）任何 edge 的 degree >= 1
: （3）任何两个 vertex 之间，至少存在一条 edge（complete graph）
|
f**e
发帖数: 890 | 34 先赞一下，再问问题。
1.原题的这句话“每两个俱乐部至少有一个公共成员”这句话我开始下意识理解为排他
，后来看到提醒，才意识到自己理解错了。这个有没有英文原题？
2.vertex 的degree代表可以连到多个vertex?
3.edge 的degree代表学生个数？
4. 我理解的图形是这样的
5.AB, AD 之间可能是同一个人，都是S1,他们必须是同一个颜色，你怎么避免给他们着
不同的色？
6.如果两V之间只有一个EDGE（代表多个学生）,那这个EDGE 就不能只是一个颜色，对
吧？
【在 t*******r 的大作中提到】
: 现在我写解法，因为我已经把题目映射成图论符号（自然语言表述），
: 所以现在开始我只用图论符号（自然语言表示）。
: （1）寻找任何一条 degree >= 2 的 edge，记为 e1。
: （2）如果找不到 e1，该问题里所有的 edge 的 degree 都是 1。
: 这样是个 trivial 的问题。
: （3）如果找到 e1，先把 e1 着色为颜色 0。
: （4）从 e1 所连接 vertex 里面，选出两个，记录为 v1 和 v2。
: （5）从 v1 找连接 v1 的所有 edge e，如果 e 还没有被着色，
: 那就把 e 着色为颜色 1。
: （6）从 v2 找连接 v2 的所有 edge e，如果 e 还没有着色，
|
t*******r
发帖数: 22634 | 35 现在我写证明：
v1 和 v2：一条 edge e1 着色为颜色 0，各自至少一条 edge
着成非颜色 0。
对于其他的 vertex v：
（1）因为 v 和 v1 之间存在一条以及一条以上 edge。
所以 v 至少存在一条 edge 颜色是 0 或 1。
（2）因为 v 和 v1 之间存在一条以及一条以上 edge。
所以 v 至少存在一条 edge 颜色是 0 或 2。
因为 v 有两条 edge。。。我还有事，待会儿写。。。
【在 t*******r 的大作中提到】
: 现在我写解法，因为我已经把题目映射成图论符号（自然语言表述），
: 所以现在开始我只用图论符号（自然语言表示）。
: （1）寻找任何一条 degree >= 2 的 edge，记为 e1。
: （2）如果找不到 e1，该问题里所有的 edge 的 degree 都是 1。
: 这样是个 trivial 的问题。
: （3）如果找到 e1，先把 e1 着色为颜色 0。
: （4）从 e1 所连接 vertex 里面，选出两个，记录为 v1 和 v2。
: （5）从 v1 找连接 v1 的所有 edge e，如果 e 还没有被着色，
: 那就把 e 着色为颜色 1。
: （6）从 v2 找连接 v2 的所有 edge e，如果 e 还没有着色，
|
t*******r
发帖数: 22634 | 36 vetex 的 degree 代表一个俱乐部里有多少个娃。
edge 的 degree 代表一个娃同时隶属于多少个俱乐部。
不要画成线型图，上集合论。
【在 f**e 的大作中提到】
: 先赞一下，再问问题。
: 1.原题的这句话“每两个俱乐部至少有一个公共成员”这句话我开始下意识理解为排他
: ，后来看到提醒，才意识到自己理解错了。这个有没有英文原题？
: 2.vertex 的degree代表可以连到多个vertex?
: 3.edge 的degree代表学生个数？
: 4. 我理解的图形是这样的
: 5.AB, AD 之间可能是同一个人，都是S1,他们必须是同一个颜色，你怎么避免给他们着
: 不同的色？
: 6.如果两V之间只有一个EDGE（代表多个学生）,那这个EDGE 就不能只是一个颜色，对
: 吧？
|
t*******r
发帖数: 22634 | 37 上集合论的意思是。。。图论的图形只是看看，证明需要集合逻辑，
比如 any 算子，exist 算子。。。当然不要那么学究，写成
自然语言表述。。。等我忙完回来写完那个证明。。。
另外 edge degree > 1 就别画成简单线型，你可以画成 star
model 或者 spanning tree 啥的。。。
【在 t*******r 的大作中提到】
: vetex 的 degree 代表一个俱乐部里有多少个娃。
: edge 的 degree 代表一个娃同时隶属于多少个俱乐部。
: 不要画成线型图，上集合论。
|
t*******r
发帖数: 22634 | 38 不好意思，俺刚才被喝令去洗脚的时候突然发现，漏了一种 corner case。
proof 的时候发现了。
当然俺就不写 if 这种恶心的玩意儿，我把逻辑加上一个限制条件。我去
改一下，马上贴上来。 |
t*******r
发帖数: 22634 | 39 不好意思，俺洗脚时有点头昏，洗脚堂氧气比较少。。。俺前面的解法是对的。。。
俺继续证明下去就是了。
【在 t*******r 的大作中提到】
: 不好意思，俺刚才被喝令去洗脚的时候突然发现，漏了一种 corner case。
: proof 的时候发现了。
: 当然俺就不写 if 这种恶心的玩意儿，我把逻辑加上一个限制条件。我去
: 改一下，马上贴上来。
|
f**e
发帖数: 890 | 40 还是上图，也是我最开始画的。 :)集合论还是高中水平，大学之后就是简单的ODE,PDE
。第七步简化，只考虑每个人都属于最少两个俱乐部，这不影响解题方法。
（7）最后对 degree 为 1 的所有 edge 着色，着色成其连接
的 v 所连接的 e 的不同颜色（如果 v 已经连接两种颜色的
e 了，那么随便着一种色）。
V1:{0,1}
V2:{0,2}
V不可以只有{0}?这种上色方法好像不可以保证每个俱乐部都最少两个颜色？
【在 t*******r 的大作中提到】
: 上集合论的意思是。。。图论的图形只是看看，证明需要集合逻辑，
: 比如 any 算子，exist 算子。。。当然不要那么学究，写成
: 自然语言表述。。。等我忙完回来写完那个证明。。。
: 另外 edge degree > 1 就别画成简单线型，你可以画成 star
: model 或者 spanning tree 啥的。。。
|
|
|
t*******r
发帖数: 22634 | 41 仔细检查了一下，的确有一个很小的漏洞，我改一改。
【在 t*******r 的大作中提到】
: 不好意思，俺洗脚时有点头昏，洗脚堂氧气比较少。。。俺前面的解法是对的。。。
: 俺继续证明下去就是了。
|
t*******r
发帖数: 22634 | 42 这里 edge 的 degree 为 1，是指该娃只属于一个俱乐部。。。连接两个 vertex
的 edge 的 degree 为 2。
PDE
【在 f**e 的大作中提到】
: 还是上图，也是我最开始画的。 :)集合论还是高中水平，大学之后就是简单的ODE,PDE
: 。第七步简化，只考虑每个人都属于最少两个俱乐部，这不影响解题方法。
: （7）最后对 degree 为 1 的所有 edge 着色，着色成其连接
: 的 v 所连接的 e 的不同颜色（如果 v 已经连接两种颜色的
: e 了，那么随便着一种色）。
: V1:{0,1}
: V2:{0,2}
: V不可以只有{0}?这种上色方法好像不可以保证每个俱乐部都最少两个颜色？
|
t*******r
发帖数: 22634 | 43 好像还是没有漏洞。。。吼吼吼，今天喝高了？。。。我继续证明吧。。。
【在 t*******r 的大作中提到】
: 仔细检查了一下，的确有一个很小的漏洞，我改一改。
|
t*******r
发帖数: 22634 | 44 现在我写证明：
对于 v1 和 v2：一条 edge e1 着色为颜色 0，各自至少一条 edge
着成非颜色 0。（这个证明我写得比较简略，反正看了下面
的复杂情况，自然能理解这个。。。码字费力）。
对于任何不是 v1 或 v2 的 vertex v，因为是 complete graph，
所以 v 和 v1，以及 v 和 v2，都存在至少一条连接（edge），所以
有以下几种情况：
（1）如果出现 v 有两条（或更多）的 edge，该 edge 同时
连到 v1 和 v2，那么其中一条一定是 e1，颜色为 0。另一条
是颜色 1。不同色。
（2）如果出现 v 有且仅一条 edge 同时连到 v1 和 v2，
那这条 edge 一定是 e1，颜色为 0。那 v 至少还有一条
edge，那条 edge 要么连到 v1，要么连到 v2，要么啥都
不连，总之颜色不会被着色成 0。不同色。
（3）如果不出现任何从 v 同时连接到 v1 和 v2 的 edge，
那么因为 complete graph，至少有一条 edge 只连接到
v1，颜色为 1。至少一条 edge 只连接到 v2，颜色为 2。
不同色。
以上 1 - 3 包括了所有的情况，所以证毕。
【在 t*******r 的大作中提到】
: 现在我写解法，因为我已经把题目映射成图论符号（自然语言表述），
: 所以现在开始我只用图论符号（自然语言表示）。
: （1）寻找任何一条 degree >= 2 的 edge，记为 e1。
: （2）如果找不到 e1，该问题里所有的 edge 的 degree 都是 1。
: 这样是个 trivial 的问题。
: （3）如果找到 e1，先把 e1 着色为颜色 0。
: （4）从 e1 所连接 vertex 里面，选出两个，记录为 v1 和 v2。
: （5）从 v1 找连接 v1 的所有 edge e，如果 e 还没有被着色，
: 那就把 e 着色为颜色 1。
: （6）从 v2 找连接 v2 的所有 edge e，如果 e 还没有着色，
|
t*******r
发帖数: 22634 | 45 这里的确有个小漏洞，有可能出现两条都连接 v1 和 v2，但是同色的
情况。。。我待会儿打个补丁给补了这种 corner case 就行。。。
也就是把这种同时连接 v1 和 v2 的 edge 给拖后解决。。。
看来不能洗完脚马上做题。。。半夜比较好。。。
【在 t*******r 的大作中提到】
: 现在我写证明：
: 对于 v1 和 v2：一条 edge e1 着色为颜色 0，各自至少一条 edge
: 着成非颜色 0。（这个证明我写得比较简略，反正看了下面
: 的复杂情况，自然能理解这个。。。码字费力）。
: 对于任何不是 v1 或 v2 的 vertex v，因为是 complete graph，
: 所以 v 和 v1，以及 v 和 v2，都存在至少一条连接（edge），所以
: 有以下几种情况：
: （1）如果出现 v 有两条（或更多）的 edge，该 edge 同时
: 连到 v1 和 v2，那么其中一条一定是 e1，颜色为 0。另一条
: 是颜色 1。不同色。
|
f**e
发帖数: 890 | 46 辛苦：这个有疑问：
“（2）如果出现 v 有且仅一条 edge 同时连到 v1 和 v2，
那这条 edge 一定是 e1，颜色为 0。
--理解
那 v 至少还有一条
edge，那条 edge 要么连到 v1，要么连到 v2，要么啥都
不连，总之颜色不会被着色成 0。不同色。”
--为啥v不可以连到其他的v？一个人（比如这个人颜色是0）同时属于所有的俱乐部就
满足了COMPLETE GRAPH 这个条件，v的第二个颜色你没保证不可以是0。你好像只着了
和保证了V1，V2的颜色，其他的v你怎么着的色，我漏掉什么了？
【在 t*******r 的大作中提到】
: 现在我写证明：
: 对于 v1 和 v2：一条 edge e1 着色为颜色 0，各自至少一条 edge
: 着成非颜色 0。（这个证明我写得比较简略，反正看了下面
: 的复杂情况，自然能理解这个。。。码字费力）。
: 对于任何不是 v1 或 v2 的 vertex v，因为是 complete graph，
: 所以 v 和 v1，以及 v 和 v2，都存在至少一条连接（edge），所以
: 有以下几种情况：
: （1）如果出现 v 有两条（或更多）的 edge，该 edge 同时
: 连到 v1 和 v2，那么其中一条一定是 e1，颜色为 0。另一条
: 是颜色 1。不同色。
|
t*******r
发帖数: 22634 | 47 我发现我错在哪里了，因为这个是 complete graph，我漏了很多 edge
没有着色。我待会儿改改。
【在 t*******r 的大作中提到】
: 这里的确有个小漏洞，有可能出现两条都连接 v1 和 v2，但是同色的
: 情况。。。我待会儿打个补丁给补了这种 corner case 就行。。。
: 也就是把这种同时连接 v1 和 v2 的 edge 给拖后解决。。。
: 看来不能洗完脚马上做题。。。半夜比较好。。。
|
t*******r
发帖数: 22634 | 48 如果所有的 edge 都是 degree 2 的 edge，而这又是一个 complete graph，
那这个 着色问题是个 trivial 问题。。。你只要把这个 complete graph
的 vertexes 给随便给 partition 成两个 partition，然后把
partition 1 内部的 edge 着色成 颜色 0，partition 2 内部的
edge 着色成 颜色 1 连接 partition 1 和 partition 2 的
edge 着色成 颜色 3。。。
当然题目不会这么 trivial。。。问题显然是在于 edge 的 degree > 2
的情况。
【在 b***e 的大作中提到】
: 模型很清晰，虽然我对那个边上有degree的图论表示怀疑。
|
b***e
发帖数: 1419 | 49 所以我认为你把这个问题归结为一个你所谓的“拓扑图论”问题的做法是不行的。图论
里图的定义就是每条边连接两个顶点。对于这个题目一个正常的图论模型来应该是一个
二分图。一侧是人，另一侧是俱乐部。中间的连线表是从属关系。
不过话说回来，我的本意是这个小学生数学竞赛为啥出这种题？是不是出错了。这一个
题没有三个小时我反正做不出来。
【在 t*******r 的大作中提到】
: 如果所有的 edge 都是 degree 2 的 edge，而这又是一个 complete graph，
: 那这个 着色问题是个 trivial 问题。。。你只要把这个 complete graph
: 的 vertexes 给随便给 partition 成两个 partition，然后把
: partition 1 内部的 edge 着色成 颜色 0，partition 2 内部的
: edge 着色成 颜色 1 连接 partition 1 和 partition 2 的
: edge 着色成 颜色 3。。。
: 当然题目不会这么 trivial。。。问题显然是在于 edge 的 degree > 2
: 的情况。
|
m**k
发帖数: 18660 | 50 潮水哥威武
【在 b***e 的大作中提到】
: 所以我认为你把这个问题归结为一个你所谓的“拓扑图论”问题的做法是不行的。图论
: 里图的定义就是每条边连接两个顶点。对于这个题目一个正常的图论模型来应该是一个
: 二分图。一侧是人，另一侧是俱乐部。中间的连线表是从属关系。
: 不过话说回来，我的本意是这个小学生数学竞赛为啥出这种题？是不是出错了。这一个
: 题没有三个小时我反正做不出来。
|
|
|
d****g
发帖数: 7460 | 51 设N组符合条件。建立N+1.有没帽子成员简单。若都是绿帽。把绿1变红，如果G1抗议，
说明G1除绿1全红。说明绿2不在G1。那把绿2变紫必须可以。如不可，说明有G2除绿2全
紫。那
么G2和
G1怎么香蕉的呢。 |
t*******r
发帖数: 22634 | 52 你这么画难道不是一回事？你这个有两种 vertex、并且 edge 的 degree 是 2
的图，跟只有一种 vertex、但允许 edge degree 是任何自然数的图，难道
不是等价图？。。。话说你把 edge 和 vertex 换过来也行，只是 complete
graph 容易不容易看的问题。
当然我前面的漏洞补掉也不难，我重新写一个。不过不写严格的，我写个简单的。
【在 b***e 的大作中提到】
: 所以我认为你把这个问题归结为一个你所谓的“拓扑图论”问题的做法是不行的。图论
: 里图的定义就是每条边连接两个顶点。对于这个题目一个正常的图论模型来应该是一个
: 二分图。一侧是人，另一侧是俱乐部。中间的连线表是从属关系。
: 不过话说回来，我的本意是这个小学生数学竞赛为啥出这种题？是不是出错了。这一个
: 题没有三个小时我反正做不出来。
|
t*******r
发帖数: 22634 | 53 写个修掉漏洞的算法，稍微改一下，从 vertex 开始。。。另外我就
写个简略通俗的，不写严格啰嗦的了。
这个解这个：
（1）首先找任意一个 vertex v1，满足条件 v1 至少有两个或两个
以上 degree > 1 的 edge。
以下是概念写法，别扣字眼就是了：
（2.1）简单情况：如果不出现跟 v1 有且仅有两个 edge 的 vertex。
那这个简单，把跟 v1 连接的某一条 edge 着色为 颜色 0，其他跟
v1 有连接的 edge 着色为 颜色 1，剩下还没着色的 edge 统统
着色为 颜色 2。
这个证明也简单，任何一个 vertex 总跟 v1 有连接吧（complete graph）。
然后因为不出现跟 v1 有且仅有两个 edge 的 vertex，所以肯定还有一个
edge 颜色为 2（vertex 的 degree 至少是 2），不同色。。。v1 上也有
两种颜色。。。成了。
（2.2）复杂情况：出现跟 v1 有且仅有两个 edge 的 vertex。
。。。等一下。。。
【在 t*******r 的大作中提到】
: 你这么画难道不是一回事？你这个有两种 vertex、并且 edge 的 degree 是 2
: 的图，跟只有一种 vertex、但允许 edge degree 是任何自然数的图，难道
: 不是等价图？。。。话说你把 edge 和 vertex 换过来也行，只是 complete
: graph 容易不容易看的问题。
: 当然我前面的漏洞补掉也不难，我重新写一个。不过不写严格的，我写个简单的。
|
t*******r
发帖数: 22634 | 54 现在写（2.2）复杂情况：出现跟 v1 有且仅有两个 edge 的 vertex。
（2.2.1）如果该 vertex 还有其他的 edge，无所谓。那个其他 edge
将来会被着色为 颜色 2。
（2.2.2）如果该 vertex 没有其他的 edge 了：
因为这是一个 complete graph，所以这种 vertex 的两个 edge 会
包括图里的所有的 vertex，当然可能这两个 edge 另一端所对应
的 vertex 的集合可能还有交集。。。这个需要在（2.1）的着色
颜色 2 以前处理。。。这么整：
先找一个这样的 vertex，把一个 edge 着色为 颜色 0，另一个
edge 着色为 颜色 1。
对于前面两个 edge 另一端里的 vertex，分情况讨论：
（2.2.2.1）在交集里的 vertex，已经有两种颜色了。
（2.2.2.2）如果再出现两个这样的特殊只有两个 edge 的 vertex，
而这两个 vertex 又共享一个 edge，而其他两个 edge 已经被上述
（2.2.2）着色了，那么把那个共享 edge 着色成另一种不同的颜色
。。。因为这种 vertex 总共只有两个 edge，如果临时 on-demand
把这个 vertex 和 edge 翻过来看，就是一个个三角形着色问题。
（当然是 hyper-graph 里的三角形）。所以总是可以用三种颜色
着色成功。。。会出现颜色 2。。。而且这些 vertex 也没有其他
edge 了，所以跟其他 vertex 着色也无关。
先 （2.2.2.2）里面一圈圈找干净。然后回到（2.2）再一圈圈
找干净。（记得循环嵌套）。
俺不想把（2.2.2.2）写成严格证明了，其实概念很简单，但
写严格太麻烦了。。。其实就是 hyper-graph 里的操作。。。
俺的文字能力比较差，看得明白就看，看不明白就算，有错请
指正。。。表抱怨俺的破语文就是了。。。
（2.2.2.3）如果不出现 （2.2.2.2）的共享 edge 的情况，
也不在 （2.2.2.1）的交集里，那这个着色被推迟。。。最后
在着色 2 以前如果还没有被着色，那就着跟另一个 edge 的
不同颜色，但避免用颜色 2。
写个修掉漏洞的算法，稍微改一下，从 vertex 开始。。。另外我就
写个简略通俗的，不写严格啰嗦的了。
这个解这个：
（1）首先找任意一个 vertex v1，满足条件 v1 至少有两个或两个
以上 degree > 1 的 edge。
以下是概念写法，别扣字眼就是了：
（2.1）简单情况：如果不出现跟 v1 有且仅有两个 edge 的 vertex。
那这个简单，把跟 v1 连接的某一条 edge 着色为 颜色 0，其他跟
v1 有连接的 edge 着色为 颜色 1，剩下还没着色的 edge 统统
着色为 颜色 2。
这个证明也简单，任何一个 vertex 总跟 v1 有连接吧（complete graph）。
然后因为不出现跟 v1 有且仅有两个 edge 的 vertex，所以肯定还有一个
edge 颜色为 2（vertex 的 degree 至少是 2），不同色。。。v1 上也有
两种颜色。。。成了。
（2.2）复杂情况：出现跟 v1 有且仅有两个 edge 的 vertex。
。。。等一下。。。
【在 t*******r 的大作中提到】
: 写个修掉漏洞的算法，稍微改一下，从 vertex 开始。。。另外我就
: 写个简略通俗的，不写严格啰嗦的了。
: 这个解这个：
: （1）首先找任意一个 vertex v1，满足条件 v1 至少有两个或两个
: 以上 degree > 1 的 edge。
: 以下是概念写法，别扣字眼就是了：
: （2.1）简单情况：如果不出现跟 v1 有且仅有两个 edge 的 vertex。
: 那这个简单，把跟 v1 连接的某一条 edge 着色为 颜色 0，其他跟
: v1 有连接的 edge 着色为 颜色 1，剩下还没着色的 edge 统统
: 着色为 颜色 2。
|
t*******r
发帖数: 22634 | 55 写完发现，这么写还是有漏洞，漏洞在于，这个会导致在 solve 跟 v
有且仅有两个 edge，并且没有其他 edge 的 vertex 的过程中，会
出现颜色 2 的 edge，该颜色 2 的 edge 可能连接正常 vertex。
不过修掉这个漏洞也不难，概念其实不变，只是写法更加繁琐坑爹。
实际上应该做的是，先解决所有只含有两个 degree 为 2 的 edge
的 vertex，用上面 （2.2） 的办法。。。不过不是在一个平面 solve，
而是在 hyper-graph 里面 constructive 的算法去 solve，
相当于 solve 在 hyper-graph 里的 triangular prisms。。。这样先
solve 了 tightest constraints，然后再把其他的 constructive
地加上去。。。不过不证明一下也确实不能确定一定存在解。。。三个小时
确实搞不定。。。
小学生题目有这么难。。。除非有啥灵巧的办法吧。。。一般小学生最多
只会抽屉原理啥的。。。
【在 t*******r 的大作中提到】
: 现在写（2.2）复杂情况：出现跟 v1 有且仅有两个 edge 的 vertex。
: （2.2.1）如果该 vertex 还有其他的 edge，无所谓。那个其他 edge
: 将来会被着色为 颜色 2。
: （2.2.2）如果该 vertex 没有其他的 edge 了：
: 因为这是一个 complete graph，所以这种 vertex 的两个 edge 会
: 包括图里的所有的 vertex，当然可能这两个 edge 另一端所对应
: 的 vertex 的集合可能还有交集。。。这个需要在（2.1）的着色
: 颜色 2 以前处理。。。这么整：
: 先找一个这样的 vertex，把一个 edge 着色为 颜色 0，另一个
: edge 着色为 颜色 1。
|
t*******r
发帖数: 22634 | 56 当然小学生也可能会用反证法。。。不过这道题确实看不出应该
咋反证。。。 |
C*****d
发帖数: 2253 | 57 你的画法如果有人参加三个组怎么办？一个edge难道可以有大于2个vertex?
【在 t*******r 的大作中提到】
: 你这么画难道不是一回事？你这个有两种 vertex、并且 edge 的 degree 是 2
: 的图，跟只有一种 vertex、但允许 edge degree 是任何自然数的图，难道
: 不是等价图？。。。话说你把 edge 和 vertex 换过来也行，只是 complete
: graph 容易不容易看的问题。
: 当然我前面的漏洞补掉也不难，我重新写一个。不过不写严格的，我写个简单的。
|
t*******r
发帖数: 22634 | 58 你画不出来不一定就不存在。。。我定义一个 edge 当然可两个 vertex
难道也不行。。。edge 就是个 set。。。hyper-graph。。。
当然你想多画两种 vertex，多一些 edge，也不是不可以。。。
【在 C*****d 的大作中提到】
: 你的画法如果有人参加三个组怎么办？一个edge难道可以有大于2个vertex?
|
t*******r
发帖数: 22634 | 59 我前面想复杂了，其实（2.2.2）的情况很简单，不会出现 “hyper triangle
prism 的情况”。。。还是因为 complete graph 的限制。
因为如果出现第二个特殊 vertex 共享那条 edge，因为那个特殊 vertex
总共只有两条 edge，所以另一条 edge 连接的 vertex，一定是前一个特殊
vertex 的另一边的 vertex 的 super set（或相等），这么搞两个特殊
vertex，所有的 vertex 就被这两哥们撑成 degree >= 2 了。。。第三个
特殊 vertex 撑不出来了，出来就爆了哈哈哈。。。
这样其实就证明了（2.2.2）。。。不过这么看来应该还有更简洁的证明办法
。。。俺要是想出来就贴上来。。。
【在 t*******r 的大作中提到】
: 现在写（2.2）复杂情况：出现跟 v1 有且仅有两个 edge 的 vertex。
: （2.2.1）如果该 vertex 还有其他的 edge，无所谓。那个其他 edge
: 将来会被着色为 颜色 2。
: （2.2.2）如果该 vertex 没有其他的 edge 了：
: 因为这是一个 complete graph，所以这种 vertex 的两个 edge 会
: 包括图里的所有的 vertex，当然可能这两个 edge 另一端所对应
: 的 vertex 的集合可能还有交集。。。这个需要在（2.1）的着色
: 颜色 2 以前处理。。。这么整：
: 先找一个这样的 vertex，把一个 edge 着色为 颜色 0，另一个
: edge 着色为 颜色 1。
|
t*******r
发帖数: 22634 | 60 严谨一点应该是“前一个特殊 vertex 的另一边减去这边的连接的 vertex 集合的
super set”。。。当然灌水就是个意思。。。
【在 t*******r 的大作中提到】
: 我前面想复杂了，其实（2.2.2）的情况很简单，不会出现 “hyper triangle
: prism 的情况”。。。还是因为 complete graph 的限制。
: 因为如果出现第二个特殊 vertex 共享那条 edge，因为那个特殊 vertex
: 总共只有两条 edge，所以另一条 edge 连接的 vertex，一定是前一个特殊
: vertex 的另一边的 vertex 的 super set（或相等），这么搞两个特殊
: vertex，所有的 vertex 就被这两哥们撑成 degree >= 2 了。。。第三个
: 特殊 vertex 撑不出来了，出来就爆了哈哈哈。。。
: 这样其实就证明了（2.2.2）。。。不过这么看来应该还有更简洁的证明办法
: 。。。俺要是想出来就贴上来。。。
|
|
|
t*******r
发帖数: 22634 | 61 我觉得我还是把特殊情况想复杂了，并且还有遗漏。。。
其实特殊情况就是那些所有 edge 都连到 v1 上的 vertex，保证它们
的 edge 不着成一色。。。这里有个限制条件就是 complete graph。。。
--------------------------------------------
重写一下解法：
（1）首先找任意一个 vertex v1，满足条件 v1 至少有两个或两个
以上 degree > 1 的 edge。
（2）找到那些所有 edge 都连到 v1 上的 vertex：
（2.1）如果出现一个这样的特殊 vertex，那个把那个 vertex 的
第一个 edge 着色成 0， 其他 edge 着色成 1。
（2.2）如果出现两个以上的这样的特殊 vertex，那么如果出现 edge
有交集，那把交集的第一个 edge 着色成 0，其他的 edge 着色
成 1。如果 edge 没有交集，那两个 vertex 里，各自选一个着色
成 0，其余的着色成 1。
（2.3）第三个以上 vertex 话，要么有至少一个目前是独立的（未着色的）
edge，着色独立的 edge 成 0 或 1 的跟其他的不同色。。。如果所有 edge
都是跟其他的 share 的，那已经是不同色了，而且也已经着色了（因为
complete graph）。
（3）如果没有上面那样的特殊 vertex，那 v1 上选一个 edge 着色成 0，
剩下的连接到 v1 的 edge 都着色成 1。
（4）然后把剩下还没着色的 edge，都着色成 2。
-----------------------------------------------
证明部分：
A. 特殊 vertex 上面已经证明了。
B. 普通 vertex：
任何一个普通 vertex 总跟 v1 有连接吧（complete graph）。
然后因为不出现跟 v1 有且仅有两个 edge 的 vertex，所以肯定还有一个
edge 颜色为 2（vertex 的 degree 至少是 2），不同色。。。v1 上也有
两种颜色。。。应该差不多。
--------------------------------------------------
可能还有更简洁的解法。。。 |
t*******r
发帖数: 22634 | 62 那个（2.3），对于 complete hyper-graph 可能还是有漏洞。。。
需要证明。。。可能要找个更好的算法。。。娃吵着要玩。。。
【在 t*******r 的大作中提到】
: 我觉得我还是把特殊情况想复杂了，并且还有遗漏。。。
: 其实特殊情况就是那些所有 edge 都连到 v1 上的 vertex，保证它们
: 的 edge 不着成一色。。。这里有个限制条件就是 complete graph。。。
: --------------------------------------------
: 重写一下解法：
: （1）首先找任意一个 vertex v1，满足条件 v1 至少有两个或两个
: 以上 degree > 1 的 edge。
: （2）找到那些所有 edge 都连到 v1 上的 vertex：
: （2.1）如果出现一个这样的特殊 vertex，那个把那个 vertex 的
: 第一个 edge 着色成 0， 其他 edge 着色成 1。
|
p**s
发帖数: 2707 | 63 挺好的题，分两种情况处理，出给小学生也不算过分 |
p**s
发帖数: 2707 | |
b***e
发帖数: 1419 | 65 又有大牛驾到。 那我洗耳恭听，愿闻其详。
【在 p**s 的大作中提到】
: 都不用分，找个人数最少的club就行了
|
t*******r
发帖数: 22634 | 66 找到人数最少的 club 以后，再咋整？谢谢。
【在 p**s 的大作中提到】
: 都不用分，找个人数最少的club就行了
|
t*******r
发帖数: 22634 | 67 我想了想，她的办法可行。
找一个 degree 最低的 vertex，这样如果要有那种特殊 vertex，
那个 vertex 的所有 edge 跟 v1 都连在一起，所以那个特殊
vertex 就自动不会同色。
加上这个应该就能证明了。。。不过对小学生还是有点难度。。。
【在 b***e 的大作中提到】
: 又有大牛驾到。 那我洗耳恭听，愿闻其详。
|
t*******r
发帖数: 22634 | 68 不过要绕一个小小的弯子好像。。。因为 v1 要满足有两个 degree > 1
的 edge（否则分不出来），这样 degree 可能不一定是最低的 degree。
所以可能要先 prune 掉所有 degree == 1 的 edge，在找最低 degree
的。。。不过找最低 degree 的 vertex 这个想法确实可行。
【在 t*******r 的大作中提到】
: 我想了想，她的办法可行。
: 找一个 degree 最低的 vertex，这样如果要有那种特殊 vertex，
: 那个 vertex 的所有 edge 跟 v1 都连在一起，所以那个特殊
: vertex 就自动不会同色。
: 加上这个应该就能证明了。。。不过对小学生还是有点难度。。。
|
t*******r
发帖数: 22634 | 69 她说的有道理，当然她说的比较简略。
其实这个 complete hyper-graph 本身并不麻烦，唯一 tricky
的地方，就是在 starting vertex v1 上，对那些特殊 vertex
（全连在 v1 上）的 edge 的 partition 问题。。。所以如果
在满足有至少两条 edge 的 degree >= 1 的 vertex 里，选一个
degree 最低的，就能避免 partition 那些特殊 vertex 的 edge
。。。这样就证明了。
找最低 degree 的 vertex 开始 construction，in-general
也是一个不错的 trick。
【在 b***e 的大作中提到】
: 又有大牛驾到。 那我洗耳恭听，愿闻其详。
|
t*******r
发帖数: 22634 | 70 也不用 pruning，只要在有两条（或以上） edge 的 degree > 1 的 vertex
里面，选一个 degree 最低的就可以了。。。逻辑上加一点条件就可以了。
【在 t*******r 的大作中提到】
: 不过要绕一个小小的弯子好像。。。因为 v1 要满足有两个 degree > 1
: 的 edge（否则分不出来），这样 degree 可能不一定是最低的 degree。
: 所以可能要先 prune 掉所有 degree == 1 的 edge，在找最低 degree
: 的。。。不过找最低 degree 的 vertex 这个想法确实可行。
|
|
|
t*******r
发帖数: 22634 | 71 漏了选择起始点的想法，我觉得主要是没注意到 complete hyper-graph
并不是完全对称（或者说，并不是完全各向同性）。。。其实这个并不完全
对称的情况，在 complete 2-degree edge graph 里也存在。。，不过不
常整 complete graph 的 tricky 题，看到 complete graph 容易在脑子
里跑出来特么就是个圆滚滚的足球！！！仔细瞧才发现好像不那么圆滚滚。。。
// 哈哈， super fast run |
p**s
发帖数: 2707 | 72 一个白，其他黑，不在这个club的红
【在 t*******r 的大作中提到】
: 找到人数最少的 club 以后，再咋整？谢谢。
|
P******e
发帖数: 1325 | 73 找到人数最少的 club,这样其他任何club都不是这个club的子集。
在这个club分配两种颜色，其他所有club分第三种颜色。
【在 t*******r 的大作中提到】
: 找到人数最少的 club 以后，再咋整？谢谢。
|
x********o
发帖数: 25 | 74 随意挑两个不完全一样的组 A, B.
共有的人拿黑的, 其他的人分别 A里的拿红和 B里的拿白.
别的某组C必须要和A,B有共同成员,就一定颜色不同.
要是不存在这样的A和B .... 那这帮孩子就积极参加了各种俱乐部....就随意分配好了.
【在 b***e 的大作中提到】
: 有一群学生组织了一些俱乐部。每个俱乐部至少有两个成员。每两个俱乐部至少有一个
: 公共成员。现在给每个学生发一个帽子。帽子只有三种颜色：白色，黑色或红色。证明
: 存在一种分发的方式似的每一个俱乐部至少有两个成员拿到不同颜色的帽子。
|
b***e
发帖数: 1419 | 75 这个是我要找的答案。简洁明了， 佩服。
【在 p**s 的大作中提到】
: 一个白，其他黑，不在这个club的红
|
z***e
发帖数: 5600 | 76 补充一下，要选人数最少的一组，进行plus说的操作
【在 b***e 的大作中提到】
: 这个是我要找的答案。简洁明了， 佩服。
|
t*******r
发帖数: 22634 | 77 刚才想了想，只要人数最少就可以，不需要区分其它的。
【在 z***e 的大作中提到】
: 补充一下，要选人数最少的一组，进行plus说的操作
|
t*******r
发帖数: 22634 | 78 是，俺想了半天也没想到选人数最少一组。。。被提示后还想了半天才想明白。。。确
实佩服。
【在 b***e 的大作中提到】
: 这个是我要找的答案。简洁明了， 佩服。
|
d****g
发帖数: 7460 | 79 厉害。。厉害。。
但我觉得我的低级答案也是对的。
【在 b***e 的大作中提到】
: 这个是我要找的答案。简洁明了， 佩服。
|
s********s
发帖数: 259 | 80 一个有数学素养的人碰到此类问题第一反映就是“数学归纳法”。
N为俱乐部的个数。
N=2, trivial.
N>2, 假设N-1的方案已有，N很容易的。
找最小俱乐部的方法固然巧妙，但是要靠灵光一现。
数学归纳法的好处，系统，简单，是揭示问题本质的有力武器。 |
|
|
t*******r
发帖数: 22634 | 81 你那个 iterative 着色算法不常用啊，不利于通解“完全图”问题
。。。这道对马工应该是属于通解题，只是大伙儿对付完全图感觉
不太顺手。。。我还是倾向于 plus 的算法。。。
其实事实上，blaze 搞对了第一步大方向：BFS constructive
“wavefront” coloring algorithm 的算法大框架。
俺后来看到了是“完全图”，猜测是完全图的 “两步将死” 模式。
也猜中了。按照“完全图”建图论的模型，其实也就是个体力活。
后来我写证明时，发现完全图之两步将死的最后一步，不需要通
过 graph connection 走（走错了还会遗漏），直接把剩下的
edge 补齐。。。其实这个属于完全图的定式了。。。不过忘了
也慢慢 figure out 出来了。
最后俺和 blaze 是栽在完全图的 constructive algorithm
可能要从 “极值 degree” 的 vertex 开始 construct。。。
这个虽然这次是栽在这里，但下次估计可以通关。。。
所以我觉得还是老老实实走 plus 的 graph coloring 的正规
算法。外加多刷点完全图，才简单有效，我觉得。
这个原因，是完全图的变化其实比正常图要少太多，只是边的数量
很多，吓人。。。但边的数量本身，对图论不构成威胁。。。所以
我觉得还是 plus 的算法容易理解也不易出错。。。
当然，啥东东都还是要刷小时数的。。。拉马克也说了，用进废退！
【在 d****g 的大作中提到】
: 厉害。。厉害。。
: 但我觉得我的低级答案也是对的。
|
t*******r
发帖数: 22634 | 82 但对于有马工素养的而言，找最小俱乐部不是灵光一现。而是马工图论
constructive 算法里面常用的一招鲜。。。而且这个也有理论基础。
这次大伙儿没想到，多半是被完全图的貌似对称性给迷惑了。。。
属于被先验知识错误剪枝了。。。
当然数学归纳法其实也是 constructive algorithm 一种，但是
可能要实现成递归算法啊啊啊。。。如果能直接 constructive，
其实也没啥不好。。。
【在 s********s 的大作中提到】
: 一个有数学素养的人碰到此类问题第一反映就是“数学归纳法”。
: N为俱乐部的个数。
: N=2, trivial.
: N>2, 假设N-1的方案已有，N很容易的。
: 找最小俱乐部的方法固然巧妙，但是要靠灵光一现。
: 数学归纳法的好处，系统，简单，是揭示问题本质的有力武器。
|
t*******r
发帖数: 22634 | 83 我又想了想，其实 plus 的算法跟你的并不矛盾，也是数学归纳法的
思想。。。其实所有的 constructive algorithm 都是数学归纳法
的具体实现。。。在这里的 BFS constructive algorithm，一步
就一口气 construct 一个“波前”，两步 construct 完毕，而不是
一个一个俱乐部 construct，这个是差别。。。
从抽象代数的角度，一次 construct 一个“波前”，跟一次 construct
一个俱乐部，都是数学归纳法思想的具体实现。。。
【在 s********s 的大作中提到】
: 一个有数学素养的人碰到此类问题第一反映就是“数学归纳法”。
: N为俱乐部的个数。
: N=2, trivial.
: N>2, 假设N-1的方案已有，N很容易的。
: 找最小俱乐部的方法固然巧妙，但是要靠灵光一现。
: 数学归纳法的好处，系统，简单，是揭示问题本质的有力武器。
|
p**s
发帖数: 2707 | 84 你的答案不是低级，是太高级了，小学竞赛用归纳法，就跟鸡兔同笼用方程组一样。
【在 d****g 的大作中提到】
: 厉害。。厉害。。
: 但我觉得我的低级答案也是对的。
|
d****g
发帖数: 7460 | 85 那倒是。不用方程解鸡兔同笼就是考脑子啊。
【在 p**s 的大作中提到】
: 你的答案不是低级，是太高级了，小学竞赛用归纳法，就跟鸡兔同笼用方程组一样。
|
t*******r
发帖数: 22634 | 86 跟方程组不一样吧。。。数学归纳法（指 literally 写成那个样子的，不包括
一般的 constructive 算法）解完全图问题，不是那么容易找通解或者模式吧
。。。
【在 d****g 的大作中提到】
: 那倒是。不用方程解鸡兔同笼就是考脑子啊。
|
d****g
发帖数: 7460 | 87 如果真是讨论计算机算法的话：
递归就是得一组一组的涂。第N组需要多等等。不如plus的算法，来一个就能领帽子。。
但如果新建立一最小组呢？
【在 t*******r 的大作中提到】
: 跟方程组不一样吧。。。数学归纳法（指 literally 写成那个样子的，不包括
: 一般的 constructive 算法）解完全图问题，不是那么容易找通解或者模式吧
: 。。。
|
d****g
发帖数: 7460 | 88 Mm.那也是plus的算法简单。只要改从前的最小组和新的最小组就行了。
就跟非博纳妾数列有f(n)的公式一样。
。。
【在 d****g 的大作中提到】
: 如果真是讨论计算机算法的话：
: 递归就是得一组一组的涂。第N组需要多等等。不如plus的算法，来一个就能领帽子。。
: 但如果新建立一最小组呢？
|
t*******r
发帖数: 22634 | 89 其实这个问题之所以有这么“简单”的解，其实也是完全图的死穴之一。
（无 costing 的）完全图，从某个角度看，其实也是 trivial 的
一种体现。。。或者说，两两相通就是两两不通的叛逆。。。从矩阵
角度说，零矩阵 vs 单位矩阵。。。虽然单位矩阵还是要麻烦点。。。
所以俺一上来就奔着那种只着一个 颜色 0，然后每步换色，两步将死，
这种很 “偏” 的解。。。反正老板没说要色平衡。。。当然俺的发动机
太不给力，没搞定。。。
【在 d****g 的大作中提到】
: Mm.那也是plus的算法简单。只要改从前的最小组和新的最小组就行了。
: 就跟非博纳妾数列有f(n)的公式一样。
:
: 。。
|
t*******r
发帖数: 22634 | 90 不过我觉得，dcbang 你的办法更接近数学，而 plus 的办法更接近信息学。
这两个学科的理念不太一样，或者说，太不一样。。。信息学其实是隶属于
science，更像物理学而不是数学。。。
【在 d****g 的大作中提到】
: 那倒是。不用方程解鸡兔同笼就是考脑子啊。
|
|
|
i***h
发帖数: 12655 | 91 这个证明太棒了
一句话讲清楚
【在 p**s 的大作中提到】
: 一个白，其他黑，不在这个club的红
|
i***h
发帖数: 12655 | 92 我也是第一反映数学归纳法。
然后。。。没想出来
【在 s********s 的大作中提到】
: 一个有数学素养的人碰到此类问题第一反映就是“数学归纳法”。
: N为俱乐部的个数。
: N=2, trivial.
: N>2, 假设N-1的方案已有，N很容易的。
: 找最小俱乐部的方法固然巧妙，但是要靠灵光一现。
: 数学归纳法的好处，系统，简单，是揭示问题本质的有力武器。
|
t*******r
发帖数: 22634 | 93 我觉得你那个数学归纳法的话，对解题非常好。。。但对于为现代
信息学打基础的扑通蛙，仅仅上那个数学归纳法，可能 doesn't
promote comprehending mathematical structure。。。因为
这个巧妙的数学归纳法证明里，不需要理解 “完全图”。如果遇上
偷懒扑通蛙就不去理解了。。。当然，自推型天才蛙另说。。。
俺昨天跟娃聊 2012版美国数学计算题八的第十题解法的时候，讲到
理解排列问题的时候，发现确实可能是这个问题。。。在从 list
& check 到数学公式数学逻辑，当中有非常重要的一步体力活，就是
decision tree。。。这题里还包括用不同的 decision tree 理解
公式里的除法。
俺说到一半的时候，忽然想起来跟娃说，其实世界上的聪明蛙 gifted kids
实在太多了。这种题目给那些蛙，他们 intuitive 就能理解公式里
的除法，他们很多还会灵机一动想出非常巧妙的解法。。。 但是学
数学很多时候就是要拼体力。我怀疑有部分聪明蛙，可能就是因此而
不画各种 decision tree，（至少要在大脑里画），最后到超出
intuition 的复杂逻辑还是会遇上瓶颈。。。其实智商对大部分娃，
可能是个 overrate 的东东。超过平均水平的智商足够学任何复杂的
实用数学了，重要的还是 diligent diligent diligent（也就是
小时数）。。。
【在 d****g 的大作中提到】
: 那倒是。不用方程解鸡兔同笼就是考脑子啊。
|
b***e
发帖数: 1419 | 94 有一群学生组织了一些俱乐部。每个俱乐部至少有两个成员。每两个俱乐部至少有一个
公共成员。现在给每个学生发一个帽子。帽子只有三种颜色：白色，黑色或红色。证明
存在一种分发的方式似的每一个俱乐部至少有两个成员拿到不同颜色的帽子。 |
d******e
发帖数: 2265 | 95 这个不是马工面试题目嘛
【在 b***e 的大作中提到】
: 有一群学生组织了一些俱乐部。每个俱乐部至少有两个成员。每两个俱乐部至少有一个
: 公共成员。现在给每个学生发一个帽子。帽子只有三种颜色：白色，黑色或红色。证明
: 存在一种分发的方式似的每一个俱乐部至少有两个成员拿到不同颜色的帽子。
|
l*****e
发帖数: 2447 | 96 缺限制条件？
【在 b***e 的大作中提到】
: 有一群学生组织了一些俱乐部。每个俱乐部至少有两个成员。每两个俱乐部至少有一个
: 公共成员。现在给每个学生发一个帽子。帽子只有三种颜色：白色，黑色或红色。证明
: 存在一种分发的方式似的每一个俱乐部至少有两个成员拿到不同颜色的帽子。
|
b***e
发帖数: 1419 | 97 愿闻其详。
【在 l*****e 的大作中提到】
: 缺限制条件？
|
b***e
发帖数: 1419 | 98 You can you up, LOL.
【在 d******e 的大作中提到】
: 这个不是马工面试题目嘛
|
l*****e
发帖数: 2447 | 99 哦，没有，原来想的对的，后来自己绕了一下，老了。
【在 b***e 的大作中提到】
: 愿闻其详。
|
b***e
发帖数: 1419 | 100 三个半个小时的竞赛，四道题。其它三道都是渣。这题太牛逼了。你这路子说的是正的
，但是要真构造起来还不是那么简单。反正要考我我当场是做不出来的。
【在 t*******r 的大作中提到】
: I think a graph-based BFS constructive traversal & coloring algorithm can
: proof this. The theoretical base is binary logic on graph construction's "
: wave front".
|
|
|
b***e
发帖数: 1419 | 101 Sure. 愿闻其详。
【在 t*******r 的大作中提到】
: 我晚上写个详细的。俺现在有事忙。
|
f**e
发帖数: 890 | 102 没看懂，帽子数量没限制，这个不是随便发吗？公共人员统一一个颜色，其他人随意用
其他剩下颜色不久可以了？有什么东西我漏了？看来有必要重回小学了。
【在 b***e 的大作中提到】
: 有一群学生组织了一些俱乐部。每个俱乐部至少有两个成员。每两个俱乐部至少有一个
: 公共成员。现在给每个学生发一个帽子。帽子只有三种颜色：白色，黑色或红色。证明
: 存在一种分发的方式似的每一个俱乐部至少有两个成员拿到不同颜色的帽子。
|
z***e
发帖数: 1757 | 103 如果没有“其他人”呢？
【在 f**e 的大作中提到】
: 没看懂，帽子数量没限制，这个不是随便发吗？公共人员统一一个颜色，其他人随意用
: 其他剩下颜色不久可以了？有什么东西我漏了？看来有必要重回小学了。
|
f**e
发帖数: 890 | 104 公共人员多余一个的话，两个人用不一样颜色的。还漏了什么？
【在 z***e 的大作中提到】
: 如果没有“其他人”呢？
|
z***e
发帖数: 1757 | 105 什么叫“公共人员多余一个"?
【在 f**e 的大作中提到】
: 公共人员多余一个的话，两个人用不一样颜色的。还漏了什么？
|
f**e
发帖数: 890 | 106 错字，“公共人员多于一个人”。大概是这样考虑到你说的漏掉的情况：
1.公共人员的第一个人选一个颜色的帽子。
2.公共人员的第二个人选第二个颜色的帽子。
3.。。。
4.如果没有公共人员的话，把那个帽子给同组的其他人，没有的话给另一个组的人，重
复。
【在 z***e 的大作中提到】
: 什么叫“公共人员多余一个"?
|
f**e
发帖数: 890 | 107 你这个是overkill 了，只有三个颜色，要求只要有两个颜色就可以。不需要遍历每个
人，遍历每个俱乐部两次足以。如果每个俱乐部一亿人，你这就多做很多无用功了。
【在 t*******r 的大作中提到】
: 我就快速写一个概念，用自然语言小学娃能看懂的。具体严格证明
: 要花点时间。
: 概念上很简单，也就是最关键的核心问题，是只有两个娃的俱乐部，
: 并且那两个娃还隶属其他只有两个娃俱乐部。
: 这个问题很简单，图景上其实就是共享顶点（拓扑）三角形问题：
: 顶点对应娃，某条边对应俱乐部。
: （1）找第一个顶点着色 0，然后连接的第二个顶点着色 1。
: （2）然后把第一个和第二个顶点都有连接的顶点着色 2。
: （3）然后从所有颜色 2 的顶点开始，把所有跟颜色 0 和颜色 2
: 有连接的顶点，都着成颜色 1。
|
b***e
发帖数: 1419 | 108 你这个构造的问题在于以前染过的点有可能被重染，破坏以前的已经做好的set。我的
直观想法和你这个类似，但是严格证明的时候漏洞无法弥补。 我最终的方法是要保证
染过的点就定下来了，在以后的算法过程中不会被重染。
【在 t*******r 的大作中提到】
: 我就快速写一个概念，用自然语言小学娃能看懂的。具体严格证明
: 要花点时间。
: 概念上很简单，也就是最关键的核心问题，是只有两个娃的俱乐部，
: 并且那两个娃还隶属其他只有两个娃俱乐部。
: 这个问题很简单，图景上其实就是共享顶点（拓扑）三角形问题：
: 顶点对应娃，某条边对应俱乐部。
: （1）找第一个顶点着色 0，然后连接的第二个顶点着色 1。
: （2）然后把第一个和第二个顶点都有连接的顶点着色 2。
: （3）然后从所有颜色 2 的顶点开始，把所有跟颜色 0 和颜色 2
: 有连接的顶点，都着成颜色 1。
|
z***e
发帖数: 1757 | 109 注意："每两个俱乐部至少有一个公共成员"
【在 t*******r 的大作中提到】
: 我刚才真的去证明了一下。。。我觉得这道题是不是错了。。。
: 比如这个反例：
: 如果我们用这个拓扑图形来表示：
: （1）把 “顶点” 认为是娃
: （2）“边” 认为是俱乐部
: 那对于正方形加两对角线，这个三种颜色漆不出来吧。我待会儿
: 上个图。
|
b***e
发帖数: 1419 | 110 那你严格的证明吧，虽然我不看好你这个路子。
【在 t*******r 的大作中提到】
: 哦，忘了这个。那应该就证明了。。。
|
|
|
b***e
发帖数: 1419 | 111 恕我愚钝，没懂。在图论里，边是没有degree的，只有两个顶点。你顶多是建一个二分
图，一边是人，一边是俱乐部，然后用边来表示从属关系。然后呢？
【在 t*******r 的大作中提到】
: 哈哈俺太粗心看错题了。。。有了这个限制条件，那证明也太简单了。。。这么反过来
: 映射到图论:
: 把俱乐部映射成 vertex，把娃映射成 edge（edge 的 degree 允许 > 2）。。。因为
: 有这个限制条件，所以这是个 complete graph。。。直接两步将死。。。
|
b***e
发帖数: 1419 | 112 不捉急，我看你也是个严肃的讨论者。我也是想看看有没有直观的解法。我没有见过边
带drgree的图论。不过我很业余，没有受过正规的数学训练。你这个拓扑意义上的图论
里的完全图概念我不是很理解。
【在 t*******r 的大作中提到】
: 图论里的 edge 是可以有 degree，因为那个是 topological 的，
: 可以不是一条线段。
: 图论是建立在集合论之上的，所谓 edge，其实是一个 set，该 set
: 告诉这个 edge 连接到那些 vertex，可以包括两个以上的 vertex。
: 我吃完饭了，我马上写一个严格证明，你稍稍等一下。
|
b***e
发帖数: 1419 | 113 模型很清晰，虽然我对那个边上有degree的图论表示怀疑。
【在 t*******r 的大作中提到】
: 因为这个是 word problem，我现在先写严格证明的第一步，
: 数学建模：把题目建模成图论表述。
: A: 映射：
: （1）把 “俱乐部” 映射 成图论里的 vertex。
: （2）把 “娃” 映射 成图论里的 edge。
: （3）把 “戴帽子” 映射 成图论里对 edge 的 着色。
: B: 题目条件：
: （1）任何 vertex 的 degree >= 2
: （2）任何 edge 的 degree >= 1
: （3）任何两个 vertex 之间，至少存在一条 edge（complete graph）
|
f**e
发帖数: 890 | 114 先赞一下，再问问题。
1.原题的这句话“每两个俱乐部至少有一个公共成员”这句话我开始下意识理解为排他
，后来看到提醒，才意识到自己理解错了。这个有没有英文原题？
2.vertex 的degree代表可以连到多个vertex?
3.edge 的degree代表学生个数？
4. 我理解的图形是这样的
5.AB, AD 之间可能是同一个人，都是S1,他们必须是同一个颜色，你怎么避免给他们着
不同的色？
6.如果两V之间只有一个EDGE（代表多个学生）,那这个EDGE 就不能只是一个颜色，对
吧？
【在 t*******r 的大作中提到】
: 现在我写解法，因为我已经把题目映射成图论符号（自然语言表述），
: 所以现在开始我只用图论符号（自然语言表示）。
: （1）寻找任何一条 degree >= 2 的 edge，记为 e1。
: （2）如果找不到 e1，该问题里所有的 edge 的 degree 都是 1。
: 这样是个 trivial 的问题。
: （3）如果找到 e1，先把 e1 着色为颜色 0。
: （4）从 e1 所连接 vertex 里面，选出两个，记录为 v1 和 v2。
: （5）从 v1 找连接 v1 的所有 edge e，如果 e 还没有被着色，
: 那就把 e 着色为颜色 1。
: （6）从 v2 找连接 v2 的所有 edge e，如果 e 还没有着色，
|
f**e
发帖数: 890 | 115 还是上图，也是我最开始画的。 :)集合论还是高中水平，大学之后就是简单的ODE,PDE
。第七步简化，只考虑每个人都属于最少两个俱乐部，这不影响解题方法。
（7）最后对 degree 为 1 的所有 edge 着色，着色成其连接
的 v 所连接的 e 的不同颜色（如果 v 已经连接两种颜色的
e 了，那么随便着一种色）。
V1:{0,1}
V2:{0,2}
V不可以只有{0}?这种上色方法好像不可以保证每个俱乐部都最少两个颜色？
【在 t*******r 的大作中提到】
: 上集合论的意思是。。。图论的图形只是看看，证明需要集合逻辑，
: 比如 any 算子，exist 算子。。。当然不要那么学究，写成
: 自然语言表述。。。等我忙完回来写完那个证明。。。
: 另外 edge degree > 1 就别画成简单线型，你可以画成 star
: model 或者 spanning tree 啥的。。。
|
f**e
发帖数: 890 | 116 辛苦：这个有疑问：
“（2）如果出现 v 有且仅一条 edge 同时连到 v1 和 v2，
那这条 edge 一定是 e1，颜色为 0。
--理解
那 v 至少还有一条
edge，那条 edge 要么连到 v1，要么连到 v2，要么啥都
不连，总之颜色不会被着色成 0。不同色。”
--为啥v不可以连到其他的v？一个人（比如这个人颜色是0）同时属于所有的俱乐部就
满足了COMPLETE GRAPH 这个条件，v的第二个颜色你没保证不可以是0。你好像只着了
和保证了V1，V2的颜色，其他的v你怎么着的色，我漏掉什么了？
【在 t*******r 的大作中提到】
: 现在我写证明：
: 对于 v1 和 v2：一条 edge e1 着色为颜色 0，各自至少一条 edge
: 着成非颜色 0。（这个证明我写得比较简略，反正看了下面
: 的复杂情况，自然能理解这个。。。码字费力）。
: 对于任何不是 v1 或 v2 的 vertex v，因为是 complete graph，
: 所以 v 和 v1，以及 v 和 v2，都存在至少一条连接（edge），所以
: 有以下几种情况：
: （1）如果出现 v 有两条（或更多）的 edge，该 edge 同时
: 连到 v1 和 v2，那么其中一条一定是 e1，颜色为 0。另一条
: 是颜色 1。不同色。
|
b***e
发帖数: 1419 | 117 所以我认为你把这个问题归结为一个你所谓的“拓扑图论”问题的做法是不行的。图论
里图的定义就是每条边连接两个顶点。对于这个题目一个正常的图论模型来应该是一个
二分图。一侧是人，另一侧是俱乐部。中间的连线表是从属关系。
不过话说回来，我的本意是这个小学生数学竞赛为啥出这种题？是不是出错了。这一个
题没有三个小时我反正做不出来。
【在 t*******r 的大作中提到】
: 如果所有的 edge 都是 degree 2 的 edge，而这又是一个 complete graph，
: 那这个 着色问题是个 trivial 问题。。。你只要把这个 complete graph
: 的 vertexes 给随便给 partition 成两个 partition，然后把
: partition 1 内部的 edge 着色成 颜色 0，partition 2 内部的
: edge 着色成 颜色 1 连接 partition 1 和 partition 2 的
: edge 着色成 颜色 3。。。
: 当然题目不会这么 trivial。。。问题显然是在于 edge 的 degree > 2
: 的情况。
|
m**k
发帖数: 18660 | 118 潮水哥威武
【在 b***e 的大作中提到】
: 所以我认为你把这个问题归结为一个你所谓的“拓扑图论”问题的做法是不行的。图论
: 里图的定义就是每条边连接两个顶点。对于这个题目一个正常的图论模型来应该是一个
: 二分图。一侧是人，另一侧是俱乐部。中间的连线表是从属关系。
: 不过话说回来，我的本意是这个小学生数学竞赛为啥出这种题？是不是出错了。这一个
: 题没有三个小时我反正做不出来。
|
d****g
发帖数: 7460 | 119 设N组符合条件。建立N+1.有没帽子成员简单。若都是绿帽。把绿1变红，如果G1抗议，
说明G1除绿1全红。说明绿2不在G1。那把绿2变紫必须可以。如不可，说明有G2除绿2全
紫。那
么G2和
G1怎么香蕉的呢。 |
C*****d
发帖数: 2253 | 120 你的画法如果有人参加三个组怎么办？一个edge难道可以有大于2个vertex?
【在 t*******r 的大作中提到】
: 你这么画难道不是一回事？你这个有两种 vertex、并且 edge 的 degree 是 2
: 的图，跟只有一种 vertex、但允许 edge degree 是任何自然数的图，难道
: 不是等价图？。。。话说你把 edge 和 vertex 换过来也行，只是 complete
: graph 容易不容易看的问题。
: 当然我前面的漏洞补掉也不难，我重新写一个。不过不写严格的，我写个简单的。
|
|
|
p**s
发帖数: 2707 | 121 挺好的题，分两种情况处理，出给小学生也不算过分 |
p**s
发帖数: 2707 | |
b***e
发帖数: 1419 | 123 又有大牛驾到。 那我洗耳恭听，愿闻其详。
【在 p**s 的大作中提到】
: 都不用分，找个人数最少的club就行了
|
p**s
发帖数: 2707 | 124 一个白，其他黑，不在这个club的红
【在 t*******r 的大作中提到】
: 找到人数最少的 club 以后，再咋整？谢谢。
|
P******e
发帖数: 1325 | 125 找到人数最少的 club,这样其他任何club都不是这个club的子集。
在这个club分配两种颜色，其他所有club分第三种颜色。
【在 t*******r 的大作中提到】
: 找到人数最少的 club 以后，再咋整？谢谢。
|
x********o
发帖数: 25 | 126 随意挑两个不完全一样的组 A, B.
共有的人拿黑的, 其他的人分别 A里的拿红和 B里的拿白.
别的某组C必须要和A,B有共同成员,就一定颜色不同.
要是不存在这样的A和B .... 那这帮孩子就积极参加了各种俱乐部....就随意分配好了.
【在 b***e 的大作中提到】
: 有一群学生组织了一些俱乐部。每个俱乐部至少有两个成员。每两个俱乐部至少有一个
: 公共成员。现在给每个学生发一个帽子。帽子只有三种颜色：白色，黑色或红色。证明
: 存在一种分发的方式似的每一个俱乐部至少有两个成员拿到不同颜色的帽子。
|
b***e
发帖数: 1419 | 127 这个是我要找的答案。简洁明了， 佩服。
【在 p**s 的大作中提到】
: 一个白，其他黑，不在这个club的红
|
z***e
发帖数: 5600 | 128 补充一下，要选人数最少的一组，进行plus说的操作
【在 b***e 的大作中提到】
: 这个是我要找的答案。简洁明了， 佩服。
|
d****g
发帖数: 7460 | 129 厉害。。厉害。。
但我觉得我的低级答案也是对的。
【在 b***e 的大作中提到】
: 这个是我要找的答案。简洁明了， 佩服。
|
s********s
发帖数: 259 | 130 一个有数学素养的人碰到此类问题第一反映就是“数学归纳法”。
N为俱乐部的个数。
N=2, trivial.
N>2, 假设N-1的方案已有，N很容易的。
找最小俱乐部的方法固然巧妙，但是要靠灵光一现。
数学归纳法的好处，系统，简单，是揭示问题本质的有力武器。 |
|
|
p**s
发帖数: 2707 | 131 你的答案不是低级，是太高级了，小学竞赛用归纳法，就跟鸡兔同笼用方程组一样。
【在 d****g 的大作中提到】
: 厉害。。厉害。。
: 但我觉得我的低级答案也是对的。
|
d****g
发帖数: 7460 | 132 那倒是。不用方程解鸡兔同笼就是考脑子啊。
【在 p**s 的大作中提到】
: 你的答案不是低级，是太高级了，小学竞赛用归纳法，就跟鸡兔同笼用方程组一样。
|
d****g
发帖数: 7460 | 133 如果真是讨论计算机算法的话：
递归就是得一组一组的涂。第N组需要多等等。不如plus的算法，来一个就能领帽子。。
但如果新建立一最小组呢？
【在 t*******r 的大作中提到】
: 跟方程组不一样吧。。。数学归纳法（指 literally 写成那个样子的，不包括
: 一般的 constructive 算法）解完全图问题，不是那么容易找通解或者模式吧
: 。。。
|
d****g
发帖数: 7460 | 134 Mm.那也是plus的算法简单。只要改从前的最小组和新的最小组就行了。
就跟非博纳妾数列有f(n)的公式一样。
。。
【在 d****g 的大作中提到】
: 如果真是讨论计算机算法的话：
: 递归就是得一组一组的涂。第N组需要多等等。不如plus的算法，来一个就能领帽子。。
: 但如果新建立一最小组呢？
|
i***h
发帖数: 12655 | 135 这个证明太棒了
一句话讲清楚
【在 p**s 的大作中提到】
: 一个白，其他黑，不在这个club的红
|
i***h
发帖数: 12655 | 136 我也是第一反映数学归纳法。
然后。。。没想出来
【在 s********s 的大作中提到】
: 一个有数学素养的人碰到此类问题第一反映就是“数学归纳法”。
: N为俱乐部的个数。
: N=2, trivial.
: N>2, 假设N-1的方案已有，N很容易的。
: 找最小俱乐部的方法固然巧妙，但是要靠灵光一现。
: 数学归纳法的好处，系统，简单，是揭示问题本质的有力武器。
|
e****m
发帖数: 484 | 137 有数学修养的人立马会用反证法，在极大极小值上构造结论 来解决一般纯在性问题。
甚至都不用具体构造
【在 s********s 的大作中提到】
: 一个有数学素养的人碰到此类问题第一反映就是“数学归纳法”。
: N为俱乐部的个数。
: N=2, trivial.
: N>2, 假设N-1的方案已有，N很容易的。
: 找最小俱乐部的方法固然巧妙，但是要靠灵光一现。
: 数学归纳法的好处，系统，简单，是揭示问题本质的有力武器。
|
s*****j
发帖数: 6435 | 138 数学无非三种方法.
演绎, 归纳, 反证
水平低的, 从左往右想问题. 水平高的, 从右往左想问题.
【在 e****m 的大作中提到】
: 有数学修养的人立马会用反证法，在极大极小值上构造结论 来解决一般纯在性问题。
: 甚至都不用具体构造
|
