No. Color vertex if buying ticket. Connect edge if friends. Note quantity (colored vertices) + (edge connecting a colored with a noncolored vertex) remains nonincreasing while updating color of vertices. Quantity starts at $20$, must end at $22$ right before the last guy gets updated (if all can be colored), which is impossible

I had an idea which I believe should lead to a solution. We can force the graph to be connected and now we consider the BFS Spanning Tree rooted at the first vertex that gets coloured. One of the branches will have only one red vertex initially so we would have a lot of cycles passing through this branch which increases the number of edges by a lot which is bad, would be really cool to see a solution with this idea

The answer is no. Construct a simple graph $G = (V,E)$ to represent the question statement. Call a point colored if the person corresponding to it bought a ticket. For some uncolored point v, let $f(v)$ be the number of colored points connected to v. Let $P = \sum_{v \in V} f(v)$. Whenever a point becomes colored, $P$ decreases by 2 and increases by 1. Hence, whenever a point becomes colored $P$ decreases by 1. Since at the beginning $P \leq 14$ and P cannot be negative, there cannot be more than 19 students who bought a ticket. Note: This question is an easier version of 2022 USAMO Q6.

Consider the graph, draw the two edges that "caused" a student to buy a ticket (if there are 3 of them just colour any 2). If everyone buys tickets there are $2\times (20-5)=30$ coloured edges. However there are exactly $\frac{3\times20}{2}=30$ edges. Furthermore the last guy can have at most 2 coloured edges, so there are at most 29 coloured edges, contradiction.

Hint:$E_G(S)$ is strictly decreasing.($S{}$ is the set of students who have ticket.)

bhan2025 wrote: I can see how P <= 15, how do you get that down to 14? I think P <= 15 but, for another ticket to be bought p > 1 (instead of 0) (you need at least 2 coloured neighbours in the graph to trigger a purchase.) And then the reasoning works. Seems you can prove constructively that given n initial ticket holders, you can add people to the network until there are 4n-1 ticket holders.

Posting my solution because it seems to be different in flavour than other posted solutions. The answer is no. Suppose, for a contradiction, that it is possible for all students to buy tickets to the concert. Construct the graph $G = (V, E)$ where $V$ consists of the students and $E$ consists of the pairs of students which are close friends. We have that $|V| = 20$ and $|E| = 30$. Let $S$ be the set of students that did not buy tickets initially with $|S| = 15$. Note that the induced subgraph $G[S]$ must have no cycles as otherwise all the vertices of the cycle would never buy tickets to the concert. Thus, $G[S]$ is a forest with $15$ vertices and so it has at most $14$ edges. Finally, there are at most $15$ edges with at least one endpoint in the set $V - S$ for a total number of edges of at most $14 + 15 = 29$ which is less than $30$, contradiction.

Notice that between all the 30 edges there are at least 15 which do not have one of the 5 initial classmates as a vertex. So we have that the 15 classmates which didn't buy the ticket in the first place have at least 15 friendships between them. This means that there is a cycle of friendships in these 15 people and since no person has already buy a ticket no one in this cycle can buy a ticket ( which proves a little stronger result since we'll have at least 3 people which won't buy the ticket )

Nope. After the $t$-th student is added, let the maximum possible number of edges between the $(5+t)$ ticketholders and the other $15-t$ people be $E_t$. Clearly, $E_0=3\cdot 5 = 15$. Now, note that every time a student is added, two edges are used, and only one is gained, so $E_14 = 15-14 = 1$. Then, there is only one available edge, so we cannot add a 15th, and therefore it is impossible for all 20 students to buy tickets.

Assume for the sake of contradiction that every student will eventually buy a ticket. For any student $s$, we draw the two arrows to the two friends that triggered $s$ to buy a ticket. 15 students do not initially have a ticket, so there will be $30$ arrows in total. Of each of the $5$ students who initially had a ticket, there are at most $3$ arrows pointing away from them, for a total of at most $15$ arrows pointing away from the initial $5$ students. For any other of the $15$ students, there is at most one arrow pointing away from each, since two other of their friends have arrows pointing toward them. Moreover, some student had no arrows pointing away from them since some student must be the last to buy a ticket. Thus, there are not more than $15 + 14 = 29$ arrows. Contradiction.

(Answer)= No it's not possible Denote set of all students who don't have ticket to be $\mathcal{F}$. Call friend pair $(\Omega , \mho)$ partial induced substructure if $\Omega$ is having ticket and $\mho$ not. And for a person $p$ that didn't bought a ticket , define $\mathcal{O}_{p}$ to be the total number of partial induced substructure for $p$. Notice for $\mho$ buying ticket we must have $\mathcal{O}_{\mho} \geqslant 2$ and $\mathcal{O}_{\mho}$ now can have at most $1$ non- partial induced substructure, so every time a person buys ticket (other than those $5$ who have bought) , it can form a partial induced substructure to other student having no tickets only once, hence we must have $\sum_{p \in \mathcal{F}} \mathcal{O}_{p}$ to be decreasing by $1$. FTSOC consider that all students are at concert , then we notice initially $3\cdot 5=15$ freindships are there , and after $14$ person's buy ticket ,we get the $\mathcal{O}_{\text{last student}} \leqslant 1$, but that is impossible for last student to be present as we must have $\mathcal{O}_{\text{last student}} \geqslant 2$. Hence this is a contradiction $\blacksquare$

The answer is no. Let the 5 friends be the vertices of a pentagon each sharing a mutual friend with their adjacent vertices.Now create an inward web like structure withs each point extending exactly 3 lines. You will notice that the structure will terminate when a total of 18 friends buy tickets. Hence the whole class does not buy tickets. Is my solution correct? I did not show a contradiction but instead showed the maximum number of students that can be pressured.

If a student buy a ticket because of his two friends bought it, then we color the edge between him and his two friend red. if there are three then only color two of them Each student needs two red edges to buy a ticket, so there will be $30$ red edges. But the last person would got three friends bought a ticket, so only two of the edges will be red. The total number of the edge is only $30$ and at least one will be non-red, we're done.