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

七把叉

  • Jr. Member
  • **
  • Posts: 27
    • http://www.sevenforks.com
    • Email
每周一题: 砖块延伸 (3/28/05 -- 4/3/05)
« Reply #15 on: 四月 01, 2005, 05:43:58 pm »
Quote from: 七把叉
现在我想提个问题,那个1/2n的堆法是不是效率最高的一种堆法?即伸出一个指定的有限距离,所需砖块最少。或者说,使用指定数量的砖,伸出距离最远。如果是,请给出证明。如果不是,那么有没有效率最高的堆法?什么方法?


这个问题问得多余了,见笑。

其实从构造的方法来看,由于n*x=1*(1/2-x),这说明对于任意一块砖来说,它上面所有砖块的重心都恰好落在这块砖的边缘,可见得效率是最高的。

而在2^n堆法中,从上往下,1、2、4、8、...、2^n块砖的重心均落在下面那块砖的边缘,但是3、5、7、9、...只要不是2^n块砖,重心就落在下面那块砖里面。因此效率不高。

fzy

  • Hero Member
  • *****
  • Posts: 520
每周一题: 砖块延伸 (3/28/05 -- 4/3/05)
« Reply #16 on: 四月 01, 2005, 06:06:17 pm »
Quote
我的反证法是否正确,还有没有漏洞,请大家再给看看。


The proof by contradiction can be fixed. But you have not fixed it yet. :wink: It is actually very easy to fix: Instead considering the maximum extend of all constructions, consider the maximum entends of all monotone constructions. No changes for the rest.

Quote
那个1/2n的堆法是不是效率最高的一种堆法?


It looke like is. But your proof does not look good enough. You proved it is "locally optimal", but have not proved it is globally optimal.  :( [/quote]

七把叉

  • Jr. Member
  • **
  • Posts: 27
    • http://www.sevenforks.com
    • Email
每周一题: 砖块延伸 (3/28/05 -- 4/3/05)
« Reply #17 on: 四月 01, 2005, 06:15:28 pm »
如果我们试着用这方法造一座跨度为100米的桥,不考虑载重,只要能负担自重。假设用长度为10米的钢板从岸两边往中间架,那么每边各需12400块钢板。如果钢板厚1厘米,那桥高有124米。

费这么多钢板,可还走不了人过不了车。你要是走到桥中间,就掉河里去了。

七把叉

  • Jr. Member
  • **
  • Posts: 27
    • http://www.sevenforks.com
    • Email
每周一题: 砖块延伸 (3/28/05 -- 4/3/05)
« Reply #18 on: 四月 01, 2005, 06:32:36 pm »
Quote from: fzy

The proof by contradiction can be fixed. But you have not fixed it yet. :wink: It is actually very easy to fix: Instead considering the maximum extend of all constructions, consider the maximum entends of all monotone constructions. No changes for the rest.


有道理。如果有极值,那么对单调的堆法自然也有极值,因此如推出矛盾,同样得证。我最初的证明就是只考虑单调情况,因此解是对的。但是由于我当时没考虑到不单调的情况,因此不能算全对。谢谢fzy指教。

差不多

  • Newbie
  • *
  • Posts: 10
每周一题: 砖块延伸 (3/28/05 -- 4/3/05)
« Reply #19 on: 四月 01, 2005, 09:56:13 pm »
哪用这么费劲啊,不就是堆砖头么,
如下,把〓〓看成一块砖:

〓〓〓〓〓〓〓〓〓〓 
 〓〓〓〓〓〓〓〓
  〓〓〓〓〓〓
   〓〓〓〓
    〓〓

每层多用一块,(单向)多伸出去半块,所以要伸出去10块只要20层,用砖210块!这差不多是最省的了吧?

难怪当年《决裂》里俺们老农民一举长满老茧的手:这就是资格啊! :lol:  :lol:
就行了

warren

  • Full Member
  • ***
  • Posts: 148
每周一题: 砖块延伸 (3/28/05 -- 4/3/05)
« Reply #20 on: 四月 02, 2005, 01:10:49 am »
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)


That is because of the top 2 bricks are thiner and lighter than other bricks.

warren

  • Full Member
  • ***
  • Posts: 148
每周一题: 砖块延伸 (3/28/05 -- 4/3/05)
« Reply #21 on: 四月 02, 2005, 01:15:11 am »
Quote from: 差不多
哪用这么费劲啊,不就是堆砖头么,
如下,把〓〓看成一块砖:

〓〓〓〓〓〓〓〓〓〓 
 〓〓〓〓〓〓〓〓
  〓〓〓〓〓〓
   〓〓〓〓
    〓〓

每层多用一块,(单向)多伸出去半块,所以要伸出去10块只要20层,用砖210块!这差不多是最省的了吧?

难怪当年《决裂》里俺们老农民一举长满老茧的手:这就是资格啊! :lol:  :lol:


你的这个思路很好, 但是你的结构是不稳定的, 会跨掉.

差不多

  • Newbie
  • *
  • Posts: 10
每周一题: 砖块延伸 (3/28/05 -- 4/3/05)
« Reply #22 on: 四月 02, 2005, 07:41:47 am »
Quote from: warren
Quote from: 差不多
哪用这么费劲啊,不就是堆砖头么,
如下,把〓〓看成一块砖:

〓〓〓〓〓〓〓〓〓〓 
 〓〓〓〓〓〓〓〓
  〓〓〓〓〓〓
   〓〓〓〓
    〓〓

每层多用一块,(单向)多伸出去半块,所以要伸出去10块只要20层,用砖210块!这差不多是最省的了吧?

难怪当年《决裂》里俺们老农民一举长满老茧的手:这就是资格啊! :lol:  :lol:


你的这个思路很好, 但是你的结构是不稳定的, 会跨掉.


:oops: 大学还是没上成,补考:
    〓〓
   〓〓〓〓
  〓〓〓〓〓〓
 〓〓〓〓〓〓〓〓
〓〓〓〓〓〓〓〓〓〓 
 〓〓〓〓〓〓〓〓
  〓〓〓〓〓〓
   〓〓〓〓
    〓〓

这回真差不多了吧,要伸出去N块砖距用砖(2N)^2块。
就行了

zzzzzzzzzz

  • Guest
每周一题: 砖块延伸 (3/28/05 -- 4/3/05)
« Reply #23 on: 四月 02, 2005, 01:07:12 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)


Not sure if I understood your question correctly, 1/2n applies to the bricks on the bottom.  The top brick can always extend out 0.5 > 0.11.

七把叉

  • Jr. Member
  • **
  • Posts: 27
    • http://www.sevenforks.com
    • Email
每周一题: 砖块延伸 (3/28/05 -- 4/3/05)
« Reply #24 on: 四月 03, 2005, 09:49:14 am »
Quote from: 差不多


:oops: 大学还是没上成,补考:
    〓〓
   〓〓〓〓
  〓〓〓〓〓〓
 〓〓〓〓〓〓〓〓
〓〓〓〓〓〓〓〓〓〓 
 〓〓〓〓〓〓〓〓
  〓〓〓〓〓〓
   〓〓〓〓
    〓〓

这回真差不多了吧,要伸出去N块砖距用砖(2N)^2块。


哈哈,倒是没想到还能这么堆。

现在我只能说,如果仅限每层一块砖,1/2n的效率最高。虽然我也给不出严格证明。

physics

  • Guest
每周一题: 砖块延伸 (3/28/05 -- 4/3/05)
« Reply #25 on: 四月 07, 2005, 06:28:34 pm »
the method by z^10 gives the optimal result.
It can be showed in the following way.
If for any given n bricks, sum (1/2*n) is the best result, then ok.

Otherwise, suppose for some m,
the result can be greater than sum (1/2*m)
so there must exist some k<m, such that
for any numbers less than k,
the extension is not greater than sum (1/2*a), for 1<=a<=k

while for k+1 bricks, it is greater than sum 1/2*(k+1)

We know it is impossible. To show it is impossible.

For the (k+1)th brick
it should satisfy two conditions,
1st, its extension relative to the first brick is greater than sum(1/2*(k+1)),
2nd, its relative extension to the second brick should be not greater than sum(1/2*k),
but it is impossible according z^10's method of calculating center of mass.

万精油

  • Administrator
  • Hero Member
  • *****
  • Posts: 1831
每周一题: 砖块延伸 (3/28/05 -- 4/3/05)
« Reply #26 on: 四月 08, 2005, 11:15:17 pm »
Check out the following link, it can be used as the title picture of this thread. :)

http://web.wenxuecity.com/BBSView.php?SubID=joke&MsgID=91152

万精油

  • Administrator
  • Hero Member
  • *****
  • Posts: 1831
Re: 每周一题: 砖块延伸 (3/28/05 -- 4/3/05)
« Reply #27 on: 九月 06, 2011, 03:54:05 pm »
今天看见两张图,觉得与这道题有关,贴在这里。