I chose this particular problem because it was really easy to understand and because I got hooked by its title. I mean, who wouldn't want free lunch?
[From here, I am going to assume you read the problem and know what I will talk about. It shouldn't take you more than a minute to understand what the problem is about]
Looking for a pattern for who wins was the first thing I did, because it is the easiest and fastest way to come up with a solution. So I set up three groups of friends with sizes of eight, nine, and ten. I found that f1, f3, and f5 got free lunch when their group sizes were eight, nine, and ten respectively. Subsequently, I found that when the group size is eleven, f7 won. So clearly, there is a pattern where f(y = 2(x-7.5)) is going to get a free lunch if the group size is eight or above. But I wondered, who is going to win if the group size is less than eight, could it be f(-1)? To see who wins when the group size is less than eight, I first looked for who wins when the group size is seven, six, and five, and I found that f7, f5, and f3 won respectively. So without investigating the result of who will win when the group sizes are one, two, three, and four, from the pattern above, I know that f1, f1, f3, and f1 are going to win respectively.
From the analysis above, I figured out the fundamental behavior of who the winner is going to be. Basically, the winner ID is going to increase by two from one until the winner ID is equal to the group size. After that point, the winner ID is going to start from one again, until it once again reaches the group size by increasing the winner ID by two every time the group size increase by one. The problem now is, whether I can find a function that can accurately portray this scenario.
In a sense, this problem is a 3-dimensional problem, because the end result (the free-lunch winner ID) is dependent on two factors, one being the group size, and the other being the number of times the winner ID had to refresh itself to f1. Therefore, if there is an equation that can determine who will get free lunch, it will look something like:
winner ID = 2n + (something affected by refresh#) where n = group size
The 2n comes from the fact that winner ID increases by two for every increase in group size if the winner ID is not refreshing. To look for how refresh# affects the stuff inside the bracket, I once again looked for a pattern in the refreshing behavior of winner ID. What I noticed was that the group sizes at which the winner ID gets refreshed at were 1, 2, 4, 8, 16, 32.........For most people, this should already ring a bell that this is a base 2 exponential function. I also noticed, that before winner ID is refreshed, the stuffs inside the bracket is a constant. In fact, I determined previously that the constant inside the bracket take a list of values -1, -3, -7, -15........ which value to take on depends on how many times the winner ID was refreshed. So now, what I am interested in finding is a function whose output is only dependent on which integer power of 2 the input is. The only one I can think of is the ceil(base_2_log(n)). With this function, I can create another function that will give me an output that corresponds to the values in the list [-1, -3, -7, -15........] based on the group size. The function that I came up with is:
1-2^ceil((base_2_log n+1)) where n = group size
Now, let's confirm whether this function can give me those values in the list. If the group size is 1, then this function will give you -1. If the group size is 2, this function will give you -3. If the group size is 3, this function will STILL give you -3. If the group size is 23 or 29, the function will give you -31. Now we have confirmed that this is the function we want to put inside that bracket to solve for winner ID. The final function that will yield the winner ID is:
winner ID = 2n + 1 - 2^ceil((base_2_log n+1)) where n = group size
or to make it sound simpler:
number of people in between you and starting person counting counter clockwise
= 2n - 1 - 2^ceil((base_2_log n+1)) where n = group size
Thus this concludes my attempt to find a way to get free lunch for whoever lucky enough to have a group of friends who are peculiar as the friends mentioned in the problem. Just make sure you know how many people are in your group, then you can plug that number into this formula, and it will tell you how many people should be in between you and the starting person.
If your friends choose who gets free lunch by counting 3 rather than counting odd, then I can only guess that the final formula look something like:
winner ID = 3n + 1 - 3^ceil((base_3_log n+1)) where n = group size
Just to make sure I was right, I plugged in n = 9 into this equation, and I got 1 as the winner ID. Then I simulated the physical scenario on paper for group size 9, and that also showed that f1 will win.
Great post! I didn't think of approaching it like this.
ReplyDeleteLooking for pattern has always worked for me when I am doing a problem like this that you can easily simulate on paper. Run enough simulations and you voila!
ReplyDelete