A lot of people suspect that this problem has appeared in one/several other sources before, any ideas?

Assassino9931 wrote: A lot of people suspect that this problem has appeared in one/several other sources before, any ideas? What exactly do they claim and how can they not confirm it if it did?

Assassino9931 wrote: A lot of people suspect that this problem has appeared in one/several other sources before, any ideas? There are $10^6$ math problems, so it is evident that the probability of appearance of similar questions in the competition is very high.

Yes yes I know, I am not trying to blame anyone, many of us are just curious for relevant sources and their style. It is completely fine for me if the problem is not original unless somebody has seen it or a similar one (I have not heard of anyone for now).

Isn't this quite easy for a P5

lelouchvigeo wrote: Isn't this quite easy for a P5 Idk it is kinda hard to see after you solved it but I don't think it was too easy. It's probably all right, the IZhO is usually a bit easier than IMO

Anyone found a graph solution to this? I guess something using Hall's theorem?

Maths_Girl wrote: Anyone found a graph solution to this? I guess something using Hall's theorem? I thought that there may be one but in marking scheme they explicitly state that progress concerning the graph (proving it is bipartite etc) is worth 0 points, so I would suppose that doesn't work

I think this works. Assume wlog that $n$ is even. Start by tiling the table with vertical dominos. Call a stripe good if it contains a domino and otherwise bad. Notice that at the start, all vertical stripes are good. We will do a process of changing the tiling such that every stripe that was good before will remain good, at every stage in the process there will be at least one good stripe added, and the dominos intersecting every bad stripe will form a $3\times 2$ rectangle (it's easy to see it happens in the start). Take the leftmost bad stripe (if there is more than one, choose one arbitrarily) and assume wlog that the dominos intersecting it are continuing upwards (i.e. they form a $3\times 2$ rectangle with the stripe at the bottom). We want to take two of these dominos and rotate them by $90^{\circ}$ so that our stripe will become good. It's easy to see that it won't make any previously good tile bad, so the only problem is if the new tile which is not in the stripe intersects a bad stripe and is not contained by it. Some case checking shows that the only such case is when the leftmost domino is contained in another bad stripe to the left of the original stripe, which is a contradiction.

Similar one (sorry, the file is in Russian): https://www.pdmi.ras.ru/~olymp/2016/problems/c_68_16.pdf See Problem 6 in Grade 6 or Problem 4 in Grade 8, which says: Quote: Given a table $60\times 60$ tiled with $2\times 5$ blocks. Prove that there exists a tiling of this table with $1\times 3$ rectangles such that every $2\times 5$ contains at least one $1\times 3$ rectangle. The same idea can applied to prove (instead of $2\times 2$, we can take a tiling with $3\times 3$; so every $2\times 5$ will have an overlap with some $3\times 3$ on $1\times 3$).

It's possible to attack it using Hall's marriage theorem. Color the table black and white like a chessboard. Call a stripe $s$ black if it contains more black than white cells and call it white otherwise. Let $W$ and $B$ be the sets of white, respectively white stripes. The given condition yields $|W=|B|$. Connect $w\in W$ to $b\in B$ if some of their end cells are adjacent (horizontally or vertically). The problem boils down to construct a perfect matching between $W$ and $B$. It's enough to check Hall's condition. Let $S\subset W$. Assume wlog that the number of rows is even. We pair the rows like 1-st to 2-nd, 3-rd to 4th, and so on. To each $s\in S$ we can map a black strip $s'\in B$ satisfying one of the two options. 1) an endpoint of $s$ and an endpoint of $s'$ are vertically one upon another in two paired rows. 2) an endpoint of $s'$ is on the right side horizontally of an endpoint of $s$. That is, if we cannot find $s'\in B$ that satisfies 1) we can find $s'$ satisfying 2). Now, this mapping is an injection, hence $|N(S)|\ge |S|$.

mathuz wrote: Similar one (sorry, the file is in Russian): https://www.pdmi.ras.ru/~olymp/2016/problems/c_68_16.pdf See Problem 6 in Grade 6 or Problem 4 in Grade 8, which says: Quote: Given a table $60\times 60$ tiled with $2\times 5$ blocks. Prove that there exists a tiling of this table with $1\times 3$ rectangles such that every $2\times 5$ contains at least one $1\times 3$ rectangle. The same idea can applied to prove (instead of $2\times 2$, we can take a tiling with $3\times 3$; so every $2\times 5$ will have an overlap with some $3\times 3$ on $1\times 3$). Yeap, that is e.g. what I was looking for! This problem has been at Bulgaria's JBMO 2021 preparation (there was a mini team contest between students) but nobody remembered it.

Complete_quadrilateral wrote: Maths_Girl wrote: Anyone found a graph solution to this? I guess something using Hall's theorem? I thought that there may be one but in marking scheme they explicitly state that progress concerning the graph (proving it is bipartite etc) is worth 0 points, so I would suppose that doesn't work Of course solution with Hall's theorem must exist because otherwise the problem would be false. So, you have a bipartite graph as described above. This graph has a perfect matching if and only if the tiling with $2\times 1$ dominos as required exists. Thus, there is a perfect matching and the Hall's condition must hold and it is provable one way or another. I suppose the marking schema just doesn't give points for only constructing a bipartite graph and the idea of Hall's theorem without proving the Hall's condition is satisfied. This was the meaning. But, I think this approach is not actually the truth about this problem. The easiest way is like in #2. Anyway, one can check here the details of #14 approach.

I wonder whether the problem can be extended. Maybe: $p$ and $q$ are two coprime positive integers.Given $m\times n$ table tiled with $p\times 1$ stripes and we are given that $pq | mn$. Find all pairs $(p,q)$ such that there necessarily exists a tiling of the table with $q\times 1$ dominoes such that each of these stripes contains one whole domino.

Twoisaprime wrote: I wonder whether the problem can be extended. Maybe: $p$ and $q$ are two coprime positive integers.Given $m\times n$ table tiled with $p\times 1$ stripes and we are given that $pq | mn$. Find all pairs $(p,q)$ such that there necessarily exists a tiling of the table with $q\times 1$ dominoes such that each of these stripes contains one whole domino. Notice $pq|mn$ is insufficient, you need to state that each of $p$ and $q$ divide one of $m$ or $n$. I think all pairs with $q<\frac{p}{2}+1$ work Just consider a $1\times pq$ rectangle which forces both tilings. If $p/2+1\leq q$, it is easy then to finish with CRT. I think also a identical strategy works in this general construction.