Office Lunch

Probability Level 4

For lunch, I have the options of Vegetarian, Paleo and Meat-lovers. Wanting to be healthy, I do not want to eat Meat-lovers for 2 consecutive days.

How many ways are there to order lunch for a 5-day workweek?

The answer is 164.

2 solutions

Ajinkya Shivashankar
Mar 10, 2017

Relevant wiki: Linear Recurrence Relations - Problem Solving

Let us go for a solution using recurrence.

Let $A_n=$ number of ways to order lunch for n days

Let $B_n=$ number of ways to order lunch for n days such that we do not choose meat on the final day

Let $C_n=$ number of ways to order lunch for n days such that we choose meat on the final day.

$A_n=B_n+C_n$

$B_n=2A_{n-1}$ we can add a non meat lunch (2 ways) at the end of n-1 days irrespective of what the previous days lunch was.

$C_n=B_{n-1}$ only if last but 1 day is non-meat can we choose the last lunch as meat.

$B_1=2 , C_1=1$

Tabulating

Days	B	C	A
1	2	1	3
2	6	2	8
3	16	6	22
4	44	16	60
5	120	44	164

Thus our answer is 164

If we had to solve it for (lets say) 100 days, I would rather create a fibonacci type recurrence and solve it $A_{n+2}=2(A_{n+1}+A_n), A_1=3, A_2=8$

And solving the recurrence gives $A_n =\frac{((\sqrt{3} - 3) (1 - \sqrt{3})^n + (9 + 5 \sqrt{3}) (1 + \sqrt{3})^n)}{(6 (1 + \sqrt{3}))}$

Indeed. The "two lunch options" case is the scenario of "how many 0, 1 sequences are there with no consecutive 1's", whose solution is well known to be the Fibonacci sequence, and one can set up the recurrence in a similar manner.

I extended the problem slightly, to illustrate how powerful this recurrence approach is, as compared to trying to "count the possibilities explicitly".

Calvin Lin Staff - 4 years, 3 months ago

Zee Ell
Mar 9, 2017

Let's have a look at the following cases (based on the number of times Calvin orders Meat-lovers (M) menus during the 5-day workweek):

Case 1: No M orders (M = 0):

There is a choice between Vegetarian (V) and Paleo (P) on each day, that gives Calvin

$2^5 = 32 \text { ways to order his lunch.}$

Case 2: One M order (M = 1):

We can choose the M-day 5 ways, and an option between the 2 other (V and P) meals on the other 4 days, which means that Calvin has another

$5×2^4 = 80 \text { ways to order his lunch.}$

Case 3: Two M orders (M = 2):

There is an option between the 2 other (V and P) meals on the other 3 days, and the 2 M-days can be chosen 6 ways on a Mon - Fri workweek:

• if the first M-day is Mon, the other M-day can be choosen 3 ways (Wed, Thu or Fri);

• if it's Tue, then 2 ways (Thu or Fri); and

• if it is Wed then only 1 way (Fri, to avoid consecutive M-days).

(and it is easy to see, that Thu or Fri cannot be the first M-day).

3 + 2 + 1= 6

This gives Calvin an additional

$6×2^3 = 48 \text { ways to order his lunch.}$

Case 4: Three M orders (M = 3):

Now it is easy to see, that the 3 M-days can be chosen only 1 way (Mon, Wed and Fri (otherwise we would have consecutive M-days)) and an option between the 2 other (V and P) meals on the other 2 days, which means that Calvin has another

$1×2^2 = 4 \text { ways to order his lunch.}$

It is also easy to see, that Calvin cannot have 4 or 5 M-orders on a 5-day workweek without having consecutive M-days.

Hence, our answer should be:

$32 + 80 + 48 + 4 = \boxed {164}$

That's slightly painful to look at.

There is a faster way :)

Hint: What happens if there were only choices of Vegetarian and Meat-Lovers for lunch?

Calvin Lin Staff - 4 years, 3 months ago

Total possibilities for lunch is 3^5.

(I) Number of ways for having meat for 2 consecutive days = 4×3^3.

(II) But this counts the number of ways for having meat for 3,4 or 5 days multiple times.

(III) So, we add the number of ways for having meat for 3 consecutive days = 3×3^2.

(IV) So, we add the number of ways for having meat for 4 consecutive days = 2×3^1.

(V) So, we add the number of ways for having meat for 5 consecutive days = 1

(VI) But (III) already includes (IV) and (V) and (IV) already includes (V).

(VII) so we subtract the number we obtained in (IV) and the twice number we obtained in (V).

Answer is $3^5-4×3^3+3×3^2+2×3+1-3×2-2×1=243-108+27+6+1-6-2=161$ .

Where have I done a mistake sir?

A Former Brilliant Member - 4 years, 3 months ago

Can you be explicit and state what you are doing?

IE If you are using the principle of inclusion and exclusion , state what those sets are.

Calvin Lin Staff - 4 years, 3 months ago

I do believe that a recurrence-type solution (like the one presented here by Ajinkya) is prettier (so it's closer to the one from the Book) and easier to generalise, however, I do not believe that it is faster in this case (5 days, just have a look at the number of calculations at both solutions and you will see).

(It took me about 2 minutes to come up with the method and the correct answer. My solution should probably be less detailed for a hard question, but I do not consider this question hard at all.)

I believe, that it would have been better to publish this question with the 5-day workweek as medium and another (hard) version with a larger number (say, 100) of consecutive days.

My solution should have a place at the current (medium level) question, along with other more "painful" solutions.

(E.g. Solution 2: Any menu can be eaten on odd days but only P or V on even days + vice versa - double counted no-M-at-all week + M exactly on the (1st and 4th) or (2nd and 5th days).

Solution 3: All non-restricted ways - 5c(onsecutive M-days) - 4ce(xactly) - 3ce - 2ce - (2ce2ce) - (3ce1) - (2ce1)

Solution 4: PIE - type (E.g what Svatejas tried to do, but done correctly))

(By the way, what would be the most painful for me here, is to look at, think of, smell or eat some of the choices offered :) My memories are particularly painful regarding spinach: when I was 6 years old, my teacher wanted to make me eat the spinach at the school canteen. After the first spoonful, my face went very pale (within seconds), then I stood up (wanted to go to the nearby lavatory), but couldn't take a step before the spinach came back and ended up on the floor.)

Zee Ell - 4 years, 3 months ago

Great! You hit the nail on the head about "appropriateness of solution to the level of the problem". I agree that for a Level 2/3, your solution would be the approach that they would try / succeed / understand, while the recurrence approach would seem somewhat mystical.

I'm glad you found several other approaches to the problem :)

One of these weeks I'm going to play with the POTW and have the problems scaffold up in such a manner.

Calvin Lin Staff - 4 years, 3 months ago

What's wrong with 3^5 -( 4 2^3 + 3 2^2 + 2*2 + 1)

Pratik Vora - 4 years, 2 months ago

Can you be explicit and state what you are doing?

Calvin Lin Staff - 4 years, 2 months ago

Using inculsion - exclusion.

1) total ways to select meal ( 3 choices) for 5 days ( $3^5$ ).

2) choosing meat on two consecutive days(4 ways) and any on the other 3 days..( $3^3$ )

3) meat on three consecutive days(3 ways) and any on other two days ( $3^2$ )

4) 4 consecutive (2 ways) and any on other day ( $3^1$ )

5) meat everyday (1 way)

$3^5 - (4\times 3^3 - 3\times 3^2 + 2\times 3^1 - 1)$ .

I think inclusion exclusion includes consecutive terms and since there is a jump between first and second term, it gets wrong..

Vishal Yadav - 4 years, 2 months ago

@Vishal Yadav – That's the right idea, but be careful with what you're doing. Specifically, in order to apply principle of inclusion and exclusion (pie) , you have to state what sets you're looking at.

It doesn't quite make sense to look at"Define $A_1$ to be that I do not eat meat on the first day", because you cannot include-exclude your way to what is desired easily. Instead, what we should do is "define $B_1$ to be that I eat meat on days 1 and 2, $B_2$ to be that I eat meat on day 2 and 3, ... " If we, we're wanting to find (the complement of) $B_1 \cup B_2 \cup B_3 \cup B_4$ . Now, we can indeed apply PIE to this union of sets.

Note: With the definition of $A_1$ , you can painfully get to the answer, but essentially by tediously keeping track of cases.

Similarly with the idea of discrete random variables - indicator variables , you want an indicator of exactly what's happening, instead of a "well, if both of these were true then it's true, but not if one is true and the other is false".

Calvin Lin Staff - 4 years, 2 months ago

Office Lunch

The answer is 164.

2 solutions

0 pending reports