12
$\begingroup$

There is a group of 300 Twitter users. Each user is following exactly one other user in the group. Prove that there exists a smaller group of 100 users where no one is following anyone else.

Source: Aust MS Gazette Puzzle Corner 43

$\endgroup$
  • $\begingroup$ should that end "anyone else in the group"? Because otherwise it doesn't make sense to me. $\endgroup$ – Kate Gregory Sep 17 '15 at 12:39
  • $\begingroup$ The "where" implies "within the group". Obviously, since everyone must follow someone, the alternative makes no sense. $\endgroup$ – Roland Sep 17 '15 at 18:19
6
$\begingroup$

Imagine all 300 Twitterites are standing in a room. Each person follows one other, so the average number of followers a person has is one. This means there exists a person $P$ with at most one follower. We select person $P$ to be in the smaller group, and we dismiss the person $P$ follows and the one person following $P$ (if there is such a person) from the room. Now nobody left in the room follows or is followed by $P$.

We repeat this process. Each time, we choose a person in the room who has at most one follower still in the room, we add that person to the smaller group, and we lose at most three people from the room (the person we add to the smaller group, the person they follow, and the person following them, if there is one). The room starts with 300 people, so we can do this 100 times, resulting in a small group of 100 people in which nobody follows anybody else.

$\endgroup$
  • $\begingroup$ If God kept a book of the most elegant proofs of every theorem, this would be the proof he used :) $\endgroup$ – Mike Earnest Sep 17 '15 at 18:25
6
$\begingroup$

We consider the directed graph G=(V,E) of all Twitter users, such that V={1,2,...,300} and $(i,j)\in E$ if and only if user $i$ follows user $j$. Since every node has outgoing degree of $1$, the graph contains several cycles and each of the other nodes is path connected to one of the cycles, i.e. for every user $i$ not belonging to a cycle and every cycle $C$, there is succession of users $a_1, a_2, ... , a_k$, such that user $i$ follows $a1$, $a1$ follows $a_2$, ... , $a_k$ follows someone from $C$.

Thus we can conclude that the graph can be split into $l$ independent subgraphs, where $l$ is the number of cycles in $G$. Alternatively, we can assume that $G$ has size $n$, contains just one cycle and we want to prove that we can choose $\lceil n/3\rceil$ users in it. Now arrange the users in layers.

First layer - the users belonging to the cycle.

Second layer - the users who follow someone from the cycle.

Third layer - the users who follow someone following someone from the cycle.

and so on...

Now let the number of people in the first layer is $x_0$, the number of people in the second layer is $x_1$, the number of people in the third layer is $x_2$, etc. Clearly, if $$\lfloor x_0/2\rfloor + x_2+ x_4+... \geq \lceil n/3\rceil$$ or $$x_1+x_3+x_5+...\geq \lceil n/3\rceil,$$ then the problem is solved. In the first case we just choose every other user in the cycle + the users in the even layers, in the second case we choose the users in the odd layer. If we assume that these two inequalities are not true, then $$\lfloor x_0/2\rfloor +x_1+x_2+...\leq 2\lceil n/3\rceil-2$$ and since $$x_0+x_1+x_2+...=n,$$ we get $$n+2-2\lceil n/3\rceil \leq \lceil x_0/2\rceil.$$

The last expression, combined with $$\lfloor x_0/2\rfloor + x_2+ x_4+... \leq \lceil n/3\rceil -1$$ gives $$n+3 + x_2 + x_4 + ...\leq 3 \lceil n/3 \rceil +\lceil x_0/2 \rceil - \lfloor x_0/2 \rfloor \leq 3\lceil n/3 \rceil +1,$$ which is possible only if $x_0$ is odd, $n=3m+1, x_2=x_4=...=0$ and then $x_i=0$ for $i\geq 2$ (this is true because the third layer is empty and therefore all successive layers are empty as well). Then we have

$$\lfloor x_0/2 \rfloor \leq m,$$ $$x_1 \leq m,$$ $$x_0+x_1=3m+1.$$

Now the only option is $x_0=2m+1$ and $x_1=m$. Since $m\geq 1$, there is at least one user U in the second layer. He follows some user V from the first layer. Now we take again $m$ users from the first layer which do not follow each other, skipping user V. Then add user U to the bunch and eventually find $m+1$ users which satisfy the condition.

Also, using the arguments above we can easily conclude that the extremal case is when the graph $G$ is consisted of several subgraphs, which are either $3$-cycles or $3$-cycles with one additional user which follows someone from the $3$-cycle.

$\endgroup$
  • $\begingroup$ I'm sure there is some minor tweak that will fix this, but what if $x_0 = 3$, $x_1 = 1$, and $n = 4$? Then the statement that you're trying to prove (about one of the two inequalities at the top being true) is false. $\endgroup$ – Tyler Seacrest Sep 16 '15 at 22:41
  • $\begingroup$ Oh yes, made a little mistake in the proof. Thanks, will fix it easily now. $\endgroup$ – Puzzle Prime Sep 17 '15 at 0:47
  • $\begingroup$ I lost you when you said $x_i = 0$ for $i \geq 2$. Can you explain that part? Also, if that's true, then from $x_0 + x_1 + \ldots = n = 3m+1$ we have $x_0 + x_1 = 3m+1$, not $3m$. Perhaps you can give more explanations? $\endgroup$ – justhalf Sep 17 '15 at 1:41
  • $\begingroup$ @justhalf, if you know that $x_2=0$, this means that the third layer is empty. This directly implies that the fourth, fifth, etc. layers are empty as well. And yes, $x_0+x_1$ should be equal to $3m+1$, will fix the typo now. Thanks! $\endgroup$ – Puzzle Prime Sep 17 '15 at 2:17
  • $\begingroup$ Ah, yes, so it comes from the definition of the layers. I think you can explicitly write the restriction $x_1 \geq x_2 \geq x_3 \geq \ldots$ if you think that makes things easier to understand. $\endgroup$ – justhalf Sep 17 '15 at 2:18
1
$\begingroup$

I had a bit of a hard time understanding Artur's answer becuase of the mathematics involved. So I tried to came up with my own solution. I got one and I think it's correct and of course it also involves mathematics but I believe it is easier to understand.

Let us define all people as $S$

First, we divide the people in 3 groups:

  • $X$ the people that are not being followed at all

  • $Y$ the people not in $X$ and that are also not being followed by anyone in $X$, note that $Y \ge S - 2X$

  • $Z$ the rest, note that $Z \le X$

Let's also define $Q$, a subgroup of $Y$:

  • the people in $Y$ that are also not being followed by anyone in $Z$. note $Q \ge S - 3X$

And then always pick everyone from $X$.

Now with $S=300$ as the problem states:

if $X \ge 100$, you're done.

if $X = 99$, the last 1 you pick just needs to be anyone of $Y$ and $Y \ge 102$

if $X = 98$. Now we want to take the remaining 2 from $Q$. $Q \ge 6$. Notice something familiar? 2 is one third of 6, just like the original problem. In the worst case all people in $Q$ follows someone else in $Q$, but anyhow, with this group $Q$ we just start over and do the algorithm again, since this algorithm guarantees that one third gets picked.

Because in general:

if $X \ge S/3$, you're done.

For any $M > 0$
if $X = S/3 - M$, then $Q \ge 3M$ and we can do this algorithm again with $Q$ which will get us $M$ people picked.

There is one corner-case and that is when $X = 0$. This means that there are only seperate cycles. In the best case there is only one cycle and then you can pick every other person. In the worst case there are only cycles of 3 people and then you can pick 1 person from every cycle.

$\endgroup$
  • $\begingroup$ I think you can simplify it even more - if there is someone who is not followed by others, then you choose him, remove the person whom he is following and increase the pick-ratio to 50% (or more), which is even better. Continue like this until everyone is followed by at least one other person, i.e. you have only cycles. Now pick every other person from each cycle, which gives you in the worst case 1/3 of the users (when you have only 3-cycles remaining). $\endgroup$ – Puzzle Prime Sep 17 '15 at 16:08
  • $\begingroup$ @ArturKirkoryan nice find :) that is indeed true. By the way, as someone who is more into math, do you think my answer makes sense? $\endgroup$ – Ivo Beckers Sep 17 '15 at 16:13
  • 1
    $\begingroup$ Yeah, actually my suggestion was based on your answer - you don't need to remove both the people followed by X's and the people followed by people followed by X's, the first is just enough. $\endgroup$ – Puzzle Prime Sep 17 '15 at 16:16
0
$\begingroup$

The Obligatory MS Paint Images (now with Word 2010!)
Since each Twitter user must be connected with at least one other user, each will be a part of a larger network of 2-N users. In each independent group of users, we will look at how many we can isolate. Obviously, we can treat each separate group independently; if there were a connection between the two, they would become one larger group to be analyzed.
If ANY group of M members (for which M|N) forbids isolating (in green) one third or more of its members, we have failed

1. Two mutually following: (1,1) Here we can just pick one of the indistinguishable Twitter users. We get $1/2$ of all users in groups of two.

enter image description here

2. Three followed by (1,1,1) and (2,1,0) There are only two ways for this independent group to follow each other, since no user can follow oneself. Here we have our worst passing case, $1/3$ of members in a (1,1,1) group, and $2/3$ from the (2,1,0).

enter image description here

3. Four followed by (1,1,1,1), (2,1,1,0), (2,2,0,0), and (3,1,0,0) As the groups get larger and more complex, it becomes impossible to pick fewer than $1/3$ of users.
In the (1,1,1,1): For this and larger simple cycles of (1,1,1...,1), we can always choose every other user. For even M, we isolate $1/2$ of users. For odd M, we have $(M-1)/2$ users, which is lowest at (1,1,1), $1/3$.
In each other case: We can represent the group as a smaller group with one or more outsiders, followed by zero people themselves. This will always allow for at least as many isolations as the minimal (1,1,1) case, as seen in the images of (2,1,1,0), (2,2,0,0), and (3,1,0,0).

enter image description here

Finally, since each possible group of M users -- from $M = 2$ to $M = N$ -- allows for at least $1/3$ of the users to be isolated, at least $1/3$ of the total N users MUST be isolated from each other. For $N = 300$, this is $100$ Twitter users.

$\endgroup$
-1
$\begingroup$

If each user is following exactly one other user, then it can be a ring of 300 users forming a circle.

Pulling every third person from that loop will give you a group of 100 users who are not following the next person in the subgroup. Even pulling every OTHER person in the big loop will do that for 150 people total.

The other extreme has 299 users following user $a$, and user $a$ follows one other user.

Both situations provide the required criteria of at least 100 users that are not following another user in the subgroup.

You could also have 150 groups of users following each other in pairs. That's over 100.

you could even have 100 groups of three users forming small circles, which is equivalent to the big circle approach, you'd just end up taking one person from each circle.

I'm sure someone will swoop in with a mathematical proof that it goes from 100 to 299 based on the number of loops or something but it seems so obvious to me that I don't feel the need to bust out the groan-inducing calculus.

$\endgroup$
  • $\begingroup$ Not necessarily a ring, but I think you're on the right track. $\endgroup$ – squeamish ossifrage Sep 16 '15 at 21:02
  • $\begingroup$ It doesn't say that each person is followed by one other. $\endgroup$ – Roland Sep 16 '15 at 21:02
  • 2
    $\begingroup$ What if everyone's following one person, except for that person who follows some other random user? $\endgroup$ – Zandar Sep 16 '15 at 21:02
  • 2
    $\begingroup$ Your solution doesn't seem very rigorous. In fact, your assertion that a ring of 300 users is "the closest you can get to NOT fulfilling the requirement" is just plain wrong. (Why select every third user? Why not every second user?) $\endgroup$ – squeamish ossifrage Sep 16 '15 at 21:12
  • $\begingroup$ You know I can't figure out why I did that either. $\endgroup$ – Kingrames Sep 16 '15 at 21:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.