BIRS Workshop Lecture Videos

Banff International Research Station Logo

BIRS Workshop Lecture Videos

Difference Necklaces Scheidler, Renate


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.

Item Media

Item Citations and Data


Attribution-NonCommercial-NoDerivatives 4.0 International