Combi Marathon

For discussing Olympiad Level Combinatorics problems
rah4927
Posts:110
Joined:Sat Feb 07, 2015 9:47 pm
Combi Marathon

Unread post by rah4927 » Sun Feb 19, 2017 11:02 am

This thread is dedicated for a marathon on combinatorics problems. The rules are similar to the Geo Marathon. A poster must post both the solution of the previous problem and the next problem of the marathon. If no one solves the next problem within $2$ days, he or she must provide a solution or a link of the official solution and jump to next. The difficulty range is C1 to C9 of the ISL.
1. Don't forget to type the problem number.
2. Try to use LaTeX code
3. Be sure about your provided problem.
If you want your solution to be constructively evaluated, post a link of your post on the Combi Solution Writing Threadie
I will provide the first problem :

Problem 1

Let $n > 3$ be a fixed positive integer. Given a set $S$ of $n$ points $P_1, P_2,\cdots, P_n$ in the plane such that no three are collinear and no four concyclic, let $a_t$ be the number of circles $P_i P_j P_k$ that contain $P_t$ in their interior, and let $m(S) = a_1 + a_2 +\cdots + a_n$. Prove that there exists a positive integer $f(n)$ depending only on $n$ such that the points of $S$ are the vertices of a convex polygon if and only if $m(S) = f(n)$.

User avatar
Thanic Nur Samin
Posts:176
Joined:Sun Dec 01, 2013 11:02 am

Re: Combi Marathon

Unread post by Thanic Nur Samin » Sun Feb 19, 2017 6:59 pm

We claim that $f(n)=\dfrac{1}{3}\dbinom{n}{2}\dbinom{n-2}{2}$.

Note that the sum simply counts one third of the quadruplet of points $(P_i,P_j,P_k,P_t)$ so that $P_t$ is inside the circle. (Since the $P$'s can permute in the quadruplet).

Now, for a non-reflex angle $\theta$, we intruduce a function $g$ so that $g(\theta)=\theta$ when $\theta \le 90^{\circ}$ and $g(\theta)=180^{\circ}-\theta$ otherwise. Note that if $g(\angle BAC)>g(\angle BDC)$, then $A$ is inside the circle $BDC$.

Now, from $n$ points, we can choose two points $P_i$ and $P_j$ in $\dbinom{n}{2}$ ways. From the remaining $n-2$ points, we can choose $2$ in $\dbinom{n-2}{2}$ ways. For each pair of points, let the one with smaller $g$ be $P_k$ and the other one be $P_t$. Now, $P_t$ lies inside circle $P_iP_jP_k$. So, the total number of quadruplets are $\dbinom{n}{2}\dbinom{n-2}{2}$ when all the points $P$ form a convex hull.

So, the desired answer is $f(n)=\dfrac{1}{3}\dbinom{n}{2}\dbinom{n-2}{2}$.
Last edited by Thanic Nur Samin on Mon Feb 20, 2017 1:13 am, edited 3 times in total.
Hammer with tact.

Because destroying everything mindlessly isn't cool enough.

User avatar
Thanic Nur Samin
Posts:176
Joined:Sun Dec 01, 2013 11:02 am

Re: Combi Marathon

Unread post by Thanic Nur Samin » Sun Feb 19, 2017 7:04 pm

Problem 2

Determine the greatest positive integer $k$ that satisfies the following property: The set of positive
integers can be partitioned into $k$ subsets $A_1,A_2, . . . ,A_k$ such that for all integers $n\ge 15$ and
all $i \in \{1, 2, . . . , k\}$ there exist two distinct elements of $A_i$ whose sum is $n$.
Hammer with tact.

Because destroying everything mindlessly isn't cool enough.

tanmoy
Posts:312
Joined:Fri Oct 18, 2013 11:56 pm
Location:Rangpur,Bangladesh

Re: Combi Marathon

Unread post by tanmoy » Sun Feb 19, 2017 10:19 pm

rah4927 wrote:Problem 1

Let $n > 3$ be a fixed positive integer. Given a set $S$ of $n$ points $P_1, P_2,\cdots, P_n$ in the plane such that no three are collinear and no four concyclic, let $a_t$ be the number of circles $P_i P_j P_k$ that contain $P_t$ in their interior, and let $m(S) = a_1 + a_2 +\cdots + a_n$. Prove that there exists a positive integer $f(n)$ depending only on $n$ such that the points of $S$ are the vertices of a convex polygon if and only if $m(S) = f(n)$.
Nice double counting problem. Here is my solution:
We will show that $\ f(n)=2\binom{n}{4}$ satisfies the problem's condition.

Let's define $m(S)$ in another way, let $m(S)$ be the number of pairs $(P_{t}, \ P_{i}P_{j}P_{k})$ so that $\ P_{t} \ $ lies interior of $(P_{i}P_{j}P_{k})$.

Let's take a $4-element$ subset $S_{a}=\{ P_{i}, \ P_{j}, \ P_{k}, \ P_{l} \}$ of the set $S$. $a_{x}$ is the number of circles among these $4$ points that contain $x$ in their interior. Take the convex hull of $S_{a}$. There are two cases:

Case (i):
The convex hull is a triangle. WLOG it is $\ P_{i}P_{j}P_{k}$. Then $a_{i}=a_{j}=a_{k}=0$ and $a_{l}=1$. In this case, $m(S)=1$.

Case (ii):
The convex hull is the quadrilateral $\ P_{i}P_{j}P_{k}P_{l}$. Now, from the problem's condition, $P_{i}P_{j}P_{k}P_{l}$ is not cyclic. Then WLOG, we may assume that $\angle P_{i}P_{j}P_{k}+\angle P_{k}P_{l}P_{i} < 180^{\circ} < \angle P_{j}P_{k}P_{l}+\angle P_{l}P_{i}P_{j}$. Then $a_{j}=a_{l}=0$ and $a_{i}=a_{k}=1$. In this case, $m(S)=2$.

From above, we see that for any $4-element$ subset of the set $S$, the maximum sum of $m(S)$ is $2$. There are $\binom{n}{4}$ such subsets. So, $m(S) \leq 2\binom{n}{4}$.

Now,$m(S) = 2\binom{n}{4}$ if and only if every four points of $S$ makes a convex quadrilateral, i.e. the points of $S$ determine a convex polygon. So, $\ f(n)=2\binom{n}{4}$ satisfies the problem's condition.
"Questions we can't answer are far better than answers we can't question"

User avatar
ahmedittihad
Posts:181
Joined:Mon Mar 28, 2016 6:21 pm

Re: Combi Marathon

Unread post by ahmedittihad » Mon Feb 20, 2017 3:59 pm

Solution to problem 2

We will show that $k=3$ is the greatest we can achieve.
Construction for $k=3$,
We let,
the first three terms of $A_1 = \{7,8,9\}$. The next terms are in the form of $3n+1$ where $n=\{3,4,5....\}$.
the first three terms of $A_2 = \{4,5,6\}$. The next terms are in the form of $3n+2$ where $n=\{3,4,5...\}$.
the first three terms of $A_3 = \{1,2,3\}$. The next terms are in the form of $3n$ where $n=\{4,5,6....\}$.

This construction indeed covers all integers more than $14$.
Now, we show that $k=3$ is the best we can do,
Assume that there is a partition for $k=4$.
We will add elements to $A_1$ to make sums of $15$, $16$, $17$....
To get $15$ in a partition, we need $A_1=\{a_1, 15-a_1\}$.
To get $16$ in a partition, we need \begin{align*}
A_1=&\{a_1, a_1+1, 15-a_1\}\\
\text{ or }&\{a_1, 15-a_1, 16-a_1\}
\end{align*}
To get $17$ in a partition, we need \begin{align*}
A_1=&\{a_1, a_1+1, 15-a_1, 16-a_1\}\\
\text{ or }&\{a_1, a_1+1, 15-a_1, 17-a_1\}\\
\text{ or }&\{a_1, a_1+1, a_1+2, 15-a_1\}\\
\text{ or }&\{a_1, 15-a_1, 16-a_1, 17-a_1\}\\
\text{ or }&\{a_1, a_1+2, 15-a_1, 16-a_1\}
\end{align*}
As there are $4$ partitions, all the numbers from $1$ to $16$ are used to get sum of $15, 16, 17$.

From casework, we get that the only possibility of $$\{A_1, A_2, A_3, A_4\}=\{\{1, 14, 15, 16\}, \{2, 3, 4, 13\}, \{5, 10, 11, 12\}, \{6, 7, 8, 9\}\}$$.
Here, we cannot add any numbers to the partitions to make them have sum $18$. We get a contradiction.
Frankly, my dear, I don't give a damn.

User avatar
ahmedittihad
Posts:181
Joined:Mon Mar 28, 2016 6:21 pm

Re: Combi Marathon

Unread post by ahmedittihad » Mon Feb 20, 2017 6:46 pm

Problem $3$
Let $n$ be a positive integer. At each of the $2n$ points around a circle we place discs with one white side and one black side. We may perform the following move: select a black disc and flip over its two neighbors. Find all initial configurations from which some sequence of moves leads to a position where all disc but one are white.
Frankly, my dear, I don't give a damn.

rubab
Posts:14
Joined:Wed Feb 19, 2014 3:20 pm

Re: Combi Marathon

Unread post by rubab » Mon Feb 20, 2017 10:12 pm

Solution to problem 3

We will show that all initial position with an odd number of black disks works.
First we show that the number of black disks must be odd.
Assign each of the black disks $-1$ and the white $1$. let M be the product of all of these numbers. M must be invariant since in each step we are changing sign of two numbers. And to have our desired position we must have M=-1 which is only possible when the number of black disks must be odd.

Now we show that if there is an odd number of black disks initially, we can have our desired position.

lemma: until we have our desired position there always exists two consecutive white disks between which there is an odd number of black disks.
Proof: Assume the opposite. So, between every pair of consecutive white disks there is an even number of black disk. That means total number of black disks must be an even number. Contradiction
.....................................................end of lemma....................................................

Now we use the following algorithm.
Choose two consecutive white disks between which there is an odd number of black disks. this is $WBB...BW$ (we are denoting white by W and black by B). number these black disks from left to right. Suppose that the number of $B's$ is $2m+1$. perform the sequence of move $(1,3,...,2m+1)$[here move $i$ means we are flipping over the 2 neighbor of $ith$ disk]. This can be easily checked that After this sequence of moves we get to the this position:$B...BB$. So the number of black disks is now $2m+3$. So, the number of black disks is increased by this process.
Continue this process until there is only one white disks. Our lemma ensue that we can do it.

Now we have the sequence of disks $(WBB...BW)$ (these are on a circle. so the first and last $W$ is same. there is only $1 W$.). Now number the $B's$ from left to right. Perform the sequence of moves $(2,4,...,2n-2)$ [there is 2n number of disks. one is $W$]. This can be easily checked that after this sequence of moves we have the sequence: $(WWB...BWW)$[again the first and last W is same.
So total number of W's is $3]$ thus we can reduce the number of black by $2$ at each step. Doing this repeatedly, We can get to our desired position at some time.
Last edited by rubab on Tue Feb 21, 2017 2:30 am, edited 1 time in total.

rah4927
Posts:110
Joined:Sat Feb 07, 2015 9:47 pm

Re: Combi Marathon

Unread post by rah4927 » Mon Feb 20, 2017 10:35 pm

ahmedittihad wrote:Problem $3$
Let $n$ be a positive integer. At each of the $2n$ points around a circle we place discs with one white side and one black side. We may perform the following move: select a black disc and flip over its two neighbors. Find all initial configurations from which some sequence of moves leads to a position where all disc but one are white.
Here is pretty much the same algorithm as @rubab above, but with a (different?) approach to getting the $011\cdots110$ block. Fix any $1$. Call this $A_1$. Number the rest of the board clockwise $A_2,...,A_{2n}$. Let $i$ be the least index with $A_i=0$. And let $j$ be the least index $j>i$ with $A_j=1$. Then since $A_i,A_{i+1},\cdots A_{j-1}$ are all $0$, we can always ensure $A_{i}=1$ by applying the operations on $A_j,A_{j-1},\cdots A_{i+1}$. This increases the length of our $111\cdots 1$ block by at least $1$. Keep doing this until you only have one $11\cdots1$ block and one $00\cdots0$ block. The rest of the algorithm is the same as @rubab.

rubab
Posts:14
Joined:Wed Feb 19, 2014 3:20 pm

Re: Combi Marathon

Unread post by rubab » Mon Feb 20, 2017 10:40 pm

Problem 4:

Each edge of a polyhedron is oriented with an arrow such that at each vertex, there is at least on arrow leaving the vertex and at least one arrow entering the vertex. Does there always exists two faces on the polyhedron such that the edges on each of it's boundary form a directed cycle?

rah4927
Posts:110
Joined:Sat Feb 07, 2015 9:47 pm

Re: Combi Marathon

Unread post by rah4927 » Tue Feb 21, 2017 12:32 am

rubab wrote:Problem 4:

Each edge of a polyhedron is oriented with an arrow such that at each vertex, there is at least on arrow leaving the vertex and at least one arrow entering the vertex. Does there always exists two faces on the polyhedron such that the edges on each of it's boundary form a directed cycle?
We are going to induct on the $E+V$ of the graph, where $E$ and $V$ are the number of edges and vertices respectively. Notice that in a polyhedron, every edge is shared by exactly two faces. Suppose faces $F_1$ and $F_2$ share edge $V_1V_2$. Now imagine a transformation that slowly shrinks this edge, while keeping the other vertices and edges intact. At one point, $V_1$ and $V_2$ will land on each other, let this new point be called $V'$. Notice that this transformation reduces $E+V$ by exactly $2$. So we are ready to induct on this. Let the new two faces be called $F_1'$ and $F_2'$ respectively.

To clear any confusion, if one of the two faces is a triangle (as in a tetrahedron), then after transformation, this face becomes a circle with two edges.

Assume there isn't a cycle on any face of the polyhedron.

Now fix vertex $V_1$. Suppose the it is connected to vertices $V_2,\cdots V_i$ of the polygon.

First shrink $V_1V_2$, as we have done before. Applying induction, some face has a cycle in it. If it is any face other than $F_1'$ and $F_2'$, we can simply reverse the transformation and claim we are done. So assume the cycle is in $F_1'$, without loss of generality. Call this cycle $C$. Now reverse the transformation.

In the face $F_1$, suppose $V_1$ is adjacent to $V_3$ ($V_3\neq V_2$).

Since we assumed there aren't any cycles, the direction of $V_1V_2$ must be in the opposite direction of the cycle $C$. WLOG, suppose the direction is from $V_1$ to $V_2$. The rest of the argument works even if the orientation is opposite, but this has been assumed for convenience of the proof. Then $V_1V_2$ and $V_1V_3$ must both be out-edges (edges that go out from $V_1$).

Now we repeat the entire argument by shrinking $V_1V_3$. The two faces this time are $F_1$ (since $V_1V_3$ is an edge of $F_1$) and call the other one $F_3$. Notice that after shrinking $V_1V_3$, $F_1$ will still not have a cycle. Therefore the new cycle must belong to $F_3'$. Now reverse the transformation. This tells us that the orientation of $A_1A_3$ must be opposite of the cycle. We already know that the orientation of this edge is $A_1\rightarrow A_3$.

Suppose in face $F_3$, $A_1$ is connected to $A_4$.

So the orientation of $A_1A_4$ must be $A_1\rightarrow A_4$.

Now once again repeat the argument by shrinking $A_1A_4$.

Notice that each time, the orientation of $A_1A_k$ is $A_1\rightarrow A_k$. But this contradicts the hypothesis that every vertex has both incoming and outgoing edges. We are done.

Finally, it is left to do the problem for one-dimensional faces as a base-case. This part is left to the reader.

Post Reply