Let N(a,b) be the number of ways to cover a table a×b with domino tiles. Let M(a,2b+1) be the number of ways to cover a table a×2b+1 with domino tiles, such that there are no vertical tile in the central column. Prove that M(2m,2n+1)=2m⋅N(2m,n)⋅N(2m,n−1)
Problem
Source: Rioplatense L-2 2022 #6
Tags: combinatorics
09.05.2023 21:04
Bump bump, anyone know if the solutions to this contest are online?
30.08.2023 15:24
This problem is quite related to ISL C8 2016 The main idea is to see that N(2m,n)⋅N(2m,n−1) is quite suggestive, after all, this is just the number of ways with all the dominos on the vertical line being "to the right": So the key is to try to find some kind of bijection within the general version of M(2m,2n+1) to the example with all the dominos to the right side, as in the picture. And what better way to think of that then to try and find some well-defined cycles of dominos in the board? If we can accomplish this goal, we can actually change the configuration of dominos in the cycle to make it closer to what we want by doing what we'll call a change: So... How do we do it? The key is to remember what we did in C8 2016. In that problem, we did something simillar to this which I'll not say to protect you from spoilers (I really encourage you to think on that problem too). But, for this one, what do we do? We reflect around the central column! With that, we'll get exactly m cycles passing through the central column. As I'm a really lazy person, let's just say that with some amount of work, you can actually prove that each of these cycles passes through 2 central dominos and never gets the dominos in different directions about the central column. So if we apply changes in the m cycles in a way that makes all dominos directed to the right of the central column! With that in mind, we can make 2m different configurations associated with each one of the simpler problem, which we know the answer. So we are done!
30.08.2023 16:52
Well played