(Putnam 1999 B6) Let $S$ be a finite site of positive integers. Suppose for any positive integer $n$, $(n,s)$ is either 1 or $s$. Show that there exists $s,t\in S$ such that $(s,t)$ is prime.

Remarks. I never understood how to figure out the extremal solution for this. Like, what are you supposed to do, just guess?

Walkthrough. Of course, the first thing to try is $|S| =1$. It is obvious that if $(n,s) = 1$ or $s$ always, then $s$ itself has to be prime! But which $n$ tells us that? We can think of it by “varying $n$” - $1=n_0 \mid n_1 \mid ... \mid n_k$, and of course at each step we add in a prime factor so that $(n,s)$ varies by a prime factor, but somehow the conditions dictate that it must jump from 1 to $s$. So on the very first prime factor it must jump to $s$ which means that $s$ itself is prime.

What about general $S$? Consider the $|S|$-tuples $\{(n,s_i)\}_i$, and once again we want to increase $n$ one prime factor at a time. This increases each entry by at most one prime factor at a time. However, all we know is among them there is at least one 1 or one $s$.

So the strategy is to start at $n_0=1$, and slowly clear out all the 1’s. The prime we will add in should remove at least one 1. Specifically, we will do $n_i = p_in_{i-1}$ where $p_i | s_m$ for an index $m$ with $(n,s_m) = 1$.

The number of 1’s strictly decrease so eventually there are no 1’s. What happens here? Aha, something has hit $s$. In fact, let’s go back in time to see the first time something hits an $s$: so we have $(n_t,s') = s'$, but $(n_{t-1},s') = s' / p$ for some prime $p$, which has to come from another $s''\in S$ (i.e. $p|s''$). So now compare $(s',s'')$: $s'$ is entirely contained in $n_t$, which has all the prime factors we added, but exactly one of those contributed to $s''$, so $(s',s'') = p$, done!

(Turkey TST 18 Q5) Fix a positive integer $k$. A graph $G$ has the property that every vertex is part of a clique of size $k$, but removing any edge will make this property false. Show that for any two adjacent vertices, there is a clique of size $k$ containing them where some vertex in the clique is only adjacent to other vertices in the clique.

The hard step is finding a good way to interpret the conditions, but a hint is that we really care about $k$-cliques.

For each vertex $v$, let $S(v)$ denote the $k$-cliques that contain $v$. Now, we see that if $v_1,v_2$ are adjacent, then the cliques that contain the edge $v_1v_2$ are precisely $S(v_1)\cap S(v_2)$. Removing this edge nukes all the cliques of some other vertex $w$, so we can write this as $$S(v_1)\cap S(v_2)\supset S(w)$$ Additionally, each clique in $S(w)$ must contain $v_1v_2$ (otherwise it doesn’t get nuked). Anyway, this should give you some ideas already: somehow we can always produce a smaller $|S(w)|$…

Anyway, let’s look at what we want to prove: for any adjacent $v_1,v_2$, we need to find a vertex $w$ contained in $C \in S(v_1)\cap S(v_2)$ with no neighbors outside $C$.

Let’s take $w$ as above. What if it’s connected to something outside $C$ (say, $w_1$)? Then the condition gives $$S(w)\cap S(w_1) \supsetneq S(w_2)$$ where the strictness comes because we lose $C$. But more amazingly, $S(w_2)$ inherits from $S(w)$ the property that each of its cliques contains $v_1v_2$! So $|S(w_2)| < |S(w)|$, with $w_2$ having the exact same properties as $w$.