Pigeon groupings

Question

Question:There are $51$ pigeons in a flock. The flock is divided into $n$ groups so that each pigeon is in exactly $1$ group. However, every pigeon dislikes exactly $3$ pigeons and thus does not want to be in the same group as the $3$. Find the smallest number $n$ such that it is always possible to arrange the groups so that no pigeon is uncomfortable with the groupings. Note: Even if, for example, pigeon $A$ dislikes pigeon $B$, pigeon $B$ does not necessarily dislike pigeon $A$.

I just want to check my answer, is it 5? thanks Edit: 5 is wrong and my new solution is listed at the end of my proof.

My solution: Let the pigeons that pigeon $a_i$ hates be $a_{i+1}, a_{i+2}, a_{i+3}$ and let $a_{i+51} = a_{i}.$

Now we can make the groups. With group 1, we can let $a_1$ be in it. The next pigeon that can be in the group is $a_5.$ In general we can put the pigeons in the form $a_{1+4n}$ except $a_{49}$ since $a_{49}$ hates $a_1.$ Therefore, group 1 has 11 members.

Moving on to group 2, we put $a_2$ in it. Like the first group the pigeons in the form $a_{2+4n}$ can be in group 2 except for the last pigeon which hates $a_2.$

We can redo these procedures for groups 3 and 4. We cannot do it for group 5.However we still have $a_{49}, a_{50}, a_{51}$ left over. The dislike each other however, so we need to put them in separate groups.

Therefore the minimum groups is $\boxed{7}.$

What matters more than the answer is how you arrived at it. For all we know, if $5$ were correct, you could have, by chance, got that fallaciously. — Shaun, Jul 28 '20 at 00:17
Thank you, can you check if this answer and solution is valid? Thanks. — Michael Li, Jul 28 '20 at 00:30
You're welcome. It's a bit late where I am (at approximately 01:34 in England), so I'm too tired right now. Maybe I'll provide an answer several hours from now. — Shaun, Jul 28 '20 at 00:34
How do you know that $a_5$ doesn't dislike $a_1$ and cannot go in the same group? — Brian M. Scott, Jul 28 '20 at 00:43
@BrianM.Scott Because they only hate 3 other pigeons so $a_1$ hates $a_2, a_3, a_4$ only, not $a_5.$ Also, $a_5$ hates $a_6, a_7, a_8.$ — Michael Li, Jul 28 '20 at 00:46
Your construction does not work, as $a_{49}$ hates $a_{50}$ and $a_{51}$ so they cannot all go in the same group. You cannot prove that $5$ groups suffice with just one construction. You can prove a minimum number of groups that can be forced by one construction. — Ross Millikan, Jul 28 '20 at 01:03
I don't understand this. You say $a_i$ hates $a_{1+1},a_{i+2},a_{i+3}$ That means that $a_1$ hates $a_2,a_3,a_4$, and $a_2$ hates $a_3,a_4,a_5$ and so on, so you have lots of pairs who hate two of the same individuals. Nothing in the problem statement suggests that there is such a structure. — saulspatz, Jul 28 '20 at 01:20
@ᄂIMIᄃΉΛΣᄂ: I understand that $a_1$ does not dislike $a_5$; by your own statement, however, $a_5$ may nevertheless dislike $a_1$. — Brian M. Scott, Jul 28 '20 at 01:23
Does anyone have another solution that could solve the problem? — Michael Li, Jul 28 '20 at 01:28
by your logic, no pair of pigeons hate each other. the problem statement does not say so. — acat3, Jul 28 '20 at 01:34
Does it matter whether hate is symmetric, when sharing the same group is symmetric? — Brian Tung, Jul 28 '20 at 02:10
Did you edit your question to include my answer, yet not accept or comment on the actual answer? @ᄂIMIᄃΉΛΣᄂ — RSpeciel, Jul 28 '20 at 16:12
@RomainS As you can see in comment #10, I had already realized the answer was seven. — Michael Li, Jul 28 '20 at 17:44

RSpeciel · Answer 1 · 2020-07-28T02:05:34.120

The minimum number of groups is $7$.

Proof: We first show that we need no more than $7$ groups, by induction. Let $p$ denote the number of pigeons; clearly the claim hold for $p=7$. Now, suppose it holds for some $p=k$. When we have $k+1$ pigeons, there must be at least one pigeon which is disliked by at most $3$ pigeons. Remove this pigeon, and group the remaining $k$ pigeons into $7$ groups. Reintroducing the removed pigeon, we see that it dislikes $3$ others, and is disliked by at most $3$, hence there must be at least $7-(3+3)=1$ group into which this pigeon can fit. This concludes the argument, by induction.

To see why we need at least $7$ groups, consider a graph with vertices $a_0,\dots, a_6$ and a directed edge between $a_i$ and $a_{i+1},a_{i+2},a_{i+3}$, with the indices taken$\mod 7$. This arrangement would clearly require at least $7$ groups (draw it!), and could certainly appear as a subgraph of any pigeon setup, regardless of the number of pigeons.

Still curious? Look into graph colorings, you'll find many more similar problems!

Pigeon groupings

1 Answers1