I Have To Be With Them!

Question

It's almost time for another year of school! But before school starts, Principal Little needs to form classes. Because there are so many people in a class, the parents are always complaining, asking why the Principal could not just split the classes up to include another class. Being ignorant, the Principal does not pay attention. Every year, as the Principal is the one who makes the classes, it seems that there is not hope. However, this year, the Principal has made a change: Each student is allowed to request 3 friends to be with, and at least one will be in the same class as them. You, as the students' favorite teacher, have been begged by the parents to think of a plan to guarantee that there will be 5 classes instead of the usual 4. Here are the rules:

1. There are always 65 students in a grade

2. There can be at most 18 students in a class

3. If there is a way to have 4 classes, the Principal will have 4 classes

4. There are 4 pairs of siblings. Siblings can not be in the same class, and can not request the other sibling.

5. 5 people left the school last year, and can not request or be requested

6. 5 new people will join this year, and they can also not request or be requested

7. The kids will be bribed by their parents to listen to you

Is there any way for the students to work together and force the Principal to put them in 5 classes?

Bonus:

1. Can you do it if 5 very smart unknown students are trying to sabotage you?

2. Is there a way to have 6 classes?

3. Can you do it if you request 4 friends instead of 3?

4. What about if siblings can't request each other?

Answer 1

Basic solution:

Take 6 students out of given 60, get 54 = 3*18. Then we split these students in 18 groups of 3, indexed like so: 1.1, 1.2, 1.3, 2.1, 2.2, 2.3, ..., 18.2, 18.3.
Now let's get over with these students. 1.1, 1.2 and 1.3 ask for joining 2.1, 2.2, 2.3; 2.1, 2.2, 2.3 ask to join 3.1, 3.2, 3.3 and so on. 18th group asks to join some pupils in a way that it doesn't create an impossible situation (for example 18.n asks for 1.n, 2.n, 3.n). What do we achieve by that ordering?
A pupil from group 1 needs a pupil from group 2, needing a... etc, etc, we create a class having a student from each group. Moreover, it has exactly one student of each group, since 18 is the max border for a class.

Having three classes filled tight, we just need two more. Just leaving out a pair of siblings we create a need for two more classes.

Note that

This strategy is unbalanced, in a way that we create 3x18 classes and 2 classes with 11 students total (much less practical, than jafe's approach). However, we can go further and make an even more ridiculous split this way.

Solution for bonus #2 (six classes):

We have 6 (six) spare students now (actually 11, but 5 are new-year dummies). Let's use them to the fullest! Get three sibling-pairs, as A, A', B, B', C and C'. They don't care about 3-friend restriction - they can ask for friends from full classes, knowing, that taking them is impossible.
Now let them group as AB', BC' and CA'. Due to the sibling rule, none of these clusters can be brought together - therefore, last 11 students split between three classes, giving us 6 total.

P.S: This also qualifies for bonus #4 now, since nowhere in the strategy we need a sibling requesting another sibling.

Answer 2

I know next to nothing about graph theory. But that won't stop me from giving this a go. :)

One primitive approach could be to assume that each student won't have to request exactly 3 friends each, but up to 3 friends each. (Or alternately can use the same friend for all of their three possible requests) This will leave us with a fairly straightforward solution:

Divide the 60 students into 5 classes of 12 students each.

For each class, student number 1 will only request to be with student number 2 of the same class. Number 2 will only request to be with number 3. All the way up to number 12, that will only request to be with number 1.

This will create an unbreakable entity, as removing any one of these students, will leave some other student with their 1-friend guarantee unfulfilled.

The 5 classes of 12 students will be too large to combine, as this will make the combined class exceed the limit of 18.

The remaining 5 students can be put in any of the five classes, without impacting the intent of creating (at least) five classes.

If this assumption is valid, then bonus question 2 will be "Yes". Just split the students into 6 classes of 10 instead.

Answer 3

Assuming siblings can request each other:

1. Pick three students who have siblings (A, B and C). Each of these requests the other two as well as their own sibling.
2. 15 students request A, B and C.
3. 9 students request A, B and A's sibling.
4. 9 students request A, B and B's sibling.
5. 9 students request A, B and C's sibling.
6. Pick one of the remaining students (D). All the remaining students request A, B and D.

Explanation:

Step 1: A, B and C have to be in the same class, since nobody can be in the same class as their sibling and there is no way to divide a group of three without leaving someone alone. (3 students in class 1)
Step 2: All 15 students have to be in the same class as A, B and C. (18 students in class 1)
Step 3: Nobody can be paired with A or B, because there is no more room in class 1. A's sibling and 9 other students form a new class. (10 students in class 2)
Step 4: Again, nobody can be paired with A or B. B's sibling has to be in the same class as 9 other students, and there is not enough room in class 2 for 10 more students. So a new class is needed. (10 students in class 3)
Step 5: Similar situation as above, no more room in either class for 10 more students. (10 students in class 4)
Step 6: A and B still can't be paired, so everyone needs to be in the same class. Since there is not enough room in any of the existing classes, this forces the creation of a fifth class.

Answer 4

There is a way to have no school at all:

Split the $60$ students that can be requested into $20$ groups of $3$ students ($A_{1}$ to $A_{20}$), putting siblings into the same group to avoid problems. Have each student in $A_{1}$ request every student from $A_{2}$ and so on until each student in $A_{20}$ requests every student in $A_{1}$. This would mean that any class would have to have at least $20$ students, a clear violation of the second point.

(When the principal notices this dilemma offer a compromise where not everyone gets someone they requested but there will be five or even six classes.)

Answer 5

After reading some of the responses, I got inspired to a new solution.

Reading the puzzle, and in particular bonus question 2, I suspect it will be acceptable to make a solution that simply aims for 6 classes...?

Take the 60 students, and split them into 20 groups of 3.
It almost won't matter where you put the siblings. Just make sure they are not placed in adjacent groups.

Split the 20 groups into two halves with 10 groups in each half. Half 1 is A and half 2 is B
First group of A is A1. Second group of A is A2. And so on. Same for B.
All the A1 students will wish for all the students in A2. All in A2 will wish for the students in A3. Up to A10, which will wish for all the students in A1. Same for B.
This will generate a constellation that will have to be broken down, as the combined circle contains 30 students, which is too big for a single class. But it won't be possible to make these smaller than three circles containing 10 students each without breaking the one wish fulfilled guarantee.
You will get another three circles from the B group, totalling six circles of 10 students each.

These are not possible to break down any further, and they are too big to combine for a single class.

The remaining 5 students can be distributed any way you want, but will most likely be put in 5 different classes, making the total of 6 classes with 11 students and a single class with 10 student.

Bonus question 1 : I don't think it will be possible to make a bulletproof plan then. I believe these 5 students always - regardless of them being placed the same class or put in different classes - will be able to create a circle of their own, that can be taken out. This will - at least with this approach - mean that some classes will become small enough, that it will be possible join them in a larger class.

Bonus question 2 : Already done. :)

Answer 6

Make a group of 4 students, have each friend all the others.

Have EVERY other student in the class request the first two students from the group of four as two of their "friends".

Stand the remaining students in five circles, one of size 12, four circles of size 11. Each child in the circle uses their remaining friend request for the child on their right.

Any class which doesn't have one of the two popular students MUST have an entire ring (rings must be legal and follow sibling rules).

A class with a popular student could have 2 of the group of 4, a full ring (11), but that's 13 so they can't also take half a ring (6) so they can't fully split a ring.

Other people have answered the bonus questions and this approach fails for 6 classes or 4 picks.