w******u
发帖数: 157 | 1 我是大概10年前参加的，发现现在的题型变化挺大。07年第3题好象挺难的，大家讨论
讨论吧。
Problem 3. In a mathematical competition some competitors are friends.
Friendship is always mutual. Call a group of competitors a clique if each
two of them are friends. (In particular, any group of fewer than two
competitors is a clique.) The number of members of a clique is called its
size. Given that, in this competition, the largest size of a clique is even,
prove that the competitors can be arranged in two rooms such that the
largest size of a c | p******n
发帖数: 46 | 2 Graph theory problem:
Let $G$ be a connected graph such that the clique number $w(G)$ is even.
Then $G$ has an edge cut $S$ such that clique numbers of the two components of $G\setminus S$ are equal. | c*******h
发帖数: 1096 | 3 找到最大的clique，平分两半A和B，分别扔到两个房间1和2。
每个房间找各自最大的clique。然后移动A的一部分到房间2，
或者移动B的一部分到房间1，使两个房间的最大clique大小相
等。
大概思路就这样了。
even,
【在 w******u 的大作中提到】
: 我是大概10年前参加的，发现现在的题型变化挺大。07年第3题好象挺难的，大家讨论
: 讨论吧。
: Problem 3. In a mathematical competition some competitors are friends.
: Friendship is always mutual. Call a group of competitors a clique if each
: two of them are friends. (In particular, any group of fewer than two
: competitors is a clique.) The number of members of a clique is called its
: size. Given that, in this competition, the largest size of a clique is even,
: prove that the competitors can be arranged in two rooms such that the
: largest size of a c
| A*******r
发帖数: 768 | | B****n
发帖数: 11290 | 5 I'M Obama
【在 A*******r 的大作中提到】
: IMO是什么？
| s*******n
发帖数: 740 | 6 In my opinion
【在 A*******r 的大作中提到】
: IMO是什么？
| s*******n
发帖数: 740 | 7 lz是代表中国参加的吗？
按你的用户名看，没有一个人符合。。 | H*****s
发帖数: 32 | 8 用什么做不变量呢?
我猜该是这样:假设最大的clique有2n人，存在一种分法，使每侧最大的clique有n人。
(冬冬) 的大作中提到: 】
【在 c*******h 的大作中提到】
: 找到最大的clique，平分两半A和B，分别扔到两个房间1和2。
: 每个房间找各自最大的clique。然后移动A的一部分到房间2，
: 或者移动B的一部分到房间1，使两个房间的最大clique大小相
: 等。
: 大概思路就这样了。
:
: even,
| l********e
发帖数: 3632 | | b*******i
发帖数: 548 | | | | h**********c
发帖数: 4120 | 11 [5] Stephen H. Friedberg, Arnold J. Insel, Lawrence E. Spence, Linear Al-
gebra Fourth Edition, Prentice, New Delhi, 2007. PP94
In fact mathematics is not my area, my area relates to stochastic guessing. | h**********c
发帖数: 4120 | 12 I not giving any answers here, it is not my area.
I just try to discuss what is 'clique', ps.
【在 h**********c 的大作中提到】
: [5] Stephen H. Friedberg, Arnold J. Insel, Lawrence E. Spence, Linear Al-
: gebra Fourth Edition, Prentice, New Delhi, 2007. PP94
: In fact mathematics is not my area, my area relates to stochastic guessing.
| h**********c
发帖数: 4120 | 13 IMO is for KU18 as I remember, not for APs. | H*****s
发帖数: 32 | 14 This is wrong. Say 5 people, A knows B, B knows C, C knows D, D knows E, E
knows A.
【在 H*****s 的大作中提到】
: 用什么做不变量呢?
: 我猜该是这样:假设最大的clique有2n人，存在一种分法，使每侧最大的clique有n人。
:
: (冬冬) 的大作中提到: 】
| H*****s
发帖数: 32 | 15 I find a proof, but rather complicated. The idea is to minimize the maximal
clique after dividing into two groups. And define the invariant according to
this idea(to define it also requires some work).
As the 3rd problem, we usually do not expect a short solution.
even,
【在 w******u 的大作中提到】
: 我是大概10年前参加的，发现现在的题型变化挺大。07年第3题好象挺难的，大家讨论
: 讨论吧。
: Problem 3. In a mathematical competition some competitors are friends.
: Friendship is always mutual. Call a group of competitors a clique if each
: two of them are friends. (In particular, any group of fewer than two
: competitors is a clique.) The number of members of a clique is called its
: size. Given that, in this competition, the largest size of a clique is even,
: prove that the competitors can be arranged in two rooms such that the
: largest size of a c
|
|
