8
$\begingroup$

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...

Example

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.

$\endgroup$
9
  • $\begingroup$ Are you the first to order? $\endgroup$
    – Ankit
    Aug 17 at 17:30
  • $\begingroup$ Yes, it says so in the least paragraph of Problem Statement :) $\endgroup$
    – Feryll
    Aug 17 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 at 23:33
  • $\begingroup$ Reminds me of this a little bit en.wikipedia.org/wiki/Pirate_game $\endgroup$ Aug 24 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 at 5:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.