References & Citations
Mathematics > Combinatorics
Title: Friendly paths for finite subsets of plane integer lattice. I
(Submitted on 2 Feb 2023 (v1), last revised 5 Feb 2024 (this version, v6))
Abstract: For a given finite subset P of points of the lattice Z^2, a friendly path is a monotone (uphill or downhill) lattice path which splits points in half; points lying on the path itself are discarded. The purpose of this paper (and its sequel) is to fully describe all configurations of n points in Z^2 which do not admit a friendly path. We say that such an n-set is inseparable. There are, up to the lattice symmetry, exactly c(n) such sets. If only lattice shifts are counted, there are \^c(n) of them. Both sequences are new entries into OEIS (A369382 and, respectively, A367783). In particular, n=27 is the first odd numbers with c(n)=1. No example was known so far. This solves problem 11484(b)* posed in American Mathematical Monthly (February 2010). In this paper we also show that inseparable n-set exist for all even numbers n>=12 and almost all odd numbers.
Submission history
From: Giedrius Alkauskas [view email][v1] Thu, 2 Feb 2023 14:52:21 GMT (625kb,D)
[v2] Thu, 11 May 2023 12:48:41 GMT (1116kb,D)
[v3] Tue, 27 Jun 2023 12:10:28 GMT (1175kb,D)
[v4] Wed, 29 Nov 2023 13:39:00 GMT (1388kb,D)
[v5] Mon, 22 Jan 2024 12:43:41 GMT (1447kb,D)
[v6] Mon, 5 Feb 2024 10:44:42 GMT (1542kb,D)
Link back to: arXiv, form interface, contact.