Re: [離散] 長方形分割

[sato186 (銀色轟炸機)]

※ 引述《mqazz1 (無法顯示)》之銘言：
: A 3*7 rectangle is divided into 21 squares each of which is colored red
: or black.
: Prove that the board contains a nontrivial rectangle (not 1*k or k*1)
: whose four corner squares are all black or all red.
: 請問這題在問什麼呢?
: 又應該怎麼證明呢?
: 謝謝

就是說 至少會有一個 m ×n 的長方形 (m,n > 1) 的四個角落皆同色

例如右邊這個長方形  □■■□
                    □■□■
                    □■■□

怎麼證明?

方便起見, 先把長方形擺橫的 □□□□□□□
                           □□□□□□□
                           □□□□□□□

首先, 由於只有兩種顏色

故對於同一行而言, 一定至少有相同顏色的兩格

e.x. □ <
     ■
     □ <

接著, 每一行同色的情況共有

╭ 3 ╮
│   │ ×2 = 6 種.
╰ 2 ╯

□ ■ □ ■ ╳ ╳
□ ■ ╳ ╳ □ ■ (╳表任意一種顏色)
╳ ╳ □ ■ □ ■

因有七行 故必至少有兩行為同樣同色情形

把那兩行抓出來當長方形兩邊就是所求


key point: 鴿籠原理

--
　　　　　　　　　 翩若驚鴻　婉若游龍　榮曜秋菊　華茂春松
　　　　　　　　　 髣彿兮若輕雲之蔽月　飄颻兮若流風之迴雪
　　　　　　　遠而望之 皎若太陽升朝霞　迫而察之 灼若芙蕖出淥波
　　　　　　　襛纖得衷　脩短合度　肩若削成　腰如約素　延頸秀項
　　　　　　　皓質呈露　芳澤無加　鉛華弗御　雲髻峨峨　脩眉聯娟
　　　　　　　丹脣外朗　皓齒內鮮　明眸善睞　靨輔承權　瑰姿豔逸
　　　　　　　　儀靜體閑　柔情綽態　媚於語言　奇服曠世　骨像應圖

--
※ 發信站: 批踢踢實業坊(ptt.cc)
※ 編輯: sato186         來自: 111.242.8.225        (10/10 20:29)
推 mqazz1      :感謝!!