The lower-bound conjecture for coupon collecting with friends
The lower-bound conjecture for coupon collecting with friends
Let ) collectors each seek a complete collection of coupon types. The process has a collection phase of rounds, followed by an exchanging phase of rounds in which collectors interact and exchange coupons.
Lower-bound conjecture. If
then
is necessary to succeed with any positive constant probability.
The conjecture asserts that the currently known upper bound on the number of interactions is tight even when only a positive constant success probability is required. The motivation is that existing lower bounds account only for the difficulty of ensuring a single interaction, not for the difficulty collectors with incomplete collections face in obtaining multiple coupons during the exchanging phase.
Sources & referencesView supporting material
Primary source
Dan Alistarh and Peter Davies, “Collecting Coupons is Faster with Friends”, arXiv:2112.05830 (2021).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.