0
$\begingroup$

A restaurant has a total of 16 tables, each of which can seat a maximum of 4 people. If 50 people were sitting at the tables in the restaurant, with no tables empty, what is the greatest possible number of tables that could be occupied by just 1 person?

I believe the integer programming conditions are the following, but I don't know a solver to execute this. How to solve by hand or via a computer?

Maximize: x*z1

Subject to: z1 + z2 = 1 (either x or y must be included in the solution) x + y = 16 x + 4y = 50 $x,y \in \mathbb{N}$

$\endgroup$
2
  • 1
    $\begingroup$ If this is a homework please, add an appropriate tag, if no, would you elaborate more on what you are looking for? $\endgroup$
    – A.Omidi
    Commented Mar 30, 2023 at 1:35
  • 1
    $\begingroup$ I'm puzzled why an IP model is required for a problem that can be easily solved by basic math? 16 people are required to ensure that there's at least 1 person/table. The remaining 50-16=34 people are used to fill up the tables. Each table has 3 seats left. ceil(34/3)=12 tables can be (partially) filled up, leaving 16-12=4 tables with 1 person? $\endgroup$ Commented Mar 30, 2023 at 2:15

4 Answers 4

-1
$\begingroup$

What about LCM? $2,3,4$ has lowest common multiple of $12$. So max $12$ tables can fit $2,3,4$ people. Remaining is $16-12=4$ tables for $1$ person

$\endgroup$
4
  • $\begingroup$ Not sure I follow. What if you could instead have up to 5 people per table? How would LCM(2,3,4,5)=60 come into play? $\endgroup$
    – RobPratt
    Commented Mar 30, 2023 at 4:11
  • $\begingroup$ Then lcm won't work. Lcm is for when each of the groups will have $\gt0$ tables. $\endgroup$ Commented Mar 30, 2023 at 4:43
  • $\begingroup$ Sorry, I still don't understand what LCM has to do with this. Please elaborate. $\endgroup$
    – RobPratt
    Commented Mar 30, 2023 at 16:11
  • $\begingroup$ What if the allowed number of people per table is 1, 2, or 4? With LCM(2,4)=4, it sounds like your LCM argument would claim that the maximum is $16-4=12$, which is false. $\endgroup$
    – RobPratt
    Commented Mar 30, 2023 at 16:38
3
$\begingroup$

For $i\in\{1,2,3,4\}$, let nonnegative integer decision variable $x_i$ be the number of tables occupied by exactly $i$ people. The problem is to maximize $x_1$ subject to linear constraints \begin{align} x_1 + x_2 + x_3 + x_4 &= 16 \tag1\label1 \\ 1 x_1 + 2 x_2 + 3 x_3 + 4 x_4 &= 50 \tag2\label2 \end{align} The linear programming relaxation yields optimal solution $x^*=(14/3,0,0,34/3)$, and the LP dual solution $(4/3,-1/3)$ certifies optimality: \begin{align} x_1 &\le x_1 + \frac{2}{3}x_2 + \frac{1}{3}x_3 \\ &= \frac{4}{3}(x_1 + x_2 + x_3 + x_4) -\frac{1}{3}(1 x_1 + 2 x_2 + 3 x_3 + 4 x_4) \\ &= \frac{4}{3}\cdot16-\frac{1}{3}\cdot50 \\ &= \frac{14}{3} \end{align} So the ILP has optimal objective value at most $\lfloor 14/3 \rfloor = 4$. Now find such a solution $x=(4,\underline{},\underline{},\underline{})$.


Note that the optimal LP solution can reasonably be obtained by inspection by arguing that $x_1$ will be maximized when $x_2=x_3=0$, which reduces \eqref{1} and \eqref{2} to two equations and two unknowns.


An alternative approach skips the LP solve and instead uses “probing” to deduce the upper bound of $4$. Suppose there are at least five tables with exactly one person ($x_1\ge5$). Then we must distribute the remaining $50-5=45$ people among the remaining $16-5=11$ tables that together have capacity $44<45$, but that is impossible. So $x_1 \le 4$.

$\endgroup$
0
$\begingroup$

Let $x_{i, j}\in\{0, 1\}$ represent whether there are $j$ people at table $i$, where $i=1, \dots, 16$, $j=1, \dots, 4$. The model is $$ \begin{split} \max &\sum_i x_{i, 1}\\ \mathrm{s.t.} &\sum_{i, j} j x_{i, j} = 50 \end{split} $$

The optimal value I believe is 4.

$\endgroup$
2
  • 2
    $\begingroup$ My integer $x_j$ variable is an aggregation $\sum_{i=1}^{16} x_{i,j}$ of your binary variables. This aggregation both reduces the number of variables and eliminates symmetry among the tables. $\endgroup$
    – RobPratt
    Commented Mar 30, 2023 at 2:04
  • $\begingroup$ @RobPratt Totally agree. $\endgroup$
    – xd y
    Commented Mar 30, 2023 at 2:35
0
$\begingroup$

No tables are empty, meaning all 16 tables must have at least one person sitting at them. Minimize the number of tables with more than one person by distributing the remaining 34 people (50 - 16 = 34) among the tables that already have 1 person.

  1. We can put 3 people at each table to reach its maximum capacity of 4. Doing this for 11 tables will accommodate 11 * 3 = 33 people.
  2. We still have 1 person left, so we can add them to the 12th table, which now has 2 people.

Now, we have:

  • 11 tables with 4 people each (44 people)
  • 1 table with 2 people (2 people)
  • 4 tables with 1 person each (4 people)

Thus, the greatest possible number of tables that could be occupied by just 1 person is 4.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.