数学吧 关注:876,334贴子:8,689,816

大佬们求助

只看楼主收藏回复

我朋友让我帮忙解游戏里这道题,要求用右边三种方块覆盖满除了划掉的剩下24个小方块(游戏里只要求尽可能多覆盖)。我试了半天都无法完全覆盖,所以感觉应该无解,但是他硬要我给出证法,所以是否可以证明无法完全覆盖呢


IP属地:北京来自Android客户端1楼2024-03-16 15:02回复
    瞪眼法猜一下,把三个形状从上到下叫甲乙丙
    甲乙的形状都可以用两个丙拼出来,一共24个格,所以如果能铺满,只需要用12个丙
    显然,不能单独用乙填满
    然后考虑能否仅用甲填满,若能填满,可以根据甲的形状看出来在挖掉格的上,右,右上三个格子限制下,有且仅有甲的两种摆法,经过目测试验后发现都无法铺满,于是得出结论,如果存在铺满方案的话,那么该方案应至少存在一个甲和一个乙,于是这一个甲和一个乙一共可以等同于4个丙,最终需要的数量是:甲≥1,乙≥1,丙≤8,这三个数量上显然是符合预留数量的
    然后看乙和丙。当乙和丙的摆放不相邻时,在此规则下的摆放方案有限,穷举法可以得知无法完成;当乙和丙的摆放相邻时,其组合形状总可以等价于一个甲+一个丙,也就是说不需要乙就可以完成摆放,这和至少需要一个乙是矛盾的
    综上所述,假设是错误的,即不存在用甲乙丙铺满的方案


    IP属地:广东来自Android客户端2楼2024-03-16 17:40
    收起回复
      猜你想搜:棋盘染色


      IP属地:美国来自Android客户端4楼2024-03-16 18:13
      回复
        24个格子有13个黑的和11个白的。你的那几种形状不论如何放置,盖住黑色和白色格子的数目都一样。所以盖不满。


        IP属地:美国来自Android客户端5楼2024-03-16 18:15
        收起回复
          这是O神那个新活动吗(关注点错误)


          IP属地:湖北来自Android客户端7楼2024-03-16 18:59
          回复
            5L正解,对于这种问题,染色往往是相当简便的解法.


            IP属地:安徽来自Android客户端8楼2024-03-16 21:24
            回复
              等后面有个允许重复格就可以了


              IP属地:浙江来自Android客户端10楼2024-03-17 11:13
              回复
                很简单,从任意一点出发,如果可以一笔遍历所有格则可以满覆盖,不能遍历则不能满覆盖(不叠放)


                IP属地:广西来自Android客户端11楼2024-03-17 13:15
                回复
                  分黑白块,然后配件黑白相等,棋盘黑比白多2,所以不能填满


                  IP属地:江苏来自Android客户端12楼2024-03-17 13:25
                  回复
                    涂黑白块吧,给出的构建块显然只能是一半黑一半白,而原图是13:11,所以没可能完全覆盖


                    IP属地:江苏来自Android客户端13楼2024-03-17 14:09
                    回复
                      至少会漏一个


                      IP属地:河北来自Android客户端14楼2024-03-17 16:40
                      回复
                        5楼正解
                        自然染色是覆盖问题的最基本做法


                        IP属地:江苏来自Android客户端15楼2024-03-17 17:15
                        回复
                          经典黑白染色法,把棋盘像国际象棋盘那样黑白间隔染色,左边那个扣掉一格后是黑色比白色多两格,而右边能用的所有方块不管怎么放黑白两色的格子一定是一样的,所以最少会有两个黑色格子无法覆盖


                          IP属地:浙江来自Android客户端16楼2024-03-17 20:09
                          回复
                            放不满也没事啦,活动还有好多天,随便玩下就级拿满奖励的


                            IP属地:安徽来自Android客户端17楼2024-03-17 22:17
                            回复
                              一眼奇偶性


                              IP属地:上海来自Android客户端18楼2024-03-17 22:18
                              回复