Wiki
Wiki

Research notes on every problem, and a library of the papers behind them. Built from the open erdos repository.

Updated


Claim. For every prime pp, every A⊆Fp∖{0}A\subseteq\mathbb F_p\setminus\{0\} of size p−2p-2, and Fp∖{0}\mathbb F_p\setminus\{0\} itself, has an ordering whose partial sums are distinct, the question of Problem 475 for the two largest sizes. The paper's result is Theorem 2 (printed p. 4) of J.-P. Bode and H. Harborth, Directed paths of diagonals within polygons: "Conjecture 1 is true for t=n−2t=n-2", where Conjecture 1 is Alspach's conjecture in the paper's language of directed diagonals of an nn-gon. In the problem's notation, for every nn every (n−2)(n-2)-subset of Zn∖{0}\mathbb Z_n\setminus\{0\} with nonzero sum has an ordering whose partial sums are distinct and nonzero: by an explicit directed cycle through all n−1n-1 lengths, with one diagonal deleted, for odd nn, and by an induction on the missing length for even nn. For n=pn=p, every (p−2)(p-2)-subset Zp∖{0,x}\mathbb Z_p\setminus\{0,x\} has sum −x≠0-x\ne0, so each has an ordering with distinct, nonzero partial sums, which is more than the problem asks. Appending xx gives a valid ordering of Zp∖{0}\mathbb Z_p\setminus\{0\}, by the step in the proof of the Archdeacon--Dinitz--Mattern--Stinson implication (Costa and Pellegrini, Arch. Math. 115 (2020), p. 7 of the arXiv version); the odd-nn cycle, read as on the result page, gives the same ordering directly. The paper's Theorem 1, for the size n−1n-1, is vacuous for odd nn, since the only (n−1)(n-1)-subset then has sum (n2)≡0\binom n2\equiv0. Hicks, Ollis and Schmitt report both sizes from this paper on their p. 2 and reprove its odd case as their Theorem 4.3, attributed to it (their claim page). Read depth: Theorem 2 and the odd-nn half of its proof are checked; the even-nn induction (pp. 5--9), carried by the paper's figures, is read for structure only.

Covers. Every prime pp: every subset of size p−2p-2, and Zp∖{0}\mathbb Z_p\setminus\{0\} itself. The latter is Graham's case t=p−1t=p-1, whose proof no cited source prints.

Depends on. Nothing in this wiki: the result is the paper's own, filed on its library result pages.

Acceptance. Refereed publication: Discrete Mathematics 299 (2005), 3--10, DOI 10.1016/j.disc.2005.05.006, available online 10 August 2005, which dates this page. The site credits the range p−3≤t≤p−1p-3\le t\le p-1 through Hicks, Ollis and Schmitt and the references therein, but its label DECIDABLE leaves the problem open, so that credit is not reviewed evidence.