Author Topic: 每周一题: 圆环问题 (12/13/04 -- 12/19/04)  (Read 14815 times)

万精油

  • Administrator
  • Hero Member
  • *****
  • Posts: 1831
每周一题: 圆环问题 (12/13/04 -- 12/19/04)
« on: 十二月 13, 2004, 09:51:27 am »
上周的题目,一方面因为太难,一方面因为太有趣,一周之内阅读数超过600,跟贴数超过50。这在这个论坛还是没有过的事。

上周问题讨论

这道题在那条线上有好几种解法,我这里只是总结一下。

1.首先要证明如果命题不成立,则所有人的朋友数相同。要证明这一点,先考虑两个不是朋友的人A,B的朋友数。A的每一个朋友AI与B有一个共同朋友BI。很容易发现,如果A,B不认识,对于不同的AI,BI也不同,因为任意两个AI只能有一个共同的朋友A。而A不是B的朋友。所以,B的朋友数一定大于等于A的朋友数,反之亦然。所以如果A,B不认识,A,B的朋友数相同。另外我们还可以证明如果A,B是朋友,则一定有一人(C)不是A,B的朋友。那么A的朋友数等于C的朋友数,又等于B的朋友数。而且,很容易证明,对于每个人而言,他的朋友都是成对的,成扇形张开在他周围。

2.如果共同朋友数为K,则对任意一个人而言,他有K个朋友,他的K个朋友每人有K个朋友,这些朋友只有A被重复K次,其于的朋友都不能相同。而且,这些朋友包括所有人,因为任何人都在两步以内(因为任意两个人都有一个共同朋友)。所以,N=K★(K-1)+1。

剩下的就是要证明这个K=2。

因为朋友都是成对的,所以K是偶数。K-1是奇数,所以K-1有一个奇数的素数因子P。现在来考虑由P个人组成的环{V1,V2,V3,...VP}。V1是V2的朋友,V2是V3的朋友,...,V(P-1)是VP的朋友,VP是V1的朋友。我们把所有这种P环组成的集合称为SP。很显然,SP里的项数能被P整除,因为对于每一个{V1,V2,V3,...VP},不同的起点对应于不同的元素。现在我们再来证明SP的项数不能被P整除。注意,我们并不要求这些V是不同的人,只要前后是朋友关系能构成一个环就行。

要证明|SP|不能被P整除,我们需要从另一个角度来考虑SP。先来考虑由P-1个人组成的链{V1,V2,V3,...V(P-1)}。V1是V2的朋友,V2是V3的朋友,...,V(P-2)是V(P-1)的朋友。我们把这种链组成的集合叫L。显然,L的个数是N★K^(P-1)。因为链的第一点有N种选择,以后的每点有K种选择。从另一个角度来看L,L中的链分两种,一种是V(P-1)等于V1,另一种是V(P-1)不等于V1。我们把它们分别叫做L1和L2。每一个SP中的环都可以从L中的链加一个人得到。对于L1中的链,有K种方法加这个人。对于L2中的链,因为V(P-1)与V1只能有一个共同朋友,所以只能有一种加法。所以我们有

|SP|  =  K★L1+L2  =  (K-1)★L1+L1+L2
          =  (K-1)★L1+N★K^(P-1)。

因为N与K除K-1都余1,所以上面的第二项不能被P整除。所以|SP|不能被P整除,这与我们前面的结果矛盾。命题得证。

另外一种方法是考虑连接矩阵,然后用特征值来证明K=2。具体细节可参看WARREN的贴子。

上周的题目太难,我们这周来几个容易的。对于那些想找面试题的读者,这几道题应该可以算得上很好的面试题。

本周问题:与圆环有关的几个问题

1.一个金属环被加热后,其内径是增大还是缩小?
2.假如你骑自行车上班。问你前轮走的远还是后能走的远?
3.能否把三个圆环套在一起使得任意取掉一个其它两个也自然脱离?
4.一个圆球被一个圆柱从正中打通。剩下的部分成一个环形。已知这个环形的高是6厘米,求这个环形的体积。
« Last Edit: 十月 08, 2009, 09:37:07 pm by 万精油 »

fzy

  • Hero Member
  • *****
  • Posts: 520
Re: 每周一题: 圆环问题 (12/13/04 -- 12/19/04)
« Reply #1 on: 十二月 13, 2004, 10:45:55 am »
Quote from: 万精油
3.能否把三个圆环套在一起使得任意取掉一个其它两个也自然脱离?


This is interesting. Yes if they are soft. A representation is three ellipses, one on the xy plane as x^2 + y^2 / 4 = 1, one on yz plane as y^2 + z^2 / 4 = 1, one on the xz plane as z^2 + x^2 / 4 = 1.

packman

  • Full Member
  • ***
  • Posts: 226
Re: 每周一题: 圆环问题 (12/13/04 -- 12/19/04)
« Reply #2 on: 十二月 13, 2004, 11:16:02 am »
1.一个金属环被加热后,其内径是增大还是缩小?
shrink?

2.假如你骑自行车上班。问你前轮走的远还是后能走的远?
front wheel?


4.一个圆球被一个圆柱从正中打通。剩下的部分成一个环形。已知这个环形的高是6厘米,求这个环形的体积。
Seems like a constant. If so, the answer should be equal to the volume of a ball with 6 cm of diameter.
简单==完美

warren

  • Full Member
  • ***
  • Posts: 148
每周一题: 圆环问题 (12/13/04 -- 12/19/04)
« Reply #3 on: 十二月 13, 2004, 01:21:17 pm »
1.一个金属环被加热后,其内径是增大还是缩小?
增大. 内径,外径,高度,厚度成比例增大.

2.假如你骑自行车上班。问你前轮走的远还是后能走的远?
前轮. 因为前轮走的弯路多.

4.一个圆球被一个圆柱从正中打通。剩下的部分成一个环形。已知这个环形的高是6厘米,求这个环形的体积。
36*pi cm^3

万精油

  • Administrator
  • Hero Member
  • *****
  • Posts: 1831
每周一题: 圆环问题 (12/13/04 -- 12/19/04)
« Reply #4 on: 十二月 13, 2004, 04:44:15 pm »
Quote
This is interesting. Yes if they are soft. A representation is three ellipses, one on the xy plane as x^2 + y^2 / 4 = 1, one on yz plane as y^2 + z^2 / 4 = 1, one on the xz plane as z^2 + x^2 / 4 = 1.


Here's a page with similar set up.

http://members.aol.com/mensanator/borromean_paper_clips.htm

I have seen a page where 3 real ring are hooked together like this, but can't find the page now.

visitor

  • Guest
每周一题: 圆环问题 (12/13/04 -- 12/19/04)
« Reply #5 on: 十二月 13, 2004, 09:44:55 pm »
2. Same, as long as you do not use the brake. The reason is that both have the same size and turn the same number of rounds. But, if you use brake, the rear wheel does not turn and the front still turns. Everybody uses brake. So, in general, the front wheel runs more.

visitor

  • Guest
每周一题: 圆环问题 (12/13/04 -- 12/19/04)
« Reply #6 on: 十二月 13, 2004, 10:36:24 pm »
4. Agree with warren.
V = 2 integral [from 0 to 3] pi*((R^2-y^2)-(R^2-3^2))dy
  = 2*pi integral [0, 3] (9-y^2)dy = 36*pi.

万精油

  • Administrator
  • Hero Member
  • *****
  • Posts: 1831
每周一题: 圆环问题 (12/13/04 -- 12/19/04)
« Reply #7 on: 十二月 14, 2004, 10:01:35 am »
Quote
2. Same, as long as you do not use the brake. The reason is that both have the same size and turn the same number of rounds. But, if you use brake, the rear wheel does not turn and the front still turns. Everybody uses brake. So, in general, the front wheel runs more.


Are you sure about this? Think about what happens when you make a turn?

fzy

  • Hero Member
  • *****
  • Posts: 520
每周一题: 圆环问题 (12/13/04 -- 12/19/04)
« Reply #8 on: 十二月 14, 2004, 10:11:17 am »
1.一个金属环被加热后,其内径是增大还是缩小?

If you ever worked in a factory you know it expands. That is how we put on ball barings.

2.假如你骑自行车上班。问你前轮走的远还是后能走的远?

If you go straight (no turns), it is the same. When you turn, the front wheel thavels a larger circle. This is true even if you go backwards.

3.能否把三个圆环套在一起使得任意取掉一个其它两个也自然脱离?

Another way is the way we string up rubber bands. It lookes like the two ways are topologically unequivalent, but I do not know how to prove it. The advantage of this way is that it applies to any number of rings, not just three.

4.一个圆球被一个圆柱从正中打通。剩下的部分成一个环形。已知这个环形的高是6厘米,求这个环形的体积。

It is easy to see the ring has the same volume as a solid ball by comparing the areas of their cross sections.

visitor

  • Guest
每周一题: 圆环问题 (12/13/04 -- 12/19/04)
« Reply #9 on: 十二月 14, 2004, 10:59:55 pm »
Quote from: 万精油
Are you sure about this? Think about what happens when you make a turn?


I am not quite sure what do you mean. My statement: "both have the same size and turn the same number of rounds." is not correct or even the statement is correct the conclusion is not right.

First I believe my statement is correct. Otherwise you will fill some tumbling.

If the statement is correct. Think it in other way. Suppose there are two industry length measure ( a wheel and the rounds will be countered when walking), they have the same size and roll over the same rounds, what is the result?

For the tuning, I think, you see different circle, because the front wheel and rear wheel start the turning from the different places.

Do you have some real experiment to prove that when turning, the rear wheel is rotating but not moving?

万精油

  • Administrator
  • Hero Member
  • *****
  • Posts: 1831
每周一题: 圆环问题 (12/13/04 -- 12/19/04)
« Reply #10 on: 十二月 15, 2004, 09:44:43 am »
Quote
First I believe my statement is correct. Otherwise you will fill some tumbling.


Your statement is wrong. The front wheel and back wheel don't turn the same number of rounds. Here's an experiment you can do. Stand by the side of a bike, put one hand on the seat, put another hand on the steering handle, make a big circle with the front wheel while the back wheel stays almost in the same spot. No breaks involved. This is the extream case. Generally, when you bike on the road, as soon as your front wheel makes a turn, the back wheel will start to have velocity on the turning direction, and short cut the route.