注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

一路

To find the final symmetry & beauty

 
 
 

日志

 
 
 
 

TWO demonstration of using technique of basic building blocks to prove the whole[origin]  

2012-04-19 17:46:42|  分类: 学习笔记 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
Problems:
1. A square lattice that of size n*n while n is an even number. Now, we cut two small unit rectangle out on one diagonal's both end. 
The following picture shows this circumstance. The problem now is that if we have infinit small rectangle bar composed by two unit square, could we use these small rectangle to cover the whole lattice precisely. If it it true,show how, if false,show why.
TWO demonstration of using technique of basic building blocks to prove the whole[origin] - saturnman - 一路
figure 1:lattice square
TWO demonstration of using technique of basic building blocks to prove the whole[origin] - saturnman - 一路
 figure2: basic building block formed by two unit square
Considering this problem directly, it is hard to know how to use the condition provided such as n is an even number. We can transform this problem into the following one by coloring the lattice square.
TWO demonstration of using technique of basic building blocks to prove the whole[origin] - saturnman - 一路
 In the above graph we can easily see that white is not adjacent to black square and conversely it is also true. So if we try to use the small block to cover this lattice,  easy time we could cover one black with one white square.  As there are more white square than black square, certainly we can't make the full cover, solving this problem by using this technique is very easy :-).
 
2. We also have one n*n lattice, now n is power of 2. Now we have L shape block composed by three unit square lattice. If we could use these L shape blocks to cover the whole lattice only left one uncovered.
TWO demonstration of using technique of basic building blocks to prove the whole[origin] - saturnman - 一路

 when n equals to 4 we have solution like the following one.
TWO demonstration of using technique of basic building blocks to prove the whole[origin] - saturnman - 一路
and when n equals to 8 we have
TWO demonstration of using technique of basic building blocks to prove the whole[origin] - saturnman - 一路
now we have got the property that each we form the solution, the left empty square is on the corner of the lattice.  Now, we can use this bigger block to form an even larger one to the next stage. We can construct one mathematical induction to prove that we can always make the cover by using L shape basic building block.

Conclusion:
    When facing problems of lattice based or even combinatoric problems, most often we can "color" the object to get an intuitive insight into the problem to make the problem easier to solve.
 
 
  评论这张
 
阅读(464)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017