BdMO Online Forum

$\text{Problem } 13$

Let $n$ be a positive integer, and let $A$ be a subset of $\{ 1,\cdots ,n\}$. An $A$-partition of $n$ into $k$ parts is a representation of n as a sum $n = a_1 + \cdots + a_k$, where the parts $a_1 , \cdots , a_k $ belong to $A$ and are not necessarily distinct. The number of different parts in such a partition is the number of (distinct) elements in the set $\{ a_1 , a_2 , \cdots , a_k \} $.
We say that an $A$-partition of $n$ into $k$ parts is optimal if there is no $A$-partition of $n$ into $r$ parts with $r<k$. Prove that any optimal $A$-partition of $n$ contains at most $\sqrt[3]{6n}$ different parts.

$\text{Solution to Problem 13}$

Lemma: Let $S$ be a set of $m$ integers. Let $T$ be the set of integers that can be written as a sum of $t$ distinct elements of $S$. Then $|T|\ge t(m-t)+1$.

Proof: Let $a_1<a_2<a_3<\ldots <a_m$ be the elements of $S$. Now, take the sum $a_1+a_2+\ldots +a_t$. Now, we define a move as taking the last number, and increase its indice by $1$. If its not possible because of crossing the limit of variables or overlapping of numbers, go to the second last and so on. It increases the value of the sum, and we can do $t(m-t)$ moves, from which the lemma follows.
Now, we tackle the original problem. Let there be an optimal partition for some $n,A,k$ as stated in the question. Let $|A|=m$. Now, take $t$ distinct element of $A$ and find there sum. All such numbers form the set $A_t$. Now, because of the definition, $n$ doesn't belong to any of the sets $A_1, A_2, A_3,\ldots A_{k-1}$. If two of them have different size but an element that is the same, we run into a contradiction if we substract the numbers with bigger size and add the numbers with small size. So each of them together can at least cover $|A_1|+|A_2|+|A_3|+\ldots +|A_{k-1}|$ integers. So we have $n\ge |A_1|+|A_2|+|A_3|+\ldots +|A_{k-1}|\ge 1(m-1)+1+2(m-2)+1+3(m-2)+1$ $+\ldots +(k-1)(m-k+1)+1=m(1+2+3+\ldots k-1)-(1^2+2^2+3^2+\ldots (k-1)^2)$ $+k-1\ge \dfrac{k(k-1)(3m-2k+1)}{6}\ge\dfrac{k(k-1)(3k-2k+1)}{6}+k-1=\dfrac{k^3+5k-6}{6}>\dfrac{k^3}{6}$ for $k>1$. The $k=1$ case is trivial.

Now, $n>\dfrac{k^3}{6}\Rightarrow k<\sqrt[3]{6n}$.

$\text{Problem 14:}$

There are $ n + 1$ cells in a row labeled from $ 0$ to $ n$ and $ n + 1$ cards labeled from $ 0$ to $ n$. The cards are arbitrarily placed in the cells, one per cell. The objective is to get card $ i$ into cell $ i$ for each $ i$. The allowed move is to find the smallest $ h$ such that cell $ h$ has a card with a label $ k > h$, pick up that card, slide the cards in cells $ h + 1$, $ h + 2$, ... , $ k$ one cell to the left and to place card $ k$ in cell $ k$. Show that at most $ 2^n - 1$ moves are required to get every card into the correct cell and that there is a unique starting position which requires $ 2^n - 1$ moves. [For example, if $ n = 2$ and the initial position is 210, then we get 102, then 012, a total of 2 moves.]

Well that was pretty easy

$\text{Solution to Problem 14}$

We prove that at most $2^n-1$ moves are required by, you guessed it, induction.

We follow the problem's definition for $k$ and $h$. We denote the label of the card on cell $i$ by $c(i)$

Lemma 0: For all cells $i$ with $i<h$, $c(i)=i$.

Since $h$ is the smallest number such that $c(h)>h$, for $i<h$ we have $c(i) \leq i$. Suppose $j$ is the smallest integer such that $c(j) < j$. Obviously $j \neq 0$. And since for $i<j$ we have $c(i)=i$, so we must have $c(c(j)) = c(j)$. But $c(j)$ can't be the card label for both cell $j$ and $c(j)$, a contradiction! Thus the lemma is proved.

Let the number of the card in cell $n$ at the starting position be $l$.

Lemma 1: The card in cell $n$ changes at most once, from card $l$ to card $n$

At any given move, only the cards in cells $h, h+1, \dots, k$ change position. So if cell $n$ changes, we must have $k=n$. This happens first when card $c(h) = n$. After this we have $c(n)=n$, so $k=n$ is impossible since the card on cell $n$ hasn't changed. Thus the card in cell $n$ changes at most once, when card $c(h) = n$

Now we prove the original problem by induction on $n$. The base case $n=0$ is trivial. Suppose the statement holds for $n-1$.

Now for a starting position where $l=n$, we can ignore the last cell since it remains unchanged throughout. Then we only have the first $n-1$ cells rearranging, which is equivalent to a starting position for $n-1$ that'll require at most $2^{n-1} - 1$ moves. Then we are done.

So we consider the case where $l<n$. Consider the starting position for $n-1$ with all of the cards on cells $0, 1, \dots , n-1$ corresponding to what we have in the starting position for $n$, with the card labeled $n$ standing in for the card labeled $l$. Now, the card labeled $n$ will eventually reach the cell $l$ by either being shifted right, or at some point $c(h)=n$ being true . Even if card $n$ reaches cell $l$ by shifting right, within the first $2^{n-1}-1$ moves we will have $c(i)=i$ for all $i<l$, and then we will have $c(h)=n$. Thus, we have $c(h)=n$ within the first $2^{n-1}-1$ moves. Then we have card $n$ move to cell $n$ in one move, and we can ignore the last cell since it remains unchanged throughout. Then we only have the first $n-1$ cells rearranging, which is equivalent to a starting position for $n-1$ that'll require at most $2^{n-1} - 1$ moves. So the total number of moves required is $ < 2^{n-1}-1 + 1 + 2^{n-1}-1 = 2^n -1$. (QED)

$\text{Problem 15}$

You and your sister have inherited a necklace, which is a linear string of $n$ different types of gemstones with an even number of stones of each type. You want to cut the necklace at some points so that you may distribute the pieces to yourself and your sister with everyone getting an equal number of gemstones of each type. What is the minimum value of $k$ for which, whatever the number of gemstones of each type or the arrangement of gemstones, you can divide a necklace of $n$ types of gemstones in $k$ cuts?

Solution $\boxed{15}$

Suppose $a_1,...,a_n$ are the number of gems of each type. If they are arranged serially like, all $a_1$ gems of type $1$ at first, all $a_2$ gems of type $2$ next, and so on till gems of type $n$, then clearly we'll need $n$ cuts to split evenly (each cut at the middle of each of the $n$ groups). So $k\ge n$.

The fact that $k\le n$ is a well-known result by Alon and West (proposition 2.1). $\square$

(A beautiful explanation of the approach in the paper: here.)

Problem $\boxed{16}$

Given a connected graph $G=(V,E)$ such that $\deg u\le d$ for all $u\in V$. Prove that there exists a partition of $G$ into two connected subgraphs each with at least $(|V|-1)/d$ vertices.

Nirjhor wrote:Solution $\boxed{15}$

Suppose $a_1,...,a_n$ are the number of gems of each type. If they are arranged serially like, all $a_1$ gems of type $1$ at first, all $a_2$ gems of type $2$ next, and so on till gems of type $n$, then clearly we'll need $n$ cuts to split evenly (each cut at the middle of each of the $n$ groups). So $k\ge n$.

The fact that $k\le n$ is a well-known result by Alon and West (proposition 2.1). $\square$

(A beautiful explanation of the approach in the paper: here.)

Problem $\boxed{16}$

Given a connected graph $G=(V,E)$ such that $\deg u\le d$ for all $u\in V$. Prove that there exists a partition of $G$ into two connected subgraphs each with at least $(|V|-1)/d$ vertices.

This is the popular graph balancing problem found in Adrian Tang's sheet here. Pick the vertex with minimal $f$ and divide into two subgraphs. We are done.

Problem 17
Let $n$ be a positive integer. Prove that the edges of the complete graph on $n$ vertices can be
decomposed into $n-1$ paths of lengths $1$, $2$,.....,$n-1$.

Solution of problem17

If n is odd then the graph has an eularian path. Since the total number of edges is $1+2+...+n-1$, we can divide the eularian path into path of size $1,2,...,n-1$.
Now if n is even then we use induction. In base case, when n=2, it is obvious. Now, suppose that the statement is true for n=k for some even $k\geq2$. When n=k+2 we choose a complete subgraph with any k vertices. By induction hypothesis, we can find paths of sizes $1,2,...,k-1$ from this subgraph. Now consider the complement graph of this subgraph. This has two vertices having odd degree. So, by a well-known theorem, this graph has an eularian path. Again we can divide this path into paths of size $k,k+1$.
Q.E.D.

The correctness of this proof depends on the definition of a path. This proof doesn't work if a path is defined to not have loops.