A note on a candy sharing game

TY - JOUR

T1 - A note on a candy sharing game

AU - Bal, Deepak

AU - DeGaetani, Joseph

N1 - Publisher Copyright: © 2020 University of Primorska. All rights reserved.

PY - 2021

Y1 - 2021

N2 - Suppose k students sit in a circle and are each distributed some initial amount of candy. Each student begins with an even amount of candy, but their individual amounts may vary. Upon the teacher’s signal, each student passes half of their candy to their left and keeps half. After this step, any student with an odd amount of candy receives an extra piece. The game ends if all the students are holding the same amount of candy. We prove, in a generalized setting, that for any initial distribution of n pieces of candy, the game terminates after O(log n) many iterations and each student ends with nk +O(log n) many pieces. Moreover, there exist initial distributions for which the O(log n) term cannot be improved.

AB - Suppose k students sit in a circle and are each distributed some initial amount of candy. Each student begins with an even amount of candy, but their individual amounts may vary. Upon the teacher’s signal, each student passes half of their candy to their left and keeps half. After this step, any student with an odd amount of candy receives an extra piece. The game ends if all the students are holding the same amount of candy. We prove, in a generalized setting, that for any initial distribution of n pieces of candy, the game terminates after O(log n) many iterations and each student ends with nk +O(log n) many pieces. Moreover, there exist initial distributions for which the O(log n) term cannot be improved.

KW - Games on graphs

KW - Markov chains

UR - http://www.scopus.com/inward/record.url?scp=85102308680&partnerID=8YFLogxK

U2 - 10.26493/2590-9770.1304.2cf

DO - 10.26493/2590-9770.1304.2cf

M3 - Article

SN - 2590-9770

VL - 4

JO - Art of Discrete and Applied Mathematics

JF - Art of Discrete and Applied Mathematics

IS - 1

M1 - P1.02

ER -