Is it possible to divide a $7\times7$ table into a few $\text{connected}$ parts of cells with the same perimeter? ( A group of cells is called $\text{connected}$ if any cell in the group, can reach other cells by passing through the sides of cells.)
Problem
Source: Iran MO 3rd round 2016 mid-terms - Combinatorics P2
Tags: Iran, combinatorics, table
12.09.2016 19:52
This seems very easy? If the bottom left is (0,0) and the top right is (7,7), Just draw a path with length 14 from (1,0) to (6,7). This must cut the board into two connected pieces of perimeter 28 each.
08.04.2017 14:52
laegolas wrote: This seems very easy? If the bottom left is (0,0) and the top right is (7,7), Just draw a path with length 14 from (1,0) to (6,7). This must cut the board into two connected pieces of perimeter 28 each. Yes, actually the problem is not this!!! In place of a few you must check if it can be divide into x of them!!! I can't remember what was x, but I think it was 13.
24.12.2017 22:04
Chamran wrote: laegolas wrote: This seems very easy? If the bottom left is (0,0) and the top right is (7,7), Just draw a path with length 14 from (1,0) to (6,7). This must cut the board into two connected pieces of perimeter 28 each. Yes, actually the problem is not this!!! In place of a few you must check if it can be divide into x of them!!! I can't remember what was x, but I think it was 13. Answer is no? floor of 49/13 is 3, so there is a piece with at most three squares. Perimeter of that must be 8. No other piece without three squares has perimeter of 8, so all pieces are 3 squares, contradiction?
25.12.2017 16:49
@above Not all pieces must consist of three squares to have perimeter $8$, it may be a $2\times 2$ squares.
26.12.2017 03:55
ThE-dArK-lOrD wrote: @above Not all pieces must consist of three squares to have perimeter $8$, it may be a $2\times 2$ squares. lol oops. I guess my logic for a three-square piece still applies for n = 13, then you have that the pieces either have three squares or 4 squares from which it follows that there must be 10 4-square pieces and 3 3-square pieces. But a chessboard style tiling with (i,j) being black iff i and j are both even shows that only 9 4-square pieces can fit on the board, so answer is no such tiling exists...
24.07.2018 03:45
problem: Is it possible to divide a table into a 13 group of cells with the same perimeter? ( A number of cells are called a group ,if any cell in the group, can reach other cells by passing through the sides of cells.) it's not actually possible. first for figuring out the perimeter we know that it has to be even and it can't be less than $ 8$ because four mean only individual squares and $6$ means just two individual squares which are connected and it's obviously wrong. we say it can't be $10$ or more because then each part must consist more than four squares which can't be $(13.4 \ge 49) \implies$ the perimeter must be eight ! and some easy calculation will give us we should have ten $2*2$ squares and three part consisting of three cells. and then you can easily check with colouring the odd rows blue and the even ones red would simply give us a contradiction !
02.08.2021 10:50
H.HAFEZI2000 wrote: problem: Is it possible to divide a table into a 13 group of cells with the same perimeter? ( A number of cells are called a group ,if any cell in the group, can reach other cells by passing through the sides of cells.) it's not actually possible. first for figuring out the perimeter we know that it has to be even and it can't be less than $ 8$ because four mean only individual squares and $6$ means just two individual squares which are connected and it's obviously wrong. we say it can't be $10$ or more because then each part must consist more than four squares which can't be $(13.4 \ge 49) \implies$ the perimeter must be eight ! and some easy calculation will give us we should have $10 $ $2*2$ squares and three part consisting of three cells. and then you can easily check with colouring the odd rows blue and the even ones red would simply give us a contradiction ! I think there is an another good way to solve last part after realizing we have $10 $ of$2*2$ squars and 3 of three cell shape ,we can use the fact that we need at least one of the $1*3$ 's to impact on every row and column and every $1*3$ can have a impact on at most 4 rows and column so we can at most impact on 12 of them but we have 14 columns and rows ,so it leads to contaction