Finite and infinite barrycades
Abstract
An n-barrycade of height h is a set of h permutations of [n] such that all the prefix sums are different. This notion was described in 2020 by Richard Guy, together with the central problem to determine for which values of n there exists a break-free n-barrycade, that is, one in which every possible prefix sum from $1$ to (n(n+1))/2−1 is covered. The height of such barrycade would be (n+2)/2. We prove that barrycades of linear height exist for infinitely many sizes: there is a constant c>0 such that for infinitely many positive integers n there exists an n-barrycade of height at least cn. We also explore an infinite variant of the problem and propose three constructions -- greedy, grasshopper and precise grasshopper -- that give increasingly more satisfying results. Along the way we encounter new integer sequences and formulate conjectures concerning omitted elements, missing partial sums, and word representations of infinite barrycades, which are firmly supported by computational data.
Related
- A groupoid model for Rørdam's finite-infinite C*-algebra
- The Almost Finite--Purely Infinite Dichotomy for Minimal Amenable Ample Groupoids
- BIBO stability in infinite dimensions: extensions and limitations of finite-dimensional theory
- Vector- and operator-valued backward stochastic equations with finite-variation drivers and a maximum principle for singular stochastic control in infinite dimensions
- Boundary phenomena for slow recurrences:finite and infinite critical sets
BibTeX
@misc{debski2026finite,
title = {{Finite and infinite barrycades}},
author = {Michał Dębski and Jarosław Grytczuk and Paweł Naroski and Bartłomiej Pawlik and Jakub Przybyło and Małgorzata Śleszyńska-Nowak},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.18476},
eprint = {2609.18476},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.18476},
}
RIS
TY - UNPB
TI - Finite and infinite barrycades
AU - Michał Dębski
AU - Jarosław Grytczuk
AU - Paweł Naroski
AU - Bartłomiej Pawlik
AU - Jakub Przybyło
AU - Małgorzata Śleszyńska-Nowak
PY - 2026
DA - 2026/09/27
PB - arXiv
DO - 10.48550/arxiv.2609.18476
UR - https://arxiv.org/abs/2609.18476
AB - An n-barrycade of height h is a set of h permutations of [n] such that all the prefix sums are different. This notion was described in 2020 by Richard Guy, together with the central problem to determine for which values of n there exists a break-free n-barrycade, that is, one in which every possible prefix sum from $1$ to (n(n+1))/2−1 is covered. The height of such barrycade would be (n+2)/2. We prove that barrycades of linear height exist for infinitely many sizes: there is a constant c>0 such that for infinitely many positive integers n there exists an n-barrycade of height at least cn. We also explore an infinite variant of the problem and propose three constructions -- greedy, grasshopper and precise grasshopper -- that give increasingly more satisfying results. Along the way we encounter new integer sequences and formulate conjectures concerning omitted elements, missing partial sums, and word representations of infinite barrycades, which are firmly supported by computational data.
ER -