Q:
In every round robin tennis tournament, there is a player who, for any other player p, has either beaten p or beaten some player who has beaten p.
Zh:
n个人中每两个人之间都进行过一次比赛。假设比赛不可能出现平局。证明，一定能找出这样的一个人，对于其它任何一人p，他击败了p或者击败了某个打败了p的人。
A:
The problem has been characterized as a quickie: once you hit on the right idea, the solution takes just a few lines.
There may be several players with the stated property: for any other player p, this one either beat p or beat a player who has beaten p. The nice idea that makes the problem a quickie is that the player who won most of the games has this property. Let P be such a player and GP a group of players beaten by P. Assume there is a player q not in GP who, in addition, has not lost to any p in GP. Since, it's a round robin tournament, that is a tournament in which every player meets any other player, q met with P and any player from GP. Moreover, since he has not lost to either P or any member of the GP group, he won all those meets implying that he won more meets than P. Contradiction with the selection of P. In other words, any q that is not in GP has been beaten by a member of the GP group.
The problem admits a recasting in terms of Graph Theory. Start with a complete graph Kn, n > 1. (A graph is complete if any two nodes are joined by an edge.) Convert Kn to a directed graph (digraph) by arbitrarily assigning to each edge a direction. The problem stipulates the existence of a node from which any other node is accessible by a directed path of the length at most 2.
2008年9月8日星期一
9.8
Q:
There are 2n + 1 people with the property that, for any n of them, there is some one of the 2n + 1, not among the n, acquainted with all n. Show that there is a person that is acquainted with every one present.
A:
The problem has been characterized as a quickie: once you hit on the right idea, the solution takes just a few lines.
The problem has a natural representation as a graph: two nodes are connected by an edge iff the fellows they represent are acquainted. The nice idea that makes the problem a quickie is that, under the conditions of the problem, there is always a clique of size at least n + 1. A clique is a term for a subgraph that, as a graph, is complete.
Let's first show that the existence of a clique C of size n + 1 leads to a solution of the problem. Let R be the remaining nodes. By the conditions of the problem, there exists a node outside R that is connected to every node in R. Since this node belongs to C (in which all the nodes are connected to each other), this node is connected to all other nodes.
Now, let's form a clique of size n + 1. Pick any n nodes. There is a node that is connected to each of the selected ones. This one, along with any of the selected, form a clique of size 2. Arbitrarily add n - 2 nodes to these two. There is a node that is connected to each of the selected ones. Along with a 2-clique it forms a 3-clique. We may continue in this manner until we get an n-clique. For this, as for any collection of n nodes, there is a node connected to each of the selected ones. Together they form an (n + 1)-clique.
There are 2n + 1 people with the property that, for any n of them, there is some one of the 2n + 1, not among the n, acquainted with all n. Show that there is a person that is acquainted with every one present.
A:
The problem has been characterized as a quickie: once you hit on the right idea, the solution takes just a few lines.
The problem has a natural representation as a graph: two nodes are connected by an edge iff the fellows they represent are acquainted. The nice idea that makes the problem a quickie is that, under the conditions of the problem, there is always a clique of size at least n + 1. A clique is a term for a subgraph that, as a graph, is complete.
Let's first show that the existence of a clique C of size n + 1 leads to a solution of the problem. Let R be the remaining nodes. By the conditions of the problem, there exists a node outside R that is connected to every node in R. Since this node belongs to C (in which all the nodes are connected to each other), this node is connected to all other nodes.
Now, let's form a clique of size n + 1. Pick any n nodes. There is a node that is connected to each of the selected ones. This one, along with any of the selected, form a clique of size 2. Arbitrarily add n - 2 nodes to these two. There is a node that is connected to each of the selected ones. Along with a 2-clique it forms a 3-clique. We may continue in this manner until we get an n-clique. For this, as for any collection of n nodes, there is a node connected to each of the selected ones. Together they form an (n + 1)-clique.
2008年6月24日星期二
龙宽的生活
龙宽
18岁的我，不会设计未来
龙宽
我在飞机上吐了个天翻地覆。站在海关人员面前我的身体发飘，大脑累得不想再转。他要我把身上带着的一大沓美元拿出来给他看，又问我数目是多少，我说大概有五千。这么些钱够支持多久？他问我。
“我父母还会再寄钱来。”这是谎话。
他不信任地看了我一眼，盖上了九个月的签证。
这是1998年1月4日的晚上，第一眼看到伦敦的时候它就在下雨。
去英国对于我所有的朋友来说是一件突然的事，我在北京的生活刚刚进入最舒服的阶段，每天跟一群感情深厚的哥们儿生活在一起，和唱片公司准备签约做专辑。而我放弃这一切跑到英国的原因很简单，因为十八岁的我不可救药地爱上了一个英国人，所以在他回国以后决定去找他。
瑞斯克是让我不顾一切飞越万水千山来到英国的人，早已在伦敦有着稳定的生活，他说不愿意见我。马上打道回府的想法在我脑子里一闪而过，接下来的念头是，我要留下来。我要在伦敦呆下去。
一个人在十八岁的时候从不会设计未来，因此我压根儿就没想过到了英国以后的生活会怎样开始，没给自己设计一条退路。如果不是为了爱情住在这个国家，那么它吸引我的只有音乐，比北京更广阔的音乐空间。
第一个星期我出去买了一份专门登各种免费广告的报纸Loot，在上面给自己登了一条消息：中国女孩，歌手兼吉他手兼词曲创作人，有意组乐队者请打电话。接下来的一个月里，我接到了三十多个电话，但大多数人只是看到了广告上的“中国女孩”而感兴趣，我见到了各种各样不靠谱的乐手，他们不是根本不会弹琴，就是拨弄两下吉他以后就开始对我胡言乱语。
我借住在北京认识的帕特家里，他在伦敦大学上学，我每天白天在街上走来走去熟悉街道，心里想，这里的冬天真暖和。空气因为经常下雨而非常潮湿，温度跟北京的春天差不多。周围的人似乎都在过着井然有序的生活，白天人人都去上班了，路上行人稀少，只有牵着狗的老人和附近大学的学生不慌不忙地在街上走。头两天我走着走着就迷路了，向许多人问路才回到家，被问的人知道我英文不好，都微笑着慢慢讲。
那段时间内伦敦确实给了我非常良好的印象，超市里面的食物之多让我兴奋不已，超市外面有人在卖一种叫Biglssue的杂志，它是专为无家可归的人和失业者办的，售价一英镑，卖它的人每份可以得到45便士。租录像带的商店里有我想看而在中国找不到的全部电影，就是在公共汽车上和地铁里，也像是在看电影一样，有那么多酒鬼、疯子，打扮很酷的年轻人和穿西装的白领上班族并排坐在一起，这一切让我觉得伦敦是一个色彩丰富、充满机会的城市，对于前面未知的生活，我不再感到担心。
我住的地区叫King’Gross，是伦敦有名的红灯区，街上电话亭里贴满了妓女的照片，我把它们都摘了下来，贴在我练琴房间的墙上当做装饰品。
18岁的我，不会设计未来
龙宽
我在飞机上吐了个天翻地覆。站在海关人员面前我的身体发飘，大脑累得不想再转。他要我把身上带着的一大沓美元拿出来给他看，又问我数目是多少，我说大概有五千。这么些钱够支持多久？他问我。
“我父母还会再寄钱来。”这是谎话。
他不信任地看了我一眼，盖上了九个月的签证。
这是1998年1月4日的晚上，第一眼看到伦敦的时候它就在下雨。
去英国对于我所有的朋友来说是一件突然的事，我在北京的生活刚刚进入最舒服的阶段，每天跟一群感情深厚的哥们儿生活在一起，和唱片公司准备签约做专辑。而我放弃这一切跑到英国的原因很简单，因为十八岁的我不可救药地爱上了一个英国人，所以在他回国以后决定去找他。
瑞斯克是让我不顾一切飞越万水千山来到英国的人，早已在伦敦有着稳定的生活，他说不愿意见我。马上打道回府的想法在我脑子里一闪而过，接下来的念头是，我要留下来。我要在伦敦呆下去。
一个人在十八岁的时候从不会设计未来，因此我压根儿就没想过到了英国以后的生活会怎样开始，没给自己设计一条退路。如果不是为了爱情住在这个国家，那么它吸引我的只有音乐，比北京更广阔的音乐空间。
第一个星期我出去买了一份专门登各种免费广告的报纸Loot，在上面给自己登了一条消息：中国女孩，歌手兼吉他手兼词曲创作人，有意组乐队者请打电话。接下来的一个月里，我接到了三十多个电话，但大多数人只是看到了广告上的“中国女孩”而感兴趣，我见到了各种各样不靠谱的乐手，他们不是根本不会弹琴，就是拨弄两下吉他以后就开始对我胡言乱语。
我借住在北京认识的帕特家里，他在伦敦大学上学，我每天白天在街上走来走去熟悉街道，心里想，这里的冬天真暖和。空气因为经常下雨而非常潮湿，温度跟北京的春天差不多。周围的人似乎都在过着井然有序的生活，白天人人都去上班了，路上行人稀少，只有牵着狗的老人和附近大学的学生不慌不忙地在街上走。头两天我走着走着就迷路了，向许多人问路才回到家，被问的人知道我英文不好，都微笑着慢慢讲。
那段时间内伦敦确实给了我非常良好的印象，超市里面的食物之多让我兴奋不已，超市外面有人在卖一种叫Biglssue的杂志，它是专为无家可归的人和失业者办的，售价一英镑，卖它的人每份可以得到45便士。租录像带的商店里有我想看而在中国找不到的全部电影，就是在公共汽车上和地铁里，也像是在看电影一样，有那么多酒鬼、疯子，打扮很酷的年轻人和穿西装的白领上班族并排坐在一起，这一切让我觉得伦敦是一个色彩丰富、充满机会的城市，对于前面未知的生活，我不再感到担心。
我住的地区叫King’Gross，是伦敦有名的红灯区，街上电话亭里贴满了妓女的照片，我把它们都摘了下来，贴在我练琴房间的墙上当做装饰品。
2008年6月22日星期日
2008年6月1日星期日
订阅：
博文 (Atom)