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}$

Improve this question
$\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
    Mar 30 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$
    – Joris Kinable
    Mar 30 at 2:15

4 Answers 4

Reset to default
-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

Improve this answer
$\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
    Mar 30 at 4:11
  • $\begingroup$ Then lcm won't work. Lcm is for when each of the groups will have $\gt0$ tables. $\endgroup$
    – Sutanu
    Mar 30 at 4:43
  • $\begingroup$ Sorry, I still don't understand what LCM has to do with this. Please elaborate. $\endgroup$
    – RobPratt
    Mar 30 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
    Mar 30 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$.

Improve this answer
$\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.

Improve this answer
$\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
    Mar 30 at 2:04
  • $\begingroup$ @RobPratt Totally agree. $\endgroup$
    – xd y
    Mar 30 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.

Improve this answer
$\endgroup$

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.

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