Combinatorics on hotel vouchers problem

Question

I'm taking an online Discrete Mathematics course because I know it is very useful if you want to get into Computer Science.

This is the question I'm struggling with.

You have vouchers for three hotels: A, B and C. You have 10 vouchers for hotel A, 15 vouchers for hotel B and 20 vouchers for hotel C.

There is one restriction though. You cannot sleep in one hotel for two nights in a row, so you must switch hotels every night. Is it possible to do this for 45 consecutive nights? 45 is the total amount of vouchers.

I know it is possible as the online professor proved it, but I was confused by his proof and didn't understand how he did it. Appreciate any explanations!

---

Edit: The professor simplified the vouchers for the different hotels since they were all divisible by 5. So hotel A had 2, B had 3, and C had 4. He then put this pattern on the board "ACACBCBCB" and said 'repeat 5 times this path of length 9'. It works, but I'm confused on how he got there. The pattern came out of nowhere.

---

Edit: Thank you all so much on the help. I honestly should have thought about it harder before asking but I'm still super grateful for all the help in helping me understand.

Answer 1

You have to sleep in $C$ $20$ times, and you have to sleep in $A$ and $B$ a total of $25$ times, so you can’t simply alternate between $C$ and the others. If you could use up $5$ of the non-$C$ vouchers first, though, you could alternate the remaining $20$ of them with $C$ vouchers. And this is easy: start by using $BABAB$. You now have $8$ $A$ vouchers, $12$ $B$ vouchers, and $20$ $C$ vouchers, so you can finish with

$$\underbrace{CACA\ldots CA}_{8\times CA}\underbrace{CBCB\ldots CB}_{12\times CB}\,,$$

for instance.

Answer 2

Not difficult:

CBCBCBCBCBCACBCACBCACBCACBCACBABCABCABCABCABC

In summary: (CB) 5 times, (CACB) 5 times, (ABC) 5 times.

Answer 3

Just come up with a solution.

If you alternate $B$ and $C$ you can sleep at $B$ for one night and $C$ then next until you run out of your $15$ $B$ coupons and have $5$ unused $C$ coupons. But you can intersperse those with the $A$ coupons. Until you $C$ coupons and have $5$ unused $A$ coupons. But just intersperse those with the first bunch of vouchers.

So Do $ABC$ five times to use up $5A$s, and $5B$s, and $5C$s. Then to $BC$ ten times to use $5A$s, $15B$s (all), and $15 C$s. Then the $AC$ five to to us up $10A$ and $15B$ and $20C$.

Or you can split the coupons into two sets. One of $23$ nights and on of $22$ nights. One has all the $B$s the other has all the $C$. The $A$ are split but in the start of one and the end of the other. So one set with is $BBBBB....BAAA$ and the other is $AAAAAAACCCC.....C$

So on night $2m +1$ you pick from set $1$ which will be $B$ if $m \le 20$ and $A$ if $m >20$. And on night $2m$ you pick from set $2$ which will be $C$ if $m >7$ and will be $A$ if $m \le 7$. The $B$ and the $C$ will never be concurrent as they are from different sets. ANd the $A$s will never be concurrent as they are in different positions in the two sets.

Alternatively I might think:

First let's place the $C$. Place them one apart.

$-C-C-C-........ -C-----$.

that fills up all the $2k$ for $k\le 20$. In other words all the evens up to $40$.

Now place then $B$s but start from the other end.

$-C-C-C-C-C-C-C-C-CBCBC........ BCBCB-B-B$

That fills up all the odds from $45$ down to ... whatever $45-2*15$ is.... I guess that's $15$.

That leave just the odd numbers up to $15$ and the even numbers more than $40$. Fill them in with $A$s.

$ACACACACACACACACACBCBC........ BCBCBABAB$

There are many ways to solve it.

Answer 4

A more or less direct approach to solving the problem is to set out $20$ $C$'s with spaces between them for $A$'s and $B$'s. Fill the first $15$ spaces with $B$'s and the final $4$ spaces with $A$'s. This leaves you with $6$ $A$'s. You can dispose of $2$ of them before the first and after the final $C$. The final $4$ $A$'s can go into some of the $CBC$'s.

The professor's approach sort of does the same thing with $2$ $A$'s, $3$ $B$'s, and $4$ $C$'s, except it look like they may have simply wedged the $4$ $C$'s in between a starting pattern of $AABBB$ (using the coincidence that $4=(2+3)-1$). The key thing, actually, is that the resulting $9$-character begins and ends with different letters, so that repeating the pattern doesn't violate the rule against consecutive letters being the same.