Min Number of Subsets of Strictly Increasing

Art of Problem Solving

AoPS Online

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

No tags match your search

M

Min Number of Subsets of Strictly Increasing

G H J

Reveal topic tags

L

G H BBookmark kLocked kLocked NReply

Source: India EGMO TST 2025 Day 1 P1

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

29 posts

#1 h Dec 13, 2024, 8:24 AM • 4 Y

Y by Supercali, GeoKing, NO_SQUARES, radian_51

Let $n$ be a positive integer. Initially the sequence $0,0,\cdots,0$ ( $n$ times) is written on the board. In each round, Ananya choses an integer $t$ and a subset of the numbers written on the board and adds $t$ to all of them. What is the minimum number of rounds in which Ananya can make the sequence on the board strictly increasing?

Proposed by Shantanu Nene

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

729 posts

#2 h Dec 13, 2024, 8:57 AM • 2 Y

Y by GeoKing, radian_51

Answer is $\lceil log_2 n\rceil$ .
Construction: Consider the binary representations of numbers' rows' (Like the first number is $0\dots 01$ ). In the $i.$ turn, add $2^{\lceil log_2 n\rceil-i+1}$ to the numbers whose $i.$ digit is $1$ . At the end of this process, $i.$ number on the row will be $i$ .
Example for the Construction: $0,0,0,0,0,0,0\rightarrow 0,0,0,4,4,4,4\rightarrow 0,2,2,4,4,6,6\rightarrow 1,2,3,4,5,6,7$ .
Lower Bound: Suppose that $2^{k-1}<n\leq 2^k$ and one can make the sequence increasing in $k-1$ turns (if it can be done in less than $k-1$ moves, then one can add $1$ to the last number for several times). For each number among $\{1,2,\dots,2^{k-1}+a\}$ , consider the binary strings where $i.$ number for $x$ is $1$ iff a number is added to $x$ in $i.$ turn. Note that each binary string must be different. However there cannot be more than $2^{k-1}$ distinct binary strings with $k-1$ digits which results in a contradiction as desired. $\blacksquare$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1261 posts

#3 h Dec 14, 2024, 5:56 AM • 3 Y

Y by bin_sherlo, GeoKing, radian_51

My problem! This one went through many iterations in a short amount of time.

We claim that the minimum number of moves needed is $\lceil \log_2(n) \rceil$ .

To show that $\lceil \log_2(n) \rceil$ moves are enough, it is enough to prove that $0,0, \dots, 0$ (of length $2^k$ ) can be made strictly increasing in $k$ moves, and then restrict our attention to the first $n$ positions, where $2^{k-1}<n \leq 2^k$ . Indeed, write the positions in binary from $0$ to $2^k-1$ , and on move $i$ , increment the positions that have a $2^{k-i}$ in their binary expansions by $2^{k-i}$ . At the end we will end up with $0,1,2, \dots, 2^k-1$ .

Now we show that at least $\lceil \log_2(n) \rceil$ moves are needed. For any sequence $\mathbf{a}$ , let $f(\mathbf{a})$ be the length of the longest non-increasing (i.e., weakly decreasing) subsequence in $\mathbf{a}$ . Suppose after applying the move once, we get the sequence $\mathbf{b}$ . We claim that $f(\mathbf{b}) \geq \frac{f(\mathbf{a})}{2}$ . Indeed, look at the longest non-increasing subsequence in $\mathbf{a}$ . Then there is a subsequence $\mathbf{a'}$ of this subsequence, having length at least $\frac{f(\mathbf{a})}{2}$ , such that either all elements of $\mathbf{a'}$ were selected in the move or none of the elements were selected (by PHP). In any case, $\mathbf{a'}$ remains non-increasing after the move, which proves the claim.

Now, if $k$ moves turn the sequence of all zeros strictly increasing, then $1 \geq \frac{n}{2^k}$ (since longest non-increasing subsequence in any strictly increasing sequence has length $1$ ). Therefore $k \geq \log_2(n)$ , as required.

Bonus:
Suppose instead of all zeros, the initial sequence is some $a_1 \geq a_2 \geq \cdots \geq a_n$ . Now, in terms of $n$ and the $a_i$ , what is the minimum number of moves needed to make the sequence strictly increasing?

This post has been edited 2 times. Last edited by Supercali, Dec 16, 2024, 1:21 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1007 posts

#4 h Dec 14, 2024, 1:17 PM • 2 Y

Y by GeoKing, radian_51

Does this work? (for the original problem)

Claim: If answer for $n$ is $k$ then $2^k >= n$ , i. e. $k \ge \lceil log_2(n)\rceil$
Proof: Let's say we add $t_1, t_2, ..., t_k$ in some order. These when summed in some order can give us at most $2^k$ values, and since all values above are to be distinct, $2^k >= n$

Claim: $k = \lceil \log_2(n) \rceil$ works.
Proof: It suffices to show this for $n = 2^a$ , for which we give an inductive constructon.

$a = 0$ is obvious.
If you have a construction for $n = 2^a$ , split $n = 2^{a+1}$ into a left side and right side of $2^a$ each.
Do the required operations on both the left and right side simultaneously to make them increasing; then do an operation on the entire right half to make its smallest element larger than the left side's largest, and we're done.

This post has been edited 1 time. Last edited by AshAuktober, Dec 14, 2024, 1:17 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

113 posts

#5 h Dec 15, 2024, 12:34 PM • 2 Y

Y by GeoKing, radian_51

Headsolved by me and blessed by Nimloth149131215208 since there is a little of Nimloth149131215208 in all of us

Solution Sketch
The minimum is $\lceil \log_2(n) \rceil$ .

Construction: Just simple binary works. $\blacksquare$

Proof of bound: For a sequence $\textbf{a}$ , denote $\textbf{a}'$ as the after effect of applying the operation in some manner and denote $f(\textbf{a})$ as the length of the longest subsequence of $\textbf{a}$ that is non-increasing(constant also works). The key realisation(by PHP) is that $f(\textbf{a}')\ge \frac{f(\textbf{a})}{2}$ but that kills, indeed, if $k$ is the number of moves, we get that $\frac{n}{2^k}\le 1$ , as desired

Alternate proof of bound due to Nimloth149131215208: Say we applied $k$ operations such that the end result is a strictly increasing sequence. For each of the $n$ elements in the list, consider the subset of the $k$ operations that acted on it. The key realisation is that no two different elements are associated to the same subset since that would contradict injectivity of the final sequence, and thus $2^k\ge n$ , just as we desired.

This post has been edited 1 time. Last edited by quantam13, Dec 16, 2024, 2:53 AM
Reason: .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

60 posts

kotmhn

#6 h Apr 24, 2025, 1:23 PM

Y by

Solved with MathAssassin and Pi-oneer.

The minimum is $\lceil \log_2(n) \rceil$ .

Construction:
Binary search works $\blacksquare$

Proof of minimality:
To get the logarithmic bound, we need the inequation
$f(n) \ge f\left(\frac{n}{2}\right) + 1$ So perform whatever first move you wish to. Then if the set you picked has $\le \frac{n}{2}$ elements, then consider the complement of that set to get the result. Else we are just done. So we have a constant subsequence that has length $\frac{n}{2}$ , so it needs at least $f\left(\frac{n}{2}\right)$ moves to make it increasing. So the inequality holds, and we are done. $\blacksquare$
$QED$

This post has been edited 1 time. Last edited by kotmhn, Apr 28, 2025, 12:17 PM
Reason: i got to know the guy's aops

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a