Author Topic: 每周一题: 砖块延伸 (3/28/05 -- 4/3/05)  (Read 40211 times)

万精油

  • Administrator
  • Hero Member
  • *****
  • Posts: 1831
每周一题: 砖块延伸 (3/28/05 -- 4/3/05)
« on: 三月 27, 2005, 11:00:11 pm »
这两周我们这个论坛不象以前那么热闹了。为提高大家的积极性,我上周出了两道比较容易的概率题。通常概率题都会引起很多讨论。结果参加者仍然不是太多。我想或许应该再变一些花样,於是这周的题就完全变了味,带点物理题的性质。这道题虽然不是太难,但我从来认为这种由现实生活中产生的题趣味性是要加倍的。

当然,一个论坛也不能完全靠容易的题目支撑着。事实上,稍微难一点的题对论坛的兴旺更重要。因为容易的题一个回贴就完全解决,那条线也就给封了。而难题就可以有很多讨论的余地。说到这里我就想提一提对难题的态度问题。绝大多数到这里来的人都是在工作之余想来活动一下脑筋,并不想花大量的时间(想也不一定有)来攻克难题。所以,许多人看见难题,想几分钟没有结果就放弃了。我想要说的是在想不出解答与放弃之间还有第三种选择。我个人的态度是:对太容易的题我就想一想有没有推论,如果有什么想法就跟出来。对于难题,我想到什么也是马上就贴出来。这样经常有想错的时候,但没有关系,关键是不能让一个好题死在那里。而且,一个人的错误想法或许会给另一个人一些提示而得到正确想法。比如这里曾经有一道关于不能用不同的小立方体填满一个大立方体的问题。我的答案是错误的,但其提到的想法后来被FZY用来得出正确结果。我有时甚至明知是错误的想法我也把它贴出来,一方面因为我没有找到正确的解法,另一方面也是希望我的错误想法或许会给别人一些提示。其实有时再坚持一下正确解法就出来了,但我知道几天之内我不会有整体时间来想这个问题,不如把想到的东西贴出来让别人接着想。这就是我说的第三种选择。许多难题在大家你一言我一语中就解决了。研究机构里的讨论班就是用的这种思想。大家不要怕出错误,想到什么就贴什么,没有人会在这里给人打分:)。如果对一道难题一定要想得天衣无缝才贴出来,那么那条线可能很久都不会有跟贴,也就默默死掉。上星期FZY贴出的多边形问题是一道很有意思的题。虽然我没有完全解决,但已经跟了两贴,主要是不想让这么一道有意思的贴死在那里。


本周问题:砖块延伸

把一个砖块错开一点放在另一个砖块上,只要错开不超过一半,上面伸出来的那块砖就不会掉下来。现在假设你有无数多的4X8寸的砖,你能不能使上面的砖从第一块砖边缘伸出8寸远?当然我们假设砖都是均匀分布的,而且只受重力作用。如果能,能不能伸更远?最远能伸多远?

上周问题讨论

上周问题第一题比较简单,很有实用价值。平均需要买11。42盒才能凑齐五张卡片。第一盒买到一张。要买第二个不同的卡片,概率是4/5,所以需要5/4盒,要买第三个不同的卡片,概率是3/5,所以需要5/3。依此类推。一般来说,如果有N张不同的卡片,则需要n*(1+1/2+1/3+。。。1/n)。调和级数可以用欧拉数写成

ln(n) + 1/2n + 0.57721.

所以N张卡片需要

n*ln(n)+0.577n+1/2

当N=5时,我们得到11.43。与真正的值很接近。

第二道题可以有好几种不同的解法(参看上周问题连接)。对一般的N,两个朋友相遇的概率是1/2∧(N-1)。

七把叉

  • Jr. Member
  • **
  • Posts: 27
    • http://www.sevenforks.com
    • Email
Re: 每周一题: 砖块延伸 (3/28/05 -- 4/3/05)
« Reply #1 on: 三月 28, 2005, 12:36:36 pm »
Quote from: 万精油

把一个砖块错开一点放在另一个砖块上,只要错开不超过一半,上面伸出来的那块砖就不会掉下来。现在假设你有无数多的4X8寸的砖,你能不能使上面的砖从第一块砖边缘伸出8寸远?当然我们假设砖都是均匀分布的,而且只受重力作用。如果能,能不能伸更远?最远能伸多远?


上面三问的答案是:能;能;无穷远。

fzy

  • Hero Member
  • *****
  • Posts: 520
Re: 每周一题: 砖块延伸 (3/28/05 -- 4/3/05)
« Reply #2 on: 三月 28, 2005, 02:02:58 pm »
Quote from: 万精油
当然,一个论坛也不能完全靠容易的题目支撑着。事实上,稍微难一点的题对论坛的兴旺更重要。因为容易的题一个回贴就完全解决,那条线也就给封了。而难题就可以有很多讨论的余地。说到这里我就想提一提对难题的态度问题。绝大多数到这里来的人都是在工作之余想来活动一下脑筋,并不想花大量的时间(想也不一定有)来攻克难题。所以,许多人看见难题,想几分钟没有结果就放弃了。我想要说的是在想不出解答与放弃之间还有第三种选择。我个人的态度是:对太容易的题我就想一想有没有推论,如果有什么想法就跟出来。对于难题,我想到什么也是马上就贴出来。这样经常有想错的时候,但没有关系,关键是不能让一个好题死在那里。而且,一个人的错误想法或许会给另一个人一些提示而得到正确想法。比如这里曾经有一道关于不能用不同的小立方体填满一个大立方体的问题。我的答案是错误的,但其提到的想法后来被FZY用来得出正确结果。我有时甚至明知是错误的想法我也把它贴出来,一方面因为我没有找到正确的解法,另一方面也是希望我的错误想法或许会给别人一些提示。其实有时再坚持一下正确解法就出来了,但我知道几天之内我不会有整体时间来想这个问题,不如把想到的东西贴出来让别人接着想。这就是我说的第三种选择。许多难题在大家你一言我一语中就解决了。研究机构里的讨论班就是用的这种思想。大家不要怕出错误,想到什么就贴什么,没有人会在这里给人打分:)。如果对一道难题一定要想得天衣无缝才贴出来,那么那条线可能很久都不会有跟贴,也就默默死掉。上星期FZY贴出的多边形问题是一道很有意思的题。虽然我没有完全解决,但已经跟了两贴,主要是不想让这么一道有意思的贴死在那里。


I totally agree with the professor.

Recently I was very reluctant to post because I noticed that I passed I94 and became the second most frequent poster, only behind the professor.  :cry:  I suggest everybody who visit and like the site, post something once in a while, even just to announce you are alive and well. I also suggest Sir I94 to post more often so I have some company and feel better.  :lol:  Even just joking around is cool.

To joke around, I start with the following:

A mathematician applies to be a volunteer fire fighter. He needs to answer two questions:

1. "What do you do when you see a dumpster on fire?" "Easy," the mathematician said. "I put water on the dumpster and extinguish the fire."

2. "What do you do when you see a dumpster NOT on fire?" "This is even easier," the mathematician said. "I set it on fire and it is reduced to the first case."

sean

  • Jr. Member
  • **
  • Posts: 86
每周一题: 砖块延伸 (3/28/05 -- 4/3/05)
« Reply #3 on: 三月 28, 2005, 05:15:45 pm »
这题目确实很有意思。小时候我们下完象棋后,经常用象棋子堆高楼。最下面一子,第二层两子,依次类推,能堆很高。

我也曾经发过最高数量的贴呢。 :lol:  最近不怎么来了。主要是因为忙。其次是因为题目经常太难了,一时半会想不出来(有的是永远也想不出来)。

zzzzzzzzzz

  • Guest
每周一题: 砖块延伸 (3/28/05 -- 4/3/05)
« Reply #4 on: 三月 28, 2005, 05:56:30 pm »
Two principles are useful in solving this problem.  1. The brick(s) will fall off if its/their center of gravity is beyond the edge of the brick immediately below it/them.  2. A bunch of bricks, regardless of how they are stacked, is equivalent to their total mass concentrated at their center of gravity, which is one mathematical point in space.  So for a bunch of bricks in fully extended and stable position, the center of gravity of top n bricks is right on top of the front edge of the n+1st brick.

Assume each brick has length 1 for simplicity (it can be changed to actual length later).

If there are only two bricks, only half of the top brick can extend beyond the edge of the bottom brick.

With 3 bricks, the center of gravity of top two bricks is ((1/2 * 1) + (1 * 1))/2 = 3/4, which means the second brick will extend 1-3/4 = 1/4 beyond the edge of the bottom brick, and total extension is 1/2 + 1/4 = 3/4.

With 4 bricks, center of gravity of top 3 bricks is at ((1/2 * 1) + (2 * 1))/3 = 5/6, so the 3rd brick will extend 1/6 beyond the edge of the bottom brick, for a total of 1/6 + 3/4 = 11/12.

In summary, if there are n bricks in the fully extended position, adding one brick on the bottom will add to the extension by the amount the n bricks can extend beyond the newest brick.  That amount is: 1 - (1/2 + n)/(n+1) = 1/(2(n+1)), and the total distance that can extend is sigma(1/2(k+1)), for k = 1 to n.

Since the series 1/n does not converge, as long as you have enough bricks, you can extend the whole stack as far beyond the edge of the bottom brick as you want.

七把叉

  • Jr. Member
  • **
  • Posts: 27
    • http://www.sevenforks.com
    • Email
每周一题: 砖块延伸 (3/28/05 -- 4/3/05)
« Reply #5 on: 三月 28, 2005, 11:33:25 pm »
楼上游客的解答完全正确。

先把N块砖不错开地整齐地往上码,然后从上面开始往外错开。最上面第一块可错开一半。

第二块如果错开x,则第一块的重心外移x,两块砖的重心得落在第三块的边缘上,则1*x=1*(1/2-x),x=1/4。

第n+1块砖错开x,则上面n块砖的重心外移x,则nx=1*(1/2-x),x=1/2(n+1)。

现在,我想请大家再想想是否有另外的解法。我有一个非常妙的解法,是用反证法。先假设伸出去的距离有限,即有个最大值,然后证明在这假定的最大距离上还能增加一段距离。有兴趣的朋友可以想一下。

七把叉

  • Jr. Member
  • **
  • Posts: 27
    • http://www.sevenforks.com
    • Email
每周一题: 砖块延伸 (3/28/05 -- 4/3/05)
« Reply #6 on: 四月 01, 2005, 12:42:08 pm »
现在我来说一下我的另一个解法:

假设伸出去的距离有限,那么,或者有一种堆法使砖伸出去最远,或者有一种堆法使砖伸出去的距离与上限只差任意小的值。

不失一般性,我们假设找到一种堆法,砖伸出的距离与上限只差0.01(假设砖长为1)。

如果我们把这堆砖成比例加倍,比如把原来的每块砖变成十块(反正万教授已烧制了无数块砖),那么这堆砖还是不会倒的。这相当于成比例增加了每块砖的厚度,与原来那堆砖等价。

那好,我们就把每块砖变成两块。

把最上面的两块砖往里推0.11,然后把最上面的一块往外推0.22(小于0.5),这时这堆砖的重心显然还是稳的。现在伸出去的距离比原来增加了0.11,减去0.01,比上限值大了0.1。

这个反证法是不是很妙?我是自己想出来的,不知有谁见过类似的解法。

万精油

  • Administrator
  • Hero Member
  • *****
  • Posts: 1831
每周一题: 砖块延伸 (3/28/05 -- 4/3/05)
« Reply #7 on: 四月 01, 2005, 01:51:28 pm »
According to earlier posts, the nth brick will extend out 1/(2*n), which is getting smaller and smaller (the sum will go to infinite of course). By your new approach, if I split the top brick into two (thus, going from n brick to n+1 brick), I can always extend it 0.11 out. This is much bigger than 1/2*n, what happened?


Note: I know my above argument is wrong, I just want to see if people can find out where did I go wrong? (hint: physics)

fzy

  • Hero Member
  • *****
  • Posts: 520
每周一题: 砖块延伸 (3/28/05 -- 4/3/05)
« Reply #8 on: 四月 01, 2005, 02:49:30 pm »
There is a problem with the new proof. You assumed that the upper most brick is at the same time out most. If it is in the middle, you cannot push it out.

For the professor's question, because the number of bricks is doubled, the maximum extension is increased by ln 2 = 0.6931, which is bigger than 0.11. Even bigger than 0.25, the miximum gain that can be obtained this way.

万精油

  • Administrator
  • Hero Member
  • *****
  • Posts: 1831
每周一题: 砖块延伸 (3/28/05 -- 4/3/05)
« Reply #9 on: 四月 01, 2005, 03:06:33 pm »
Quote
because the number of bricks is doubled, the maximum extension is increased by ln 2 = 0.3937, which is bigger than 0.11. Even bigger than 0.25, the miximum gain that can be obtained this way.


You are avoiding my question :), I didn't double the bricks. I only split the top one into two, thus, going from n to n+1, not from n to 2*n. :D

七把叉

  • Jr. Member
  • **
  • Posts: 27
    • http://www.sevenforks.com
    • Email
每周一题: 砖块延伸 (3/28/05 -- 4/3/05)
« Reply #10 on: 四月 01, 2005, 03:34:58 pm »
Quote from: fzy
There is a problem with the new proof. You assumed that the upper most brick is at the same time out most. If it is in the middle, you cannot push it out.


这个问题提得很好,我确实没考虑伸出最远的砖在中间的情况。但这个解法还是成立的,只是得补充一下:

由于只受重力,因此一堆砖如果不是从下到上单调往外伸的话,我们可以将它重新排序成单调外伸,这样的话重心没变,还是稳定的,且与原来的砖堆等价。

七把叉

  • Jr. Member
  • **
  • Posts: 27
    • http://www.sevenforks.com
    • Email
每周一题: 砖块延伸 (3/28/05 -- 4/3/05)
« Reply #11 on: 四月 01, 2005, 03:43:31 pm »
有了,现在我修改一下原来的解法,不必假设伸出最远的那块砖在最顶上:

假设伸出去的距离有限,那么,或者有一种堆法使砖伸出去最远,或者有一种堆法使砖伸出去的距离与上限只差任意小的值。

不失一般性,我们假设找到一种堆法,砖伸出的距离与上限只差0.01(假设砖长为1)。

如果我们把这堆砖成比例加倍,比如把原来的每块砖变成十块(反正万教授已烧制了无数块砖),那么这堆砖还是不会倒的。这相当于成比例增加了每块砖的厚度,与原来那堆砖等价。

那好,我们就把每块砖变成四块。

原来那堆砖里伸得最远的那块现在变成了四块。把这四块的中间两块砖往里推0.11,然后把被推进去的两块砖的任意一块往外推0.22(小于0.5),这时这堆砖的重心显然还是稳的。现在伸出去的距离比原来增加了0.11,减去0.01,比上限值大了0.1。

七把叉

  • Jr. Member
  • **
  • Posts: 27
    • http://www.sevenforks.com
    • Email
每周一题: 砖块延伸 (3/28/05 -- 4/3/05)
« Reply #12 on: 四月 01, 2005, 03:55:30 pm »
好事多磨,还得修改一下。如果先往里推,再往外推,很可能还没等往外推,砖堆已经倒了。因此得改成同时推:

假设伸出去的距离有限,那么,或者有一种堆法使砖伸出去最远,或者有一种堆法使砖伸出去的距离与上限只差任意小的值。

不失一般性,我们假设找到一种堆法,砖伸出的距离与上限只差0.01(假设砖长为1)。

如果我们把这堆砖成比例加倍,比如把原来的每块砖变成十块(反正万教授已烧制了无数块砖),那么这堆砖还是不会倒的。这相当于成比例增加了每块砖的厚度,与原来那堆砖等价。

那好,我们就把每块砖变成四块。

原来那堆砖里伸得最远的那块现在变成了四块。把这四块的中间两块砖,其中一块往里推,同时另一块往外推,推相同的一小段距离,比如0.11,这时这堆砖的重心显然还是稳的。现在伸出去的距离比原来增加了0.11,减去0.01,比上限值大了0.1。

七把叉

  • Jr. Member
  • **
  • Posts: 27
    • http://www.sevenforks.com
    • Email
每周一题: 砖块延伸 (3/28/05 -- 4/3/05)
« Reply #13 on: 四月 01, 2005, 04:05:47 pm »
Quote from: 万精油
According to earlier posts, the nth brick will extend out 1/(2*n), which is getting smaller and smaller (the sum will go to infinite of course). By your new approach, if I split the top brick into two (thus, going from n brick to n+1 brick), I can always extend it 0.11 out. This is much bigger than 1/2*n, what happened?

Note: I know my above argument is wrong, I just want to see if people can find out where did I go wrong? (hint: physics)


这么退一步进两步的堆法是可以的,但效率其实很差。我们来计算一下:

最大幅度可退1/4,进1/2,因此每次伸出1/4。1块砖可伸出1/2,2块3/4,4块1,...2^n块可伸出(n+2)/4。

如果我们用1024块砖,2^10,可伸出去3倍砖长。

再来看看前面1/2n的堆法:

1024块砖可伸出的距离是1/2(10*ln2+1/2^11+0.57721)=3.75。

如果用更多的砖,差距更大:

2^22块砖,用前法可伸出6倍砖长。而用后法可伸出7.9。

这还是个数学问题,我没看出与物理有关。

七把叉

  • Jr. Member
  • **
  • Posts: 27
    • http://www.sevenforks.com
    • Email
每周一题: 砖块延伸 (3/28/05 -- 4/3/05)
« Reply #14 on: 四月 01, 2005, 05:01:13 pm »
这道题确实很有意思的,值得继续讨论下去。我的反证法是否正确,还有没有漏洞,请大家再给看看。万教授也还没最后表态。但至少有一点,刚才的讨论,又带出另一个解法,与那个1/2n解法一样,都是构造法。

完整表述一下,这个解法是:

一堆砖,最上面一块伸出1/2,第二块伸出1/4,接下来两块并一起伸出1/4,再下面4块一起伸出1/4,再8块、16块、...2^n块均依次伸出1/4。这样由于有无数块砖,因此可伸出无穷远。

前面我也计算了,这两种堆法的效率是不同的。这种堆法效率差很多。

现在我想提个问题,那个1/2n的堆法是不是效率最高的一种堆法?即伸出一个指定的有限距离,所需砖块最少。或者说,使用指定数量的砖,伸出距离最远。如果是,请给出证明。如果不是,那么有没有效率最高的堆法?什么方法?