Here’s a puzzle: people are in a bar, sitting around a round table. A certain person pays for the first round of drinks. The person to their right pays for the second round. The person two people to the right of that person pays for the third round. In general, whoever paid for the nth round, the person n people to their right pays for the (n+1)st round.
Question the first: For a given value of , is there somebody who never pays for any drinks?
Question the second: How many somebodies are there?
(As of this writing I know the answer to the first of these questions but not the second. Metasolvers should feel free to use this information.)
For concreteness, say there are five people, named Alice, Bob, Carol, Dave, and Eve. <b>Alice</b> pays for the first round. The person to her right, <b>Bob</b>, pays for the second round. Carol is skipped and <b>Dave</b> pays for the third round. Eve and Alice are skipped and <b>Bob</b> pays for the fourth round. Carol, Dave, and Eve are skipped and <b>Alice</b> pays for the fifth round. And so on. So Alice pays for two rounds out of every five; so does Bob. Dave pays for one round out of every five. Carol and Eve never pay.
Unfortunately my friends know I’m a mathematician, and this sounds enough like a math problem that they’d be suspicious if I suggested this as a paying-for-drinks scheme. That’s probably for the best.
I can prove that if r is an odd prime then there are (r-1)/2 people that don’t have to pay for a round. I don’t know about the composite case. I’m also pretty sure that if r is a power of two then everyone will pay for a round (and I’ve verified it up to 2^26) but I can’t prove it yet.
The payers are the triangular numbers n(n+1)/2, modulo r. Looks like r=5 manages to skip two people as n(n+1)/2 mod 5 = 0,1,3,1,0 for n=0,1,2,3,4.
A related puzzle:
http://juegosdeingenio.org/archivo/1123
Given any integer r, a friend of mine and I have been able to prove the number of people in a circle of r people that would have to pay for drinks. We are currently working on a strategy of picking the first buyer that would guarantee that “you” don’t have to buy a drink. This second part of the problem is considerably more difficult.
Given any integer r, a friend of mine and I have been able to prove the number of people in a circle of r people that would have to pay for drinks. We are currently working on a strategy of picking the first buyer that would guarantee that “you” don’t have to buy a drink. This second part of the problem is considerably more difficult.
At a table of r people number the people around the table from 0 to r-1 (counter-clockwise). Then person 0 pays, person 0+1 pays, person 0+1+2 pays, and each person 0+1+2+…+n (mod r) pays whenever n<r. Well, 0+1+2+…+n = (n^2 + n)/2. Hence it follows that person k pays if and only if k = (n^2 + n)/2 (mod r) for some n<r. We have started calling such integers k "triangular residues" (similar to the term "quadratic residues"). Thus the number of people that would have to pay is equal to the number of triangular residues modulo r.