5
$\begingroup$

The Infinite McDonald's is a magical restaurant with a menu containing infinitely many items! Each menu item is a combo, where each of the infinitely many dishes either appears once or not at all. No combo is ever repeated.

The menu has the following properties:

  1. There exists a combo that contains every dish — the McNuggets, Filet-O-Fish, fries, and infinitely many other delights!

  2. For any two combos, there exists a combo that contains all dishes present in either of the two combos.

  3. If you dislike a particular combo, take comfort: there exists a combo that contains exactly all the dishes that are missing from the one you dislike.

The restaurant's CEO wants there to be a "Combo of the Year" every year and that a dish can never be present in two or more "Combo of the Year". Is that always possible?

Improve this question
New contributor
Racist Cat is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
$\endgroup$
8
  • 1
    $\begingroup$ @Pranay you do need to prove that that solution is always possible though. It could be the case that there are no menu combos with one dish. $\endgroup$ Commented yesterday
  • $\begingroup$ @Goblin. Ah I see. I see that we are only told what the combos satisfy, but we aren’t told what the combos themselves are. Nice! $\endgroup$ Commented yesterday
  • 1
    $\begingroup$ @florianF no other. $\endgroup$ Commented yesterday
  • 1
    $\begingroup$ Why do we need property 1? Properties 1 and 3 imply the empty set, which we might as well choose to be Combo of the Year every year. It seems we can just do away with this by taking property 1 to be assuredly false. $\endgroup$ Commented yesterday
  • 1
    $\begingroup$ Since $M\cup M'=\mathcal U$, properties 2 and 3 imply property 1, and so also the empty set as this is $(M\cup M')'$. $\endgroup$ Commented 20 hours ago

3 Answers 3

Reset to default
5
$\begingroup$

Here is a closely related math version of this problem.

The question is basically asking:

Does every infinite Boolean Algebra contain an infinite sequence of pairwise disjoint elements?

The answer is

Yes.

Think of the menu in two ways: either you have indivisible parts (atoms) or you don't:

Infinite Atoms (like "Nuggets"): The menu contains infinitely many "indivisible" combos. If so, simply pick a distinct atomic combo each year. Since they are indivisible, they cannot overlap.

Atomless Remainder (like "Dough"): If the number of atoms is finite, removing them must leave a non-empty "atomless" remainder (otherwise the menu would be finite). Think of this as a glob of dough that can always be sliced into smaller valid pieces.

If you are left with the "dough" (atomless part), you use a recursive slicing strategy:

  • Cut a proper slice $C_1$ off the dough. Serve it. Keep the remainder $R_1$.
  • Cut a proper slice $C_2$ off $R_1$. Keep the remainder $R_2$.
  • Repeat indefinitely.

Because the remainder is atomless, you never hit a smallest piece which ensures the sequence never terminates.

In a mathematical way, the menu forms a Boolean Algebra of subsets of the dishes $D$. We need an infinite sequence of pairwise disjoint non-empty combos.

Case 1: Infinitely many atoms. Pick a different atom each year. Distinct atoms are disjoint by definition: if two atoms overlap, their intersection would be a smaller non-empty menu combo, which forces them to be identical.

Case 2: Finitely many atoms. Let $A$ be the union of all atoms. If $A = D$, the entire algebra is generated by finitely many atoms, which will make the menu finite.

Thus, the leftover $L = D \setminus A$ is non-empty and atomless. We apply the slicing strategy to $L$: Let $R_0 = L$ and for each year $n$, choose $C_n$ to be any non-empty proper subset of the previous remainder $R_{n-1}$. Then define the new remainder as $R_n = R_{n-1} \setminus C_n$.

Since we are working within an atomless set, a proper subset will always exist. This generates the asked infinite sequence of disjoint combos for our CEO.

Improve this answer
$\endgroup$
2
  • 2
    $\begingroup$ +1 nicely done. although I'm not sure if the head chef can understand this $\endgroup$ Commented yesterday
  • 1
    $\begingroup$ @RacistCat he will never have a infinite items in his restaurant probably anyway :) $\endgroup$ Commented yesterday
3
$\begingroup$

There is a little bit of ambiguity in the second property: does the new combo contain only the dishes contained in either of the two original combos, or can it contain more? I'm going to assume that it contains only these dishes as otherwise the second property has no force (it's already fulfilled by the first property, the existence of a universal combo.) In this case, the answer is yes, and here is how:

For the first combo of the year, first think of any combo at all, call it $M$. By property 3, the complementary combo, which I'll call $M'$, also exists. By property 2, given any two combos $A$ and $B$, their combination combo, which I'll call $A\cup B$, also exists. But then, again given combos $A$ and $B$, the combo which contains all and only the dishes present in both of $A$ and $B$ must also exist, since it is $(A'\cup B')'$. Call this combo $A\cap B$.

If combo $A$ contains all the dishes present in $B$, and perhaps more, call this property $A\supseteq B$ (or $B\subseteq A$.) Then given any combos $A\subseteq M$ and $B\subseteq M'$, $A\cup B$ is also a combo. But it's also true that any combo $C$ can be gotten by combining some combo $A\subseteq M$ and some combo $B\subseteq M'$, since for any combo $C$, $C=(C\cap M)\cup (C\cap M')$, $C\cap M\subseteq M$, and $C\cap M'\subseteq M'$.

Because of this, if we look at (1) the set of combos $A$ with $A\subseteq M$, and (2) the set of combos $B$ with $B\subseteq M'$, one of the two sets (1) and (2) must be infinite, since if they were both finite, then since, as we just saw, any combo can be gotten by combining a combo in (1) with one in (2), the overall set of all combos would be finite, which we know it's not.

If (2) is infinite, pick $M$ as combo of the year; otherwise (1) must be infinite, so pick $M'$. In order to prepare future combos of the year, we now prepare a new menu (for internal use only) which contains only combos in (2), if we picked $M$, or (1), if we picked $M'$. That way, we automatically fulfill the requirement that no dish be present in two combos of the year. But notice that our new menu is still infinite and, if we restrict our attention to dishes present only in $M$ or $M'$ (as appropriate) then it still fulfills properties 1, 2, and 3: property 1 is satisfied since the menu contains $M$ or $M'$, which is now the universal combo from the point of view of this new menu, property 2 is satisfied as it was satisfied in the original menu, and property 3 is satisfied as if $A$ is a combo, so is $A'\cap M$ (or $A'\cap M'$.) So now, for the second combo of the year, we apply the same reasoning as we did for the first combo but with the new submenu; of course this will mean making a new subsubmenu, which we use to choose the third combo of the year, and so on. Continuing in this way we can choose combos of the year forever, which is what we wanted to do.

Improve this answer
New contributor
David Moews is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
$\endgroup$
1
  • 1
    $\begingroup$ i like this!! no assumption of any prior set theory whatsoever $\endgroup$ Commented yesterday
1
$\begingroup$

This is

always possible.

(No spoiler blocks from here.)

Let's call our set of dishes $X$ and the set of combos $B$. From the requirements, we know that $B$ is infinite and is closed under taking complements and (finite) unions (in math terms, $B$ is a sub-boolean algebra [or boolean subalgebra?] of $\mathcal{P}(X)$, if that means anything to you). Let's call a nonempty subset $A\in B$ unsplittable if no proper nonempty subset of $A$ is also in $B$ and splittable otherwise.

Note that any family of unsplittable elements is automatically disjoint (think about intersections). Therefore, if it happens that $B$ contains infinitely many unsplittable combos, we are good to go. (For instance, if $B$ contains every possible combo, the set of singletons $\{x\}$ for $x\in X$ would be such a family.)

As such, we only need to worry about there being only finitely many unsplittables. (This is definitely possible! For instance, think about $X=\mathbb{Q}$ and $B$ the set of "clopen" subsets, i.e. the sets generated by unions and complements of intervals $(r_1,r_2)$ for irrational $r_i\in \mathbb{R}$.) If we are in that case, consider the complement of the union of all unsplittables and call it $Y$. I claim that $Y$ is not empty: Otherwise the finitely many unsplittables $A_1,...,A_n$ would cover all of $X$. But then, there would only be $2^n$ many combos in $B$, since every combo would be determined exactly by the set of unsplittables contained in it. As $B$ is assumed to be infinite, this cannot happen. As a consequence, $Y$ is not empty. Moreover, since $Y$ contains no unsplittables, every subset of it must be splittable, starting with $Y$ itself.

From there, we can build our sequence iteratively: Start by picking any nonempty proper subset $A_1$ of $Y$ (in $B$). Then the complement $Y\setminus A_1$ is disjoint from $A_1$ and still splittable. Pick any (nonempty proper) subset $A_2$ from it and again look at the complement $Y\setminus(A_1\cup A_2)$.

By repeating this splitting off, we obtain a sequence $A_1, A_2, \cdots$ of disjoint subsets of $Y$ such that $Y\setminus(A_1\cup \cdots \cup A_n)$ always remains splittable.

Thus, in any case, we can build our infinite sequence of disjoint combos.

(At least if we assume the axiom of choice in the part about repeatedly splitting off. I haven't thought this through yet, but it feels like there should be counterexamples available if (say) our set-theoretic universe contains an amorphous set or something similar.)

Improve this answer
$\endgroup$
1
  • 2
    $\begingroup$ the choice police begins to crack down on Infinite restaurants that have their menu as amorphous set, so I don't think we have to worry about that:) $\endgroup$ Commented yesterday

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.