Skip to main content

Basic Combinatorial Ideas Part 1

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

For those of you who want to try the problems before seeing the 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)

1) ISL 2009 C1 (a) 
2) USAMO 1997 P1
3) IMO 2011 P4
4) USAMO 2002 P1
5) (adapted from) Canada 2018 P3

Rather than just giving out the solution, I will try to motivate how you come up with such a step, so that it helps to develop intuition :D


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}\]

where $\{x\}$ denotes the fractional part of $x$. Find, with proof, all $x_0$ satisfying $0 < x_0 < 1$
for which the sequence $x_0, x_1, x_2, \ldots$ eventually becomes $0$.

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$.

Now basically you try a few 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.

So on the basis of our observations, we claim that all rational values for $x_0$ work, and irrational values don't. Let's prove that rational values work. We know that $x_0 \in (0,1)$, so it's very natural to consider $x_0 = \frac{a}{b}$, where $a,b \in \mathbb{Z}$ and $a < b$.
$$\implies x_1 = \left\{ \frac{2b}{a} \right\} $$
Now when we simplify the above expression for $x_1$ and write it in fractional form, we see that it will be of form $x_1 = \frac{t}{a}$, where $t < a$. Now we find $x_2$
$$x_2 = \left\{\frac{3a}{t}\right\}$$
So basically what happened was, the numerator of $x_i$ becomes the denominator of $x_{i+1}$, and since the numerator of $x_i$ is always less than the denominator of $x_i$ as $x_i \le 1$ by definition. And hence we get that denominators continuously decrease, or there's a point when the denominator divides the numerator. The first case can be solved using an idea that we used in Problem 1 !! Can you figure it out and finish it? For the second case, it's almost similar as well, sooo you can finish it as an exercise :P

Now we also have to prove that irrationals don't work, hmm. So for proving that, we use the above fact. If in the sequence, at any point of time a rational number occurs, it will just end up being $0$ as proved. So if an irrational value for $x_0$ doesn't work, it means that $\{x_n\}_{n \ge 0}$ should be a sequence of irrational numbers only. This is kind of easy to prove, so I recommend trying it on your own! But for sanity purposes, here's the idea:- 
If $x$ is irrational, then so is $\frac{1}{x}$ and now you should be able to finish by induction by using the fact that how $x_i$ is defined :P

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.
Determine the number of ways in which this can be done.

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$. 

Now, we try to extract some information from the question. Note that the weights are in a geometric progression, there should be a reason behind it, right? It can't be just random, this is not the same as having the weights to be $1, 2, 3, 4, \ldots $. But what's special about a geometric series and total weight on each pan after placing $i$ blocks?
One interesting thing to note is that $$2^0 + 2^1 + \ldots + 2^k < 2^{k +1}$$ But now how is this useful? The thing is, whenever you place the heaviest block existing(it should always go on the left pan), all the other blocks after it can go anywhere, as the right pan will always remain lighter than the left pan.

Suppose we place the weight $2^{n - 1}$ after placing $i$ blocks. Then we first choose any $i$ blocks from the other $n - 1$ blocks, in $\binom{n - 1}{i}$ ways. Now, since those $i$ weights could be organized on the pan in $a_i$ ways. This is because of the property of the geometric progression I mentioned above. So which means there are $$\binom{n - 1}{i} \cdot a_i$$
ways to place $i$ blocks before placing the $2^{n -1 }$ block. Clearly, this block can only go to the left pan and there's only $1$ way to do so. Now the remaining $n - i - 1$ blocks can be placed on any of the pans in any order, so we first consider the number of orders which is just $(n - i - 1)!$ and since each block has $2$ options to go to, we get $$2^{n - i - 1}\cdot (n - i - 1)!$$ ways to put the remaining blocks. 
Combining, we get that if the block $2^{n - 1}$ is placed after $i$ blocks, the number of ways will be $$2^{n - i - 1} \cdot (n - i - 1)! \binom{n - 1}{i} \cdot a_i = 2^{n - i - 1} \cdot \frac{(n - 1)!}{i!}\cdot a_i$$
Now, notice that $i$ can be anything from $0$ to $n - 1$
$$\implies a_n = \sum_{i = 0}^{n - 1} \left(2^{n - i - 1} \cdot \frac{(n - 1)!}{i!}\cdot a_i\right)$$
Now this sum can be solved easily, but for the sake of completeness, here's the remaining solution :- 
$$\implies a_n = \sum_{i=0}^{n-2} \left(2^{n-i-1}\cdot \frac{(n-1)!}{i!}\cdot a_i\right) + a_{n-1}$$
$$\implies a_n = 2(n-1) \cdot\sum_{i=0}^{n-2} \left(2^{n-i-2}\cdot \frac{(n-2)!}{i!}\cdot a_i\right) + a_{n-1} $$
Note that we can write $$a_{n - 1} = \sum_{i = 0}^{n - 2} \left(2^{n - i - 2}\cdot \frac{(n - 2)!}{i!} \cdot a_i\right)$$
$$\implies a_n = 2(n-1)\cdot a_{n-1} + a_{n-1} = (2n-1)a_{n-1}$$
Since $a_1 = 1$, we get 
$$a_n = (2n - 1)\cdot (2n - 3) \cdot \ldots \cdot 3 \cdot 1$$ $$\implies \boxed{a_n = (2n - 1)!!}$$

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\}$.
The most natural thing now is to try for $k = 1, 2, 3\ldots$. After you try it with enough patience, you realize it's true for all small values of $k$, so you make a guess that it might be true for all $k$! 

Now the next thing you try to see is if there's some sort of "pattern" on how to color because c'mon $2^{2022}$ is like very HUGE. So if you're observant enough, you can notice that we can color the elements inductively. For $k = 1, 2$ it's easy.

Assume that we can color all the subsets for $\mid S \mid = k - 1$, we need to prove we can also color the subsets of $S$ when $\mid S \mid = k$ with the given conditions.
If $N \le 2^{k - 1}$, color the same subsets white which you did for $k - 1$ case. Note that for $k - 1$ case, none of the subsets has element $k$ in it. And hence exactly $N$ white subsets will be there for $N \le 2^{k - 1}$ case satisfying the other $2$ properties (if this doesn't seem obvious to you, think over it by considering some small cases, say $k - 1 = 4$ and try to prove it yourself!)

Now when $N > 2^{k - 1}$ what do we do?? Notice that if there are exactly $N$ white subsets, then there are exactly $2^k - N$ black subsets!
$$2^k - N < 2^k - 2^{k - 1} < 2^{k - 1}$$
This means there are less than $2^{k - 1}$ black subsets. This means if you color all the subsets black which was white in $2^k - N$ white subsets case, you will be done! SO YAYYY we proved the problem for all $\mid S \mid \ge 1$.

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.

We basically 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:- 
Now, what we try to do is consider a cycle starting from $1$, such that at any given time we can move only $1$ step right/left/up/down, basically, no diagonal moves are permitted. This ensures that consecutive elements are prime-related. And we also want the cycle to end at $1$ and cover all the numbers in the grid exactly once so that we can arrange the numbers in the circle. So if it was possible to do so, then we can find such a cycle, but we have to show it's not possible. Note that from $1$, you can only go to $p_1$ or $p_2$, say you go to $p_1$. Now to end at $1$, the second last element should be $p_2$ only (think why?). 

This next step is a bit hard to think of but is a fairly standard idea. We now do chessboard coloring in this grid, and since $p_1$ and $p_2$ are diagonal, they should be of the same color. This means our path(starting from $p_1$ and ending at $p_2$) should be of an odd length so as to not change the color (parity reasons, as in each 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.

Okay so this works! Now we try to generalize this idea for $k$ prime factors too :P Soooo get ready for the nicest idea hehe.....
We consider a $k-$dimensional grid, and basically whenever we move along a particular direction, we multiply by a particular prime number. If it's hard to imagine this way, we can also consider a $k-$length tuple denoting indices of the grid, so for example 
$$(x_1, \ x_2, \ \ldots, x_i, \ldots, x_k) \mapsto (x_1, x_2, \ \ldots, x_{i} + 1, \ldots, x_k)$$
we multiply by $p_i$.
Now we do the same chessboard coloring, so basically if the distance between two points is $\sqrt{2}$, they both are of the same color, and here we want to have a cycle with the same conditions, which is basically a path from one prime factor to another prime factor is needed, wlog say from $p_1$ to $p_2$. And now since $p_1, p_2$ are both of the same color and the path will be of even length, this is not possible. And hence a contradiction.

Which means 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. 

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.
Moreover, you could also rephrase this thing graphically, but I think that's not as easy as the idea presented above.



Phew! we are done for today yayy, I hope you liked the problems and learned some new ideas from them. 
You can try the following questions as an exercise which are based on similar ideas :-

Exercise 1 [Kazakhstan 2016] : 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}}$
and $\frac{d_{i+1}}{d_i}$ is a prime number.

Exercise 2 [USAMO 2019 P4] :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 
  • $|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$.

I will bring part $2$ of it soon where we will work on $5$ more problems hehe. Do tell in the comments which problem you liked the most, and if the overall difficulty was fair enough or if I should modify (increase/decrease) it a bit in part 2.

Byeeeeeee :DDD
Pranav

Comments

  1. 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

Post a Comment

Popular posts from this blog

Constructions in Number Theory

Hi, I am Emon, a ninth grader, an olympiad aspirant, hailing from Kolkata. I love to do olympiad maths and do some competitive programming in my leisure hours, though I take it seriously. I had written INOI this year. Today, I would be giving you a few ideas on how to Construct in Number Theory . Well, so we shall start from the basics and shall try to dig deeper into it with the help of some important and well-known theorems and perhaps, some fancy ones as well. Okay, so without further delay, let's start off... What do we mean by "Constructions"? If noticed, you can see that you often face with some problems in olympiad saying, "... Prove that there exists infinitely many numbers satisfying the given conditions" or "... Prove that there exists a number satisfying the above conditions." These are usually the construction-problems .  For example, let's consider a trivial example : Problem. Prove that there exist infinitely many integers $a$ such th

EGMO solutions, motivations and reviews ft. Atul, Pranjal and Abhay

The  European Girls' Mathematical Olympiad a.k.a EGMO 2022 just ended. Congrats to Jessica Wan from USA, Taisiia Korotchenko, and Galiia Sharafetdinova for the perfect scores! Moreover, the Indian girls brought home 4 bronze medals! By far, this is the best result the EGMO India Team has ever achieved! To celebrate the brilliant result, here's a compilation of EGMO 2022 solutions and motivations written by my and everyone's favorite IMOTCer Atul ! And along with that, we also have reviews of each problem written by everyone's favorite senior, Pranjal !  These solutions were actually found by Atul, Pranjal,  and Abhay  during the 3-hour live solve. In the live solve, they solved all the 6 problems in 3 hours 😍!!! Okie Dokie, I think we should get started with the problems! Enjoy! Problem 1:  Let $ABC$ be an acute-angled triangle in which $BC<AB$ and $BC<CA$. Let point $P$ lie on segment $AB$ and point $Q$ lie on segment $AC$ such that $P \neq B$, $Q \neq C$ and

Q&A with experts about bashing

Heyy everyone! From the title, you can see that we are going to talk about  BASH.  Yesss, we are going to discuss whether you really need to learn bash or not?  Let me first introduce myself, I am Pranav Choudhary, a 10th grader from Haryana(India). I like to do geo and combo the most :PP. Oki so let's begin! For those of you who don't know what bashing is, lemme give you a brief introduction first. Bashing is basically a technique used to solve Geometry Problems. In general, when you try a geo problem you might think of angles, similarities, and some other techniques (e.g. Inversion, spiral similarity etc). All of which are called synthetic geometry. But sometimes people use various other techniques called "bash" to solve the same problems.  Now there are different kinds of bashing techniques, e.g. - Coordinate bash, Trig Bash, Complex bash, Barycentric Coordinates. Let me give you a brief introduction to each of them.  Coordinate Bash : You set one point as the orig