Make Everyone Souper Happy!

Today I was at my university dining hall, looking at the options for soup.

The dining hall has 2 types of soup at any given time, but they rotate these soups out with several other soups daily. Let's say there are 6 in total.

I am happy to eat some of the soups, but there are also many soups which I do not like to eat. For example, while I like the Italian meatball soup, I don't like the buttermilk squash. Unfortunately, on this day, they did not have a soup that I wanted, but rather just buttermilk squash and garden vegetable mix. "At least the people who like buttermilk squash or garden vegetable mix are happy", I reasoned. But these two soups seem to me like soups that not many people like in general. Therefore, it makes sense to say that they should not be put out together.

Let's now assume a few things. Say that we somehow know which soups each of the N students who eat at the cafeteria like, and which they do not like (there is no in-between). Let's also say that the cafeteria wants to establish a M-day rotation where each soup is used exactly once. The cafeteria wants to make it so that, on the worst day in the rotation, the maximal amount of people are happy. To further generalize, let's say that they have exactly K slots for soup.

Given all the data, what is the best algorithm you can develop for solving this?

Example: Let's use the dining hall I've described. Say there are 4 students, so N = 4, M = 3, and K = 2. Then, let's list out all of the students by their preferences, with a 1 for 'like' or 0 for 'dislike'. The first number in the line will represent if they like the first soup, the second the second soup, and so on.

4 3 2

1 1 0 0 0 0

1 0 1 1 0 0

1 0 0 0 1 1

0 0 1 1 0 1

A possible answer:

Day 1 : The first and fifth soup (only the 4th student is sad)

Day 2 : The second and third soup (only the 3rd student is sad)

Day 3 : The fourth and sixth soup (only the 1st student is sad)

With this answer, on each day (and therefore the worst day), exactly 1 student does not have a good soup. This is the optimal answer because it is impossible that each student is happy every day. One way to prove this is to notice that the first student only likes soups 1 and 2, so there is no way to make him happy for 3 days.

Note: I made up this question while thinking about soup and thought it interesting, it is not guaranteed to have an easy or nice answer. Therefore, you may use your creativity! If you can't come up with a fast optimal solution, try a fast solution that gives 'good' results, or try fixing one of the variables, for example, solving the problem only for K=2.

Note by Alex Li
3 years, 6 months ago

No vote yet
1 vote

  Easy Math Editor

This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.

When posting on Brilliant:

  • Use the emojis to react to an explanation, whether you're congratulating a job well done , or just really confused .
  • Ask specific questions about the challenge or the steps in somebody's explanation. Well-posed questions can add a lot to the discussion, but posting "I don't understand!" doesn't help anyone.
  • Try to contribute something new to the discussion, whether it is an extension, generalization or other idea related to the challenge.
  • Stay on topic — we're all here to learn more about math and science, not to hear about your favorite get-rich-quick scheme or current world events.

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold

- bulleted
- list

  • bulleted
  • list

1. numbered
2. list

  1. numbered
  2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1

paragraph 2

paragraph 1

paragraph 2

[example link]( link
> This is a quote
This is a quote
    # I indented these lines
    # 4 spaces, and now they show
    # up as a code block.

    print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in \( ... \) or \[ ... \] to ensure proper formatting.
2 \times 3 2×3 2 \times 3
2^{34} 234 2^{34}
a_{i-1} ai1 a_{i-1}
\frac{2}{3} 23 \frac{2}{3}
\sqrt{2} 2 \sqrt{2}
\sum_{i=1}^3 i=13 \sum_{i=1}^3
\sin \theta sinθ \sin \theta
\boxed{123} 123 \boxed{123}


Sort by:

Top Newest

Wow. You must really like soup 🍜

Annie Li - 3 years, 6 months ago

Log in to reply


How about you???

Matin Naseri - 3 years, 6 months ago

Log in to reply

Depends. Some of them makes me go to the bathroom alot

Annie Li - 3 years, 6 months ago

Log in to reply

@Annie Li LOL\text{LOL}

Matin Naseri - 3 years, 6 months ago

Log in to reply

I have a feeling this problem is going to be NP-complete.

Agnishom Chattopadhyay - 3 years, 6 months ago

Log in to reply


Problem Loading...

Note Loading...

Set Loading...