Now, we switch from number theory to graph theory.

It is also a part of our course but now we are using the graphs in a very simple way.

So, here is the puzzle.

There are three hotels in a town A,

B and C and you have vouchers.

You have 10 vouchers for hotel A,

15 vouchers for B and 20 for C but there is a restriction.

The hotel does not allow you to use the voucher two nights in a row.

So you need to change hotels.

Every night you should move to a different hotel.

So, somehow you can symbolically draw this A, B,

C as hotels and every day you should take the green line,

move along the green line from one hotel to another.

The question is whether it is possible to do this for 45 consecutive nights.

What do you think? Here are the hints.

You can, it is not obligatory, but let's try.

We can try to repeat five times a path of length nine.

So, you see that all these numbers are a multiple of five.

So, if we can solve the same problem with two,

three and four then we can repeat

the solution several times and get the solution for the original problem.

There is one subtle thing here,

did you see what is wrong in what I have said?

Actually, the path for a smaller problem should have different endpoints,

it should not end where it started because otherwise when we combine

this path together we get a problem when switching from one to the other.

So, the initial point should be different from the final point.

Okay, but still let us try to find this.

So we have a path of length nine and it should use two,

three and four times A,B and C. So,

path of length nine and C should appear there four times.

So, C cannot appear twice in a row.

So, it is natural to try C with distance two and put something in between.

So, let us decide that every second point is C,

let us try it and then it is rather easy.

We start with A, C, A,

C so we use A twice, as is required.

And then we switch to B,

since A we already used, B, C, B, C and B.

So we have a path of length nine

and the end point is different from the starting point so,

we can just repeat it like this,

just play the same second time and five times.

So, in this way we get the solution.

We proved that we can find a way

to spend all of our vouchers without violating the rules of the hotels.

This is a positive case but sometimes the task is impossible.

Let us look at an impossible case.

So, imagine we have more vouchers for C. We have 13 vouchers for C and then we

can try to spend 45 nights.

Is it possible or not, what do you think?

Do you see an obstacle for that?

And the obstacle is that we have too many vouchers for C. We have

45 nights and 30 vouchers for C and we cannot use them twice in a row.

So, between every two C,

there should be at least one A or B.

So, if we have 30 Cs we should fill

somehow at least 29 hotels and we have only 10 and 15.

So, that is not enough hotels that can be used between Cs.

We need at least 29 others and we do not have them.