Let $a_1,a_2,\cdots$ be a strictly increasing sequence on positive integers. Is it always possible to partition the set of natural numbers $\mathbb{N}$ into infinitely many subsets with infinite cardinality $A_1,A_2,\cdots$, so that for every subset $A_i$, if we denote $b_1<b_2<\cdots$ be the elements of $A_i$, then for every $k\in \mathbb{N}$ and for every $1\le i\le a_k$, it satisfies $b_{i+1}-b_{i}\le k$?
Problem
Source: own. For APMC 2016 #3
Tags: combinatorics
aopser123
09.01.2017 02:12
Bump Bump
dgrozev
09.01.2017 18:03
Yes, it's possible. The proof is constructive, every sequence entering at some point on, when the previous ones gather some "magnitude". One may imagine we consecutively mark the natural numbers with colors $A_i$. Suppose we've already marked some segment of the natural numbers $[1,N]$ with $A_1,A_2,\dots,A_k$, such that $N, N-1, \dots, N-k+1$ are marked resp. with $A_k, A_{k-1},\dots,A_1$. Suppose also the next member of each $A_i,i=1,\dots,k$ can be at distance at least $m$ from the previous one, where the value of $m$ will be assigned later. We begin to mark $N+1,N+2, \dots$ with color $A_{k+1}$, till the max allowed next distance of $A_{k+1}$ become at least $k+1$. Let at the moment it's satisfied, $N+N_1$ be the last colored with color $A_{k+1}$. Now, going back, we choose $m$ with $m>\max(N_1, k+1)$. Further, the next marked numbers will be respectively with colors: $A_1,A_2,\dots,A_k, A_{k+1}$, repeating this pattern again some times to ensure the max allowed distance of each $A_i, i=1,\dots, k+1$ be at least the "next" $m$. Then we stop and it's the initial configuration for the next step.
Dianademon
12.08.2021 18:12
dgrozev wrote: Yes, it's possible. The proof is constructive, every sequence entering at some point on, when the previous ones gather some "magnitude". One may imagine we consecutively mark the natural numbers with colors $A_i$. Suppose we've already marked some segment of the natural numbers $[1,N]$ with $A_1,A_2,\dots,A_k$, such that $N, N-1, \dots, N-k+1$ are marked resp. with $A_k, A_{k-1},\dots,A_1$. Suppose also the next member of each $A_i,i=1,\dots,k$ can be at distance at least $m$ from the previous one, where the value of $m$ will be assigned later. We begin to mark $N+1,N+2, \dots$ with color $A_{k+1}$, till the max allowed next distance of $A_{k+1}$ become at least $k+1$. Let at the moment it's satisfied, $N+N_1$ be the last colored with color $A_{k+1}$. Now, going back, we choose $m$ with $m>\max(N_1, k+1)$. Further, the next marked numbers will be respectively with colors: $A_1,A_2,\dots,A_k, A_{k+1}$, repeating this pattern again some times to ensure the max allowed distance of each $A_i, i=1,\dots, k+1$ be at least the "next" $m$. Then we stop and it's the initial configuration for the next step. why i think is impossible.
navi_09220114
27.02.2022 03:33
It is actually possible
AshAuktober
23.04.2024 16:36
VIDEO GAME FROGZZZZZ
(this is, no joke, the visualisation for the solution. Consider jumping frogs which can upgrade their jump distance after some a_k time, and which only move forward)