Hiiiiiiiii everyone! Today I will be showing you a few combinatorics problems which are not very hard. Each one has a different idea. My aim is to introduce you to various ideas you can think of while trying combo problems and realize that combo is very fun!!!!

Oki without wasting much time, let's begin :P

*solution/ideas presented*, here's a list of problems I have discussed below (note that I have modified a few questions, and some of them have answers to the original questions, so you can try reading the problems from AoPS instead if you're too worried on getting "spoiled" xD)

__Problem 1 [ISL 2009 C1 (a)]__ : Consider $2009$ cards, each having one gold side and one black side, lying on parallel on a long table. Initially all cards show their gold sides. Two player, standing by the same long side of the table, play a game with alternating moves. Each move consists of choosing a block of $50$ consecutive cards, the leftmost of which is showing gold, and turning them all over, so those which showed gold now show black and vice versa. The last player who can make a legal move wins. Does the game necessarily end?

__Ideas__ : So the first thing you see is that you are talking about how cards are placed, like if a specific card is showing the gold side or the black side? Well, it's kinda hard to think of so many cards with different colors altogether so we think of some other way to represent it. Why do we really need cards? Since they ain't have a specific purpose here, so the answer is no. Instead, what we do is that we represent a card that is showing its gold side by $1$ and a card that is showing its black side by $0$.

So, initially, you have a sequence of $2009$ $1$'s, and in each move, you change $50$ consecutive numbers from $1$ to $0$ or $0$ to $1$ such that the first number was initially $1$. Moreover, since the only digits we are using are $0$ and $1$, at any given point in time, the sequence can't be negative.

Now if you read the question carefully(or the rephrased version), you notice a line that says

The first number among the $50$ consecutive numbers should initially be $1$

But how does this help us? So basically in every move, you have some initial sequence of $1$'s and $0$'s starting with $1$, e.g. $$1011\ldots$$

and you flip all the numbers, so the above sequence becomes $$0100\ldots$$

So what you do is $$1011\ldots \mapsto 0100$$

Do you see something interesting? The second number is less than the first number! and this always holds true, because initially there was a $1$ in beginning and after we do a move, it's $0$. Now suppose this sequence was *surrounded* by some other numbers too, does this still hold true? The answer is YES! As a quick exercise, you can try to prove it yourself :P

Okay so now let's accumulate all the information we have now:-

1) The initial sequence is $\underbrace{1 \ 1 \ \ldots \ 1}_{2019\text{ ones}}$

2) After every move, the sequence decreases.

3) The sequence is always non-negative

Hmm, this looks interesting. Ok so from points $2$ and $3$ we can see that a positive integer is constantly decreasing, but after a certain point of time, it can't decrease anymore, because if it continues to decrease infinitely it will become negative, which can't happen. And hence, the game must always end.

__Remarks__ : The main idea of this problem was to note that a lower bounded sequence __of integers__ can never decrease infinitely and that the *gold and black-sided cards *are just flavor text and you can instead use binary numbers to denote them. Rewriting the problem in different ways is a very important step in many questions.

You can generalize this problem for $n$ cards, where you flip $k$ cards in a given move, the idea is still the same.

__Problem 2 [USAMO 1997 P1] __ : Let $p_1, p_2, p_3, \ldots$ be the prime numbers listed in increasing order, and let $0 < x_0 < 1$ be a real number between 0 and 1.

\[x_k = \begin{cases} 0 & \mbox{if} \; x_{k-1} = 0, \\[.1in] {\displaystyle \left\{ \frac{p_k}{x_{k-1}} \right\}} & \mbox{if} \; x_{k-1} \neq 0, \end{cases}\]

__Ideas__: In this problem, if $x_{i - 1} \ne 0$ and $x_i = 0$, it means that $$\left\{ \frac{p_i}{x_{i-1}}\right\} = 0$$ which is possible only if $x_{i - 1} \mid p_i \implies x_{i - 1} \in \{1, p_i\}$ for some $i$.

*seemingly nice*values of $x_0$ and make some conclusions. Well if you have enough patience and try out a few values you note that

*most*of those work out... This is because when we think of picking a "nice" value, we most of the time pick a rational value, in a very rare case we will pick some irrational value of $x_0$. Well if you picked all rational values, then you might guess that all possible $x_0$ work, but then you should be careful! You didn't try irrational values.

__Remarks__: The main thing is to guess the answer correctly, and realize that putting $x_0 = \frac{a}{b}$ is nice. Tho at first glance it looks like you're

*adding an extra*variable in some sense, well sometimes you gotta be strong and just work it out!

__Problem 3 [IMO 2011 P4]__: Let $n > 0$ be an integer. We are given a balance and $n$ weights of weight $2^0, 2^1, \cdots, 2^{n-1}$. We are to place each of the $n$ weights on the balance, one after another, in such a way that the right pan is never heavier than the left pan. At each step we choose one of the weights that has not yet been placed on the balance, and place it on either the left pan or the right pan, until all of the weights have been placed.

__Ideas__: At first glance, the most natural thing to try is to try for $n = 1,2,3$ and maybe other small values too. Well counting the number of ways directly for $n$ seems a bit vague right? So it gives vibes to find the number of ways for $n$ in terms of $n-1$ and maybe some other small values. To formalize this, we let $a_n$ be the number of required ways, and we are basically trying to find a recurrence in $a$.

**and**total weight on each pan after placing $i$ blocks?

__Remarks__: The main idea is to realize that you can write $a_n$ in terms of smaller $n$'s, and basically to realize how to do that, which is a bit non-trivial. Then solving the recurrence is pretty standard if you have enough practice with it.

__Problem 4 [USAMO 2002 P1]__: Let $S$ be a set with $2002$ elements, and let $N$ be an integer with $0 \leq N \leq 2^{2002}$. Prove that it is possible to color every subset of $S$ either black or white so that the following conditions hold:

- the union of any two white subsets is white;
- the union of any two black subsets is black;
- there are exactly $N$ white subsets.

__Ideas__: Clearly at first glance it's obvious that $2002$ is just a bluff, and it should hopefully work for all $k$ or maybe even $k$, either of which can be true or maybe all $k$ with some specific property.(Here $k = |S|$) Moreover, for simplicity we can assume that if $S$ is a $t$ length subset then $S = \{1, 2, \ldots, t\}$.

__Remarks__: The main thing was to notice that $2002$ is not important. Moreover realizing that we can do this inductively is a key idea to solve this. I personally like this problem

*a lot*because you don't really need paper to solve this, you can try this problem in your mind when just hovering around and finish it off :P

__Problem 5 [Canada 2018 P3]__: Two positive integers $a$ and $b$ are

__prime-related__if either $a/b$ or $b/a$ is prime. Prove that if $n \ne 1$ is a perfect square then it's not possible to arrange all the divisors of $n$ in a circle, so that any two adjacent divisors are prime-related.

__Ideas__: Since we are talking about prime thingies and factors of $n$, it's natural to consider $n = p_1^{a_1}p_2^{a_2} \ldots p_k^{a_k}$, where $a_i$ is even because $n$ is a perfect square. Now working directly with $k$ seems a bit hard, so we try to work for smaller values of $k$ first. For $k = 1$ it's trivial, so let's take $k = 2$ first. Now I don't really know how to motivate the next step, but maybe it's just practice and observations.

*try*to make it look a bit organized. So what we do is, we arrange all the factors of $n$ in a $(a_1 + 1) \times (a_2 + 1)$ size grid, with the top-left element as $1$. And whenever we move to the right, we multiply with $p_1$ and when we move down we multiply by $p_2$. So basically the grid looks something like this:-

*move*it changes its color). But the number of numbers it passes through other than $1$ is $$(a_1 + 1)(a_2 + 1) - 1$$ Since $a_1, a_2$ are even, the above number is even, which is a contradiction.

__Remarks__: The actual problem is a bit different, I found the other part of problem boring, but this idea to consider a $k-$dimensional chessboard was pretty cool. Moreover, this just comes from basic intuition from the $k = 2$ case. Like at first glance you might try $k$ colors instead of just black/white for $k$ dimensional grid and

*that*

*might*not work, then you try some other things until you realize the $2$ color idea just works.

**: Let $n\geq 2$ be a positive integer. Prove that all divisors of $n$ can be written as a sequence $d_1,\dots,d_k$ such that for any $1\leq i<k$ one of $\frac{d_i}{d_{i+1}}$**

__Exercise 1 [Kazakhstan 2016]__**:Let $n$ be a nonnegative integer. Determine the number of ways to choose sets $S_{ij} \subseteq \{1, 2, \dots, 2n\}$, for all $0 \le i \le n$ and $0 \le j \le n$ (not necessarily distinct), such that**

__Exercise 2 [USAMO 2019 P4]__- $|S_{ij}| = i+j$, and
- \item $S_{ij} \subseteq S_{kl}$ if $0 \le i \le k \le n$ and
- $0 \le j \le l \le n$.

Very nice blog, Pranav. I really enjoyed while solving them and I'm looking forward for part 2. But I think it maybe better if the difficulty level of problems are increased in part 2.

ReplyDelete