Consider lattice points of a $6*7$ grid.We start with two points $A,B$.We say two points $X,Y$ connected if one can reflect several times WRT points $A,B$ and reach from $X$ to $Y$.Over all choices of $A,B$ what is the minimum number of connected components?
Problem
Source: Iranian second round2019/Day2/Problem6
Tags: combinatorics, graph theory
03.05.2019 13:01
Consider the grid in the lattice points.Then the parity of coordinate of each point doesn't change under reflection we will prove that each of four parity based sets are not connected from which every thing else follows.First consider the points with both coordinate even other cases can be handeled similarly.Since we have $16$ points and the generator is a point $x$ for example we should also have $8(a-b)+x$ or $8(b-a)+x$ which if $A,B$ are in different rows is a contradiction.When $A,B$ are in the same row everything is clear.So we should have at least $8$ connected components.The construction is easy take two centeral points.
04.05.2019 16:16
Another Solution: Consider the graph where the vertices are the $56$ lattice points, and two are connected if they are reflections with respect to either $A$ or $B$. If our graph has $k$ connected components and the $i-th$ component has $x_i$ vertices, then our original graph has at least $(x_1-1)+...+(x_k-1)=56-k$ edges, on the other side, every edge of our graph is drawn because of either $A$ or $B$. Assume that the distance of $A$ to the leftmost column, rightmost column, highest row, and the lowest row is $a,b,c,d$ respectively. Assume points $R,S$ are reflections of eachother with respect to $A$, assume WLOG that $R$ lies at the first region wrt to $A$ then, $S$ lies at the third region of $A$ , if $x_R-x_A=e$ then $x_A-x_S=e$ and if $y_R-y_A=f$ then $y_A-y_S=f$ ( where $x_W$ and $y_W$ denote the $x$ and $y$ coordinate of point $W$. ) Because points $R,S$ lie within the region of $6*7$ grid, we conclude that $e\leq a , e\leq b$ so $e\leq min(a,b)\leq 3$ because $a+b=7$ and $f \leq c , f\leq d$ so $f\leq min(c,d)\leq 3$ because $c+d=6$ so all the pairs of points $(R,S)$ that are reflections with respect to $A$ lie within the $6*6$ rectangle area where $A$ is the center of rectangle. If the height of the created rectangle is $6$ , then we conclude that $ min(c,d)=3 , c+d=6 $ so $ c=d=3$ so $A$ should lie on the fourth row ( among the $7$ rows) and one can easily check that among all lattice points such that the rectangle region around them are $6*6$ are only those two lattice points closest to the center of the rectangle. If one of $A$ or $B$ lie at one of those two points, the number of the edges drawn in our graph because of that point will be $25$. Otherwise, the rectangle region around the point would be at most $6*4$ and this generates $18$ edges, so if points $A,B$ are not precisely those two lattice points closest to the center of the rectangle, the number of the edges in graph will be at most $18+25=43$ and the relation $56-k \leq 43$ yields $13 \leq k$ but if points $A,B$ are the two lattice points closest to the center of the rectangle, one can easily check that $k=8$. Note: In the above solution two ( not necessarily distinct ) vertices are drawn if they are reflections with respect to one of the two points $A,B$ . However, we can remove the two edges where their endpoints are the same ( that are precisely the points $A,B$ ), then, the $6*6$ rectangle area around point $A$ generates $24$ edges and other rectangle areas , that are at most $4*6$ , generate at most $17$ edges, putting these in our inequality, we obtain a better bound $15 \leq k$ for the case that points $A,B$ are not precisely the two points closest to the center of the rectangle.
04.05.2019 17:37
When reflecting, should the reflected point stay inside the table?
04.05.2019 17:38
math90 wrote: When reflecting, should the reflected point stay inside the table? Yes it should.
06.05.2019 06:35
30.12.2019 20:17
Prove that if the distanse of the 2 points is more than 1 than we cant have more than 7 in one group we have example for 8 so for the sake of contradiction we say that there exists an example for 7 (if its lower just let us have some empty groups) and since in a 6×7 grid we have 56 points in one of the groups we have atleast 8 points but we cant have 8 points in every group (consider the group that the point A itself is in it) so we should have a group with atleast 9 points inside it and we have 5 of them are in one side of the line AB and using thales we have that the distance of 2 points like C and D is atleast 8T such that T is the distance of AB the highest distance in the 6×7 grid is sqr(36+49) and we know if T>1 than T >= sqr(2) so we should have 8 sqr(2)< sqr(85) and this is wrong so we have T=1 and sinse the line CD is parallel to AB we have that CD is lower than 8 but we have CD is equal to 8. Contradiction
19.04.2020 09:35
Without loss of generality we can suppose $A=(0,0)$ and $B=(p,q)$. I have two claims: 1. The parity of reflected point doesn't change over operation It's trivial as discussed before, I leave it. 2. Each point in a arbitrary set lays on one of two defined lines: Consider the point $(x,y)$ we start from. As you see we have two reflection paths: $$(x,y)\to(-x,-y)\to(2p+x,2q+y)\to(-2p-x,-2q-y)\to(4p+x,4q+y)\to\dots$$$$(x,y)\to(2p-x,2q-y)\to(-2p+x,-2q+y)\to(4p-x,4q-y)\to(-4p+x,-4q+y)\to\dots$$ Those two lines are: $(x+kp,y+kq)$ and $(-x+kp,-y+kq)$ where $k\in \mathbb{Z}$ Lemma 1. No two linearly consecutive points are in same set. Proof. Let's divide this to two parts; Points laying on same $x-$axis or $y-$axis and others. First can is trivial because of parity difference. But for the second part I'm going to use some basic number theory. I claim that not all of points laying on a line can have same parity. This is because of $p$ and $q$. Consider two points lying on one line. Let call them $S_1=(x_0,y_0)$ and $S_2=(x_0+p,y_0+q)$. them: We know $gcd(kp,kq)$ is at least $2$ there is at least one point standing between $S_0$ and $S_1$ that its parity differs. ($(x+\frac{p}{2^d},y+\frac{q}{2^d})$ where $d$ is the greatest power of two dividing both $p$ and $q$) So by this claim each line have at least two different parities. (I'm not considering lines going through only one points on corners.) Finally note that each line in parallel to line $(kp,kq)$ or the line passing through points $(p,q)$ and each two corresponding lines are symmetrical because the sign of $x$ and $y$. We have at least 6 lines related to how we choose $(p,q)$. In splitting these lines to pairs of corresponded lines by noting that lines in a pair are symmetrical to line $(kp,kq)$, there can be two pairs and two single lines. We have two different components for each of two pairs $=2\times 2=4$ and two other for single lines $=2\times 2 = 4$. At all we have at least $4+4=8$ components. Finally we need to give an example that a solution exists with this bound: ooooooo ooooooo oooxooo oooxooo ooooooo ooooooo
20.03.2024 14:05
Hello, what if $A$ and $B$ were in corner? Woudn't it be $2$ components then?