Search Results

Motivation. Suppose we are given $6$ boxes, arranged in the following manner: $$\left[\begin{array}{ccc} 1 & 2 & 3 \\ 4 & 5 & 6 \end{array}\right]$$ Two of these boxes contain a present, and the rem …

We say that a family ${\cal S}\subseteq{\cal P}(\mathbb{N})$ is bijection-dodging if there is a bijection $\varphi:\mathbb{N}\to\mathbb{N}$ with $\varphi(T)\notin {\cal S}$ for all $T\in{\cal S}$. Gi …

For any set $X$, let $\newcommand{\N}{\mathbb{N}}[X]^2 = \big\{\{x,y\}:x\neq y \in X\big\}$ and set $[n]^2 = [\{0,\dotsc,n-1\}]^2$ for any positive integer $n$. For $A\subseteq [\N]^2$ we set $$\newco …

Let $\mathbb{N}$ denote the set of non-negative integers. We say $A\subseteq \mathbb{N}$ is a finite arithmetic progression if there are $a, n, d\in\mathbb{N}$ with $d \geq 1$ and $n \geq 2$ such that …

Let $S_k$ be the group of permutations $\pi:\{1,\ldots,k\} \to \{1,\ldots,k\}$ for any positive integer $k$. …

Motivation. I am trying to make an interesting infinite version out of this fascinating problem from the Russian mathematical olympiad: There are $c$ flavours of cookies, we are given $n$ cookies of …

Let $S_n$ be the collection of bijections $\varphi:\{1,\ldots,n\}\to \{1,\ldots,n\}$. In an earlier question, the insert-and-shift graph structure was introduced on $S_n$ and the resulting graph is ca …

Let $S_n$ be the collection of all permutations of $[n]$ and let $\pi\neq \psi \in S_n$ form an edge if there are $s\in [n-1]$ and $t\geq s+2$ such that $\pi = \sst \circ \psi$ or $\psi = \sst \circ \pi …

By $\FF_n$ we denote the collection of fixed-point-free permutations $\pi:\n\to\n$. For any $\pi \in \FF_n$ we let $\lc(\pi)$ be the lengh of the longest cycle of $\pi$. …

This is a strengthening of an older question. Is there a positive integer $c_0$ with the following property? For every integer $n\geq c_0$ there is a function $f:\{0,1\}^{c_0}\to\{0,1\}$ such that th …

Motivation. This weekend I was playing the pair-matching game Memory (also called Concentration in other parts of the world) against my youngest son, and wondered about what constitutes a "good shuffl …

For any $A\subseteq \mathbb{N}$ we let the (lower) density of $A$ be defined by $$d(A) = \liminf_{n\to\infty}\frac{|A\cap\{0,\ldots,n\}|}{n+1}.$$ If $\pi:\mathbb{N}\to\mathbb{N}$ is a permutation (bij …

Let $S_\omega$ be the group of permutations (bijections) $\varphi:\omega\to\omega$, together with composition as binary operation. …

This question is motivated by Linear Feedback Shift Registers, which cycle through $\{0,1\}^n \setminus \{(0,\ldots,0)\}$ by shifting and applying a small set of XOR operations. Let $n>1$ be an intege …

For $n\in \mathbb{N}$ let $S_n$ denote the set of permutations (bijections) $\pi: \{0,\ldots,n-1\}\to \{0,\ldots,n-1\}$. …