N, T, A, B are arbitrary constants in this problem. I have only definitively solved the N=1 subproblem, so, if the general problem cannot be solved, I will be satisfied to mark as accepted a solution to this subproblem. I may put a bounty out for the general solution before that.

Problem Statement

You and N friends are seated at a restaurant, where you have agreed to equally split the check for \$T. The dining process consists of a waiter going around the table, asking each guest in turn to order an entrée costing any amount of \$1, \$2, ..., up to \$A (you cannot skip an entrée). The meal is of course over once the \$T limit has been reached (it cannot be exceeded).

The vain glutton that you are, you want to:

  1. eat more than you pay for (that is, \$T/(N+1)), but also;
  2. not be exposed as a glutton, which in this case consists of eating more than \$B extra than the next most expensive eater. If (1) cannot be achieved, you will nonetheless consider it a victory to see someone else exposed in such a fashion.

Assuming you are first to order, for what values of N, T, A, B can you guarantee victory, no matter how your friends order? Keep in mind, they may conspire to make it difficult for you...


If (N, T, A, B) = (1, 21, 13, 10), your gluttony might tempt you to order the most expensive \$13 entrée right off the bat. This would be a mistake, because your friend could thereafter order only \$1 entrées and expose you as a glutton. Similarly, you shouldn't order an \$11 or \$12 entrée. Yet if you order a $10 entrée or less, your friend may order an \$11 entrée, and you wind up paying for more than you eat while he cannot be exposed. So, there is no victory in this example configuration.

  • $\begingroup$ Are you the first to order? $\endgroup$
    – Ankit
    Aug 17, 2021 at 17:30
  • $\begingroup$ Yes, it says so in the least paragraph of Problem Statement :) $\endgroup$
    – Feryll
    Aug 17, 2021 at 19:03
  • 1
    $\begingroup$ Funny, N>1 case seems easier than N=1, because the other's don't have to worry about being exposed (unless b=0). Still, too many cases for me ;-) $\endgroup$
    – loopy walt
    Aug 17, 2021 at 23:33
  • $\begingroup$ Reminds me of this a little bit en.wikipedia.org/wiki/Pirate_game $\endgroup$ Aug 24, 2021 at 4:24
  • 1
    $\begingroup$ @Petr Naryshkin He will go around the table as many times as it takes to reach a total check of T, yes. $\endgroup$
    – Feryll
    Aug 25, 2021 at 5:45


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Browse other questions tagged or ask your own question.