Nonnegative integer sequence containing floor(k/2^m)?

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

Nonnegative integer sequence containing floor(k/2^m)?

G H J

Reveal topic tags

L

G H BBookmark kLocked kLocked NReply

Source: ELMO 2024/4

The post below has been deleted. Click to close.

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

polishedhardwoodtable

130 posts

polishedhardwoodtable

#1 h Jun 21, 2024, 4:23 PM • 3 Y

Y by ehuseyinyigit, OronSH, ihatemath123

Let $n$ be a positive integer. Find the number of sequences $a_0,a_1,a_2,\dots,a_{2n}$ of integers in the range $[0,n]$ such that for all integers $0\leq k\leq n$ and all nonnegative integers $m$ , there exists an integer $k\leq i\leq 2k$ such that $\lfloor k/2^m\rfloor=a_i.$

Andrew Carratu

Z K Y

The post below has been deleted. Click to close.

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

1540 posts

#2 h Jun 21, 2024, 4:27 PM • 3 Y

Y by VicKmath7, shafikbara48593762, MS_asdfgzxcvb

We claim there are $2^n$ such sequences.
Define the $k$ -interval as $\{a_k, a_{k+1}, \dots, 2k\}$ . Then the condition requires that $k, \left\lfloor \frac{k}{2} \right\rfloor, \dots$ are in the $k$ -interval. Call these the lamps for $k$ .

Claim: We induct on the following claims:

Each $k$ -interval consists of all integers $\{0, 1, \dots, k\}$ .
$\{a_{2k-1}, a_{2k}\} = \{a_{k-1}, k\}$
$a_{k-1}$ is a lamp for $k$ .

Proof. We prove this inductively. The base case of $k = 0, 1$ works.
Now, we show that $a_{k-1}$ is a lamp for $a_k$ . Suppose that $k$ is even. Then we get that $\{a_{k-1}, a_{k}\} = \{a_{\frac{k}{2}-1}, \frac{k}{2}\}$ , and note that $a_{\frac{k}{2}-1}$ is a lamp for $\frac{k}{2}$ which is a lamp for $\frac{k}{2}$ which implies the result.
Likewise, if $k$ is odd, we consider $\{a_{k-1}, a_{k-2}\} = \{\frac{k-1}{2}, a_{\frac{k-1}{2}-1}\}$ which are both lamps for $k$ . As such, since the $a_{k-1}, \dots, a_{2k-2}$ contains $a_k$ exactly once, we get that $a_k, \dots, a_{2k-2}$ doesn't contain $a_k$ . It also can't contain $k$ . Since $a_k$ and $k$ are lamps for $k$ , $a_k, \dots, a_{2k}$ must contain them, which implies that $a_{2k-1, a_{2k}} = \{a_{k-1}, k\}$ . Then we get that $\{a_k, \dots, a_{2k}\} = \{a_{k-1}, \dots, a_{2k-2}, k\} = \{0, \dots, k\}$ for the third claim. $\blacksquare$
Notably, we also have that if $\{a_{2k-1}, a_{2k}\} = \{a_{k-1}, k\}$ and $a_0, \dots, a_{2k-2}$ is a valid sequence, then $a_0, \dots, a_{2k}$ is a valid sequence.
This constraint gives us $2^n$ total options for building up $a_0, \dots, a_{2k}$ by first choosing $\{a_1, a_2\}$ and so forth.

Z K Y

The post below has been deleted. Click to close.

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

Usernumbersomething

62 posts

Usernumbersomething

#3 h Jun 23, 2024, 6:54 AM

Y by

See https://artofproblemsolving.com/community/c6h44479p281572 for something similar. I feel like this problem is like a more accessible version of the 2005 IMO problem.

This post has been edited 3 times. Last edited by Usernumbersomething, Jun 23, 2024, 4:03 PM

Z K Y

The post below has been deleted. Click to close.

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

821 posts

#4 h Sep 2, 2024, 10:36 PM • 1 Y

Y by Rajukian

Answer: $2^n$ . The key claim is the following:

Claim: $a_k, \dots, a_{2k}$ is a permutation of $(0,1, \dots, k)$ for all $k\leq n$ .
Proof. We strong induct on $n$ . The base cases of $k=1$ and $k=2$ can be checked.
Now, we know that $a_{k-1}, \dots, a_{2k-2}$ is a permutation of $(0,\dots, k-1)$ . Thus $a_k, \dots, a_{2k-2}$ are not $k=\lfloor k/2^0\rfloor$ , so $a_{2k-1}$ or $a_{2k}$ is $k$ . It suffices to show that $a_{k-1}$ appears in $a_k, \dots, a_{2k}$ or $a_{k-1}=a_{2k-1},a_{2k}$ . By our inductive hypothesis and the reasoning above, $\{a_{2l-1}, a_{2l}\} = \{a_{l-1},l\}$ for $l<k$ .

Let $j=\lfloor k/2\rfloor$ . Thus $\{a_{2j-1},a_{2j}\}=\{a_{j-1},j\}$ . Also, $k-1=2j-1$ or $2j$ by the floor definition of $k$ . Thus $a_{k-1}=a_{j-1}$ or $k$ . If $a_{k-1}=j$ , then since $\lfloor k/2\rfloor = a_j$ must appear in $a_k, \dots, a_{2k}$ we conclude. Else, $a_{k-1}=a_{j-1}$ . We can repeat the same argument to find $a_{j-1}=\lfloor j/2\rfloor$ or $a_{\lfloor j/2\rfloor -1}$ . Repeat this inductively to get $a_{k-1}=\lfloor k/2^m\rfloor$ for some $m$ . Thus $a_{k-1}$ is in $a_k, \dots, a_{2k}$ and the claim is proven. $\blacksquare$

To finish, repeatedly applying the claim gives $a_0=0$ and $i \in \{a_{2i-1}, a_{2i}\}$ . Now, I claim the answer is $2^n$ . This is from choosing which of $a_{2i-1}, a_{2i}$ is $i$ . It suffices to show each choice gives a unique sequence. This is true by applying the claim on $1$ through $n$ to get the other number in each pair.

Z K Y

The post below has been deleted. Click to close.

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

6877 posts

#5 h Oct 26, 2024, 1:19 AM • 2 Y

Y by Amkan2022, Rajukian

Solution from Twitch Solves ISL:

The answer is $2^n$ . We note $a_0=0$ and ignore it going forward, focusing only on $a_i$ for $i \ge 1$ .
In what follows, for each positive integer $t$ we let $D(t) \coloneqq \left\{ t, \left\lfloor t/2 \right\rfloor, \left\lfloor t/4 \right\rfloor, \dots \right\}.$ For example, $D(13) = \{13, 6, 3, 1, 0\}$ . Then the problem condition is equivalent to saying that every element of $D(k)$ appears in $\{a_k, \dots, a_{2k}\}$ .
We prove the following structure claim about all the valid sequences.
Claim: In any valid sequence, for each $0 \le k \le n$ ,

$a_{2k-1}$ and $a_{2k}$ are elements of $D(k)$ ; and
$a_k$ , \dots, $a_{2k}$ consist of all the numbers from $0$ to $k$ each exactly once.

Proof. We proceed by induction; suppose we know it's true for $k$ and want it true for $k+1$ . By induction hypothesis:

$\{a_k, \dots, a_{2k}\}$ contains each of $0$ to $k$ exactly once;
$a_k$ is an element of $D(\left\lceil k/2 \right\rceil)$ ;
We also know $\{a_{k+1}, \dots, a_{2k+2}\}$ contains all elements of $D(k+1)$ by problem condition.

However, note that $D\left( \left\lceil k/2 \right\rceil \right) \subseteq D(k+1)$ so that means either $(a_{2k+1} = a_k \text{ and } a_{2k+2} = k+1) \quad\text{OR}\quad (a_{2k+1} = k+1 \text{ and } a_{2k+2} = a_k).$ $\blacksquare$
We return to the problem of counting the sequences. It suffices to show that if $(a_0, \dots, a_{2n})$ is a valid sequence, there are exactly two choices of ordered pairs $(x,y) \in \{0, \dots, n+1\}$ such that $(a_0, \dots, a_{2n}, x, y)$ is a valid sequence. However, the structure claim above implies that $\{x,y\} = \{a_n, n+1\}$ , so there are at most two choices. Moreover, both of them work by the structure claim again (because $k=n=1$ is the only new assertion when augmenting the sequence, and it holds also by the structure claim). This completes the proof.

Remark: Here are some examples to follow along with. When $n=4$ the $16$ possible values of $(a_4, a_5, a_6, a_7, a_8)$ are $\begin{array}{cc} (2,1,3,4,0) & (2,0,3,4,1) \\ (2,1,3,0,4) & (2,0,3,1,4) \\ (0,1,3,4,2) & (1,0,3,4,2) \\ (0,1,3,4,2) & (1,0,3,4,2) \\ (0,1,3,2,4) & (1,0,3,2,4) \\ (2,3,1,4,0) & (2,3,0,4,1) \\ (2,3,1,0,4) & (2,3,0,1,4) \\ (0,3,1,4,2) & (1,3,0,4,2) \\ (0,3,1,2,4) & (1,3,0,2,4) \\ \end{array}$ Now the point is that when moving to $n=5$ , the element $a_4 \in \{0,1,2\} = D(2) \subseteq D(5)$ is chopped-off, and $a_9$ and $a_{10}$ must be $5$ and the chopped-off element in some order. So each of these sequences extends in exactly two ways, as claimed.

This post has been edited 1 time. Last edited by v_Enhance, Oct 26, 2024, 1:20 AM

Z K Y

The post below has been deleted. Click to close.

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

1301 posts

#6 h Dec 5, 2024, 4:12 AM • 1 Y

Y by GeoKing

The answer is $2^n$ .

Clearly $a_0=0$ , and $\{a_1,a_2\} = \{0,1\}$ .

The key structural claim is that $\{a_{2k-1},a_{2k}\} = \{a_{k-1},k\}$ , call $P(k)$ . It is clearly true for $k=1$ .

Note that one can show $P(1),P(2),\cdots,P(k)$ imply $(a_k,\cdots,a_{2k})$ is a permutation of $\{0,\cdots,k\}$ via induction. Furthermore, $P(1),\cdots,P(k-1)$ and $\{a_k,\cdots,a_{2k}\}$ being permutation of $\{0,\cdots,k\}$ imply that $\{a_{2k-1},a_{2k}\} = \{a_{k-1},k\}$ , because I remove $a_{k-1}$ , add $a_{2k},a_{2k-1}$ , and end up just adding $k$ to the set.

I will use $P(1),\cdots,P(k-1)$ to show $\{a_k,\cdots,a_{2k}\}\supset\{0,\cdots,k\}$ , which suffices. Let $x \in \{0,\cdots,k\}$ . If $x=k$ we are done, since the problem condition tells us that $\{a_k,\cdots,a_{2k}\} \supset \left\{x,\lfloor \frac x2\rfloor, \cdots, \lfloor \frac{x}{2^m}\rfloor, \cdots, 1,0\right\}. (*)$
Henceforth assume $x<k$ . Then by $P(x)$ , we have $x \subset \{a_{2x+1},a_{2x+2}\}$ .

By $P(2x+1),P(2x+2)$ , if $2x+2 < k$ we have $\{a_{2x+1},a_{2x+2} \} \subset \{a_{4x+3},\cdots,a_{4x+6}\}$ .

(If $2x+1\ge k$ then we also have $\{a_{2x+1},a_{2x+2}\}\subset \{a_k,\cdots,a_{2k}\}$ since $x<k$ . If $2x+2=k$ then we have $\{a_{2x+1},a_{2x+2} \} = \{a_k, a_{2k-1},a_{2k}\}$ by $P(k-1)$ )

We iterate the inductive step. Set a counter $e=2$ . At each $e$ we have a set $\{a_{2^ex + (2^e-1)}, \cdots, a_{2^ex + 2^{e+1}-2}\}$ containing $x$ , and we want to show it is contained in $\{a_k,\cdots,a_{2k}\}$ . If $2^ex + 2^{e+1}-2 < k$ then by inductive hypothesis on $2^ex+(2^e-1)$ to $2^ex + (2^{e+1}-2)$ we have

$\{a_{2^ex + (2^e-1)}, \cdots, a_{2^ex + 2^{e+1}-2}\} \subset \{ a_{2(2^ex + (2^e-1))+1}, a_{2(2^ex + (2^e-1))+2}, \cdots, a_{2(2^ex + (2^{e+1}-2))+1}, a_{2(2^ex + (2^{e+1}-2))+2} \} = \{a_{2^{e+1}x + (2^{e+1}-1)}, \cdots, a_{2^{e+1}x + 2^{e+2}-2}\}$
Thus we set $e \leftarrow e+1$ . Otherwise, $2^ex + 2^{e+1}-2\ge k$ , so $2^ex + (2^e-1) > \frac 12 (2^ex + 2^{e+1}-2) \ge \frac k2$ . For everything from $2^ex + 2^e-1$ to $k-1$ (possibly there is nothing there) I apply inductive hypothesis, so this ends up giving us a subset of $\{a_k,\cdots,a_{2k}\}$ . This proves $P(k)$ , as desired.

Since the only restrictions we have are $\{a_{2k-1},a_{2k}\} = \{a_{k-1},k\}$ , given any $a_0,\cdots,a_{2k-2}$ there are 2 choices for $(a_{2k-1},a_{2k})$ . We make $n$ such choices so the answer is $2^n$ .

Z K Y

The post below has been deleted. Click to close.

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

awesomeming327.

1711 posts

awesomeming327.

#7 h Jan 27, 2025, 4:23 AM

Y by

Let the $k$ -set be the set of all nonnegative integers that can be the result of
$\left\lfloor\frac{k}{2^m}\right\rfloor$ for some nonnegative integer $m$ . For example, the $5$ -set is $\{5,2,1,0\}$ .

Let $f(n)$ be the desired answer. We will show that $f(n)=2^n$ . First, note that $f(0)=1$ is clear because the $0$ -set, $\{0\}$ , is a subset of $\{a_0\}$ , implying that $a_0=0$ . $f(1)=2$ because the $1$ -set, $\{1,0\}$ , is a subset of $\{a_1,a_2\}$ on top of the fact that $a_0=0$ , so both $(0,0,1)$ and $(0,1,0)$ work.

We now work recursively, showing that $f(n)=2f(n-1)$ for all $n\ge 2$ . Drop the condition that the sequence's terms are in $[0,n]$ . We will inductively show that this is forced anyway.

It suffices to show that there are exactly $2$ ways to select $a_{n-1}$ and $a_n$ , because $\{a_{2n-1},a_{2n}\}$ is determined, for any selection of $a_1$ , $a_2$ , $\dots$ , $a_{2n-2}$ that satisfies the conditions for $0\le k\le n-1$ .

Claim 1:

For any sequence that is a solution to the $n-1$ problem, $a_1$ , $a_2$ , $\dots$ , $a_{2n-2}$ , we have that the values $a_{n},a_{n+1},\dots,a_{2n-2}$ contain all but two values from the $n$ -set.
$a_{2n-1}$ and $a_{2n}$ are both in the $n$ -set.
$a_{2n-1}$ and $a_{2n}$ are different from everything in $a_{n},a_{n+1},\dots,a_{2n-2}$ .

We proceed with strong induction, where the base case has already been proved above. Clearly, since $n$ is not in any $k$ -set for $k<n$ , $a_{n},a_{n+1},\dots,a_{2n-2}$ does not contain $n$ . Since $a_{n-1}$ is in the $\lfloor n/2\rfloor$ -set, it is in the $n$ -set. By the Inductive Hypothesis, $a_{n},a_{n+1},\dots,a_{2n-2}$ are all different from $a_{n-1}$ . Thus, the first part of the claim is proved. The next two parts follow naturally because $a_{2n-1},a_{2n}$ must be the two remaining values.

We are done.

This post has been edited 1 time. Last edited by awesomeming327., Jan 27, 2025, 4:23 AM

Z K Y

The post below has been deleted. Click to close.

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

575 posts

#8 h Apr 19, 2025, 1:08 AM

Y by

For some fixed $k$ let the set $f(x)$ be the range of values $\left \lfloor \frac{k}{2^m} \right \rfloor$ can attain as $m$ varies. A key observation is that $f(\lfloor x/2 \rfloor) = f(x) /\{x\}.$ Note that $a_0=0.$ We prove the following proposition by induction on $k$ :

For all $k \geq 1,$ $\{a_k, a_{k+1}, \cdots, a_{2k}\}$ is a permutation of $\{0, 1, 2, \cdots, k\},$ and $a_{2k}, a_{2k-1} \in f(k).$

The base case $k=1$ is trivial. Now assume that the proposition holds for some $k.$ Then for $k+1,$ observe that as $\{a_k, a_{k+1}, \cdots, a_{2k}\}$ is a permutation of $\{0, 1, 2, \cdots, k\}$ one of $a_{2k+1}, a_{2k+2}$ equals $k+1 \in f(k+1).$ Meanwhile $a_{k} \in f(\lceil k/2 \rceil) = f(\lfloor (k+1)/2 \rfloor) = f(k+1)/\{k+1\}.$ so as $a_{k+1}, a_{k+2}, \cdots, a_{2k}$ are distinct from $a_k$ we have that one of $a_{2k+1}, a_{2k+2}=a_k \in f(k+1).$ Thus as $a_k \neq k+1$ it follows that $\{a_{2k+1}, a_{2k+2}\} = \{k+1, a_k\} \subseteq f(k+1).$ We can also see from here that $\{a_{k+1}, a_{k+2}, \cdots, a_{2k+2}\}$ is a permutation of $\{0, 1, 2, \cdots, k+1\}.$ So the induction is complete.

Now from above we can induct to show that the answer is $\boxed{2^n},$ essentially for every next $\{a_{2k+1}, a_{2k+2}\} = \{a_k, k+1\}$ there are two possible ways to assign them.

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a