Open Collections

Difference Necklaces

Banff International Research Station for Mathematical Innovation and Discovery

Is it possible to arrange the integers 1, 2, ... , n in a circle such that any two adjacent entries sum to a square Cube Fibonacci number What if the word sum is changed to difference Or the square, cube, Fibonacci number restriction is replaced by some other permissible finite set of values If such arrangements are possible, how many are there Are there infinitely many Richard Guy loved these types of questions which live at the interface between number theory and combinatorics and sound like simple brain teasers, but for which coming up with proofs is frequently extremely difficult if not outright impossible. Our protagonist in this talk is an (a,b)-difference necklace, which is a circular arrangement of the first n non-negative integers such that the absolute difference of any two neighbours takes on one of two possible values (a,b). We prove that such arrangements almost always exist for sufficiently large n, and provide explicit recurrence relations for the cases (a,b) = (1,2), (1,3), (2,4) and (1,4). Using the transfer matrix method from graph theory, we then prove that for any pair (a,b) -- and in fact for any finite set of two or more difference values -- the number of such arrangements satisfies a linear recurrence relation with fixed integer coefficients. This work began in summer 2017 as an NSERC USRA project undertaken by U of C undergraduate student Ethan White, now a PhD candidate at UBC, and jointly supervised by Richard Guy and me.

Mathematics; Mathematics

video/mp4

Author affiliation: University of Calgary

2020-10-30

Attribution-NonCommercial-NoDerivatives 4.0 International

http://hdl.handle.net/2429/76427

Unreviewed

http://creativecommons.org/licenses/by-nc-nd/4.0/