0
$\begingroup$

Levi likes to eat one piece of fruit every day: an apple, and orange, or a banana. Each Sunday he prepares a schedule for the upcoming week: which fruit will he eat which day. How many weeks can he go without repeating a weekly schedule if he cannot eat any fruit more than 3 times a week?

I think I got the answer but I am pretty sure there is a faster way to do it.

$\endgroup$
1
  • 5
    $\begingroup$ How did you approach the problem? What is your answer? Asking if there's a faster way is pointless if we don't know what your answer is. $\endgroup$
    – erfink
    Oct 17, 2016 at 0:55

1 Answer 1

3
$\begingroup$

First of all, notice that there are only two possible generic patterns: $[1,3,3]$ and $[2,2,3]$. In total with permutations $6$ ($3$ of each).

Consider pattern $[1,3,3]$: there are $7!$ ways to assign piece of fruit to the day, but as far as pieces of fruites of the same type are indistinguishable, we should take into account their permutations: $$ \frac{7!}{3!3!1!}=140 $$ The same for $[2,2,3]$: $$ \frac{7!}{2!2!3!}=210 $$ Then, final result: $$ 3*140+3*210=1050 $$ Alternative solution

Let us now instead of possible patterns count impossible patterns: $[7,0,0];[6,1,0];[5,2,0];[5,1,1];[4,3,0];[4,2,1]$.

Respective numbers of possible permutations: $3;6;6;3;6;6.$

Then, result: $$ 3^7-\left(3\frac{7!}{7!0!0!}+6\frac{7!}{6!1!0!}+6\frac{7!}{5!2!0!}+3\frac{7!}{5!1!1!}+6\frac{7!}{4!3!0!}+6\frac{7!}{4!2!1!}\right)=$$ $$ 2187-1137=1050 $$

$\endgroup$
5
  • $\begingroup$ Why multiply by 3? $\endgroup$
    – Gerard L.
    Oct 19, 2016 at 0:28
  • $\begingroup$ @GerardL.: permutations of generic patterns (e.g {1-apple, 3-orange, 3-banana}, {3-apple, 1-orange, 3-banana}, {3-apple, 3-orange, 1-banana}) $\endgroup$ Oct 19, 2016 at 0:32
  • $\begingroup$ I think you got the wrong answer. I think you calculated the incorrect rearrangements that are supposed to be subtracted from 3^7 $\endgroup$
    – Gerard L.
    Oct 19, 2016 at 0:55
  • $\begingroup$ @GerardL.: please explain yourself, because subtracting from $3^7$ implies that impossible states like $[5,1,1]$ should be calculated, which is not the case $\endgroup$ Oct 19, 2016 at 0:58
  • $\begingroup$ @GerardL.: I added the solution which uses subtraction from $3^7$, so it should be clear now $\endgroup$ Oct 19, 2016 at 1:34

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .