ITYM 2013 Question 6: Upper Secondary Mathematics Competition Question

ITYM 2013 Question 6. An Expensive Dinner

There are n friends, numbered 1 through n. They are all going to a restaurant for dinner tonight.  They are all very good at math, but they are all very strange: the ath  friend will be unhappy unless the total cost of the meal is a positive integer, and is divisible by a.

The friends enter the restaurant one at a time. As soon as someone enters the restaurant, if that person is unhappy then the group will call a waiter immediately.

As long as there is at least one unhappy person in the restaurant, one of those unhappy people will buy the lowest-cost item that will make him or her happy. This will continue until nobody in the restaurant is unhappy, and then the waiter will leave. Fortunately, the restaurant sells enough food at every integer price.

The friends could choose to enter the restaurant in any order.  After the waiter has been called, if there is more than one unhappy person in the restaurant, any one of those unhappy people could choose to buy something first.  The way in which all of those choices are made could have an effect on how many times the group calls a waiter.

For example, if n = 3 and the friends arrive in the order [1, 2, 3], then a waiter will be called three times. (#1  arrives, is unhappy, calls a waiter and buys something costing 1 euro. #2 arrives next, is unhappy, calls a waiter and buys something costing 1 euro.  Now nobody is unhappy. #3 arrives next, is unhappy, calls a waiter and buys something costing 1 euro. Now #2 is unhappy and buys something costing 1 euro. Now #3 is unhappy and buys something costing 2 euro, for a total of 6 euros. Finally nobody is unhappy, and a waiter was called three times.) However, if the friends arrive in the order [3, 1, 2], then a waiter will be called 2 times.

1. Denote by Wmax  the maximal number of times the friends might call a waiter. Find Wmax or estimate it.

2. Denote by Wmin  the minimal number of times the friends might call a waiter. Find Wmin or estimate it.

3. Suppose now that only friends with numbers a₁, . . . , a_k will come to the restaurant. Find or estimate Wmax  and Wmin  in this case. Here a₁, . . . , a_k are distinct positive integers.

4. Denote by W the number of times the friends will call a waiter. Determine the set of all possible values of W . Consider the following cases:

a) The friends are numbered 1 through n.

b) The friends have numbers a₁, . . . , a_k (distinct positive integers).

5. Denote by U the total number of times the friends were unhappy. Determine the set of all possible values of U in the cases a) and b) above.

6. Suggest and investigate additional directions of research.


This question is from the 2013 ITYM. As of writing, the tournament is ongoing (5-12 July 2013) but a look at the Regulations shows that all the teams have already submitted their solutions (and partial solutions) and that the live tournament is for debating purposes.

If you have participated in any of the International Tournaments of Young Mathematicians then let us know about your experience.




Feel free to comment, ask questions and even check your answer in the comments box below powered by Disqus Google+.

If you enjoy using this website then please consider making a donation - every little helps :-)

You can receive these questions directly to your email box or read them in an RSS reader. Subscribe using the links on the right.

Don’t forget to follow Gifted Mathematics on Google+, Facebook or Twitter. You may add your own interesting questions on our Google+ Community and Facebook..

You can also subscribe to our Bookmarks on StumbleUpon and Pinterest. Many resources never make it onto the pages of Gifted Mathematics but are stored in these bookmarking websites to share with you.