Can you solve this with expected value? I got a stronger bound that $\frac{1}{2}p$.

For each $k = 0, \dots, p-1$ let $G_k$ be the graph on $\{1, \dots, p\}$ where we join $\{i,j\}$ if and only if \[ a_i + ik \equiv a_j + jk \pmod p \iff k \equiv - \frac{a_i - a_j}{i-j} \pmod p. \]So we want a graph $G_k$ with at least $\tfrac{1}{2} p$ connected components. However, each $\{i,j\}$ appears in exactly one graph $G_k$, so some graph has at most $\tfrac 1p \tbinom p2 = \tfrac{1}{2}(p-1)$ edges (by pigeonhole). This graph has at least $\tfrac{1}{2}(p+1)$ connected components, as desired. Remark: Here is an example for $p=5$ showing equality can occur: \[ \begin{bmatrix} 0 & 0 & 3 & 4 & 3 \\ 0 & 1 & 0 & 2 & 2 \\ 0 & 2 & 2 & 0 & 1 \\ 0 & 3 & 4 & 3 & 0 \\ 0 & 4 & 1 & 1 & 4 \end{bmatrix}. \]

This problem was proposed by me. There is nothing to prove for $p = 2$, so assume $p = 2q + 1$ is odd. Create a $p \times p$ table of numbers, as follows: \begin{tabular}{cccc} $a_1 + 1 \cdot 1$ & $a_2 + 2 \cdot 1$ & $\cdots$ & $a_p + p \cdot 1$\\ $a_1 + 1 \cdot 2$ & $a_2 + 2 \cdot 2$ & $\cdots$ & $a_p + p \cdot 2$\\ $\vdots$ & $\vdots$ & $\ddots$ & $\vdots$\\ $a_1 + 1 \cdot p$ & $a_2 + 2 \cdot p$ & $\cdots$ & $a_p + p \cdot p$\\ \end{tabular}Interpret all the numbers above modulo $p$. Examine two different columns, say $\{a_i + ik\}_k$ and $\{a_j + jk\}_k$. We claim they agree (modulo $p$) in only one row. Indeed, if $a_i + ik \equiv a_j + jk \pmod{p}$, then $(i - j)k \equiv a_j - a_i \pmod{p}$, so since $p$ is prime and $i \not\equiv j \pmod{p}$, it follows that $k \equiv \tfrac{a_j - a_i}{i - j} \pmod{p}$. Thus, there are $\tbinom{p}{2} = \tfrac{p(p - 1)}{2} = pq$ pairs of equivalent entries in the same row in the table. Since there are only $p$ rows, some row, say $\{a_n + nk\}_n$, must have at most $q$ pairs of equivalent entries. We claim that this $k$ is as desired. Suppose not; and let $e_1, \dots, e_q$ be the multiplicities (possibly zero) of the remainders appearing in $\{a_n + nk\}_n$. Then \begin{align*} e_1 + \dots + e_q & = p = 2q + 1,\\ \binom{e_1}{2} + \dots + \binom{e_q}{2} & \le \frac{p - 1}{2} = q. \end{align*}Thus \begin{align*} e_1(e_1 - 1) + \dots + e_q(e_q - 1) & \le 2q,\\ e_1^2 + \dots + e_q^2 & \le 4q + 1. \end{align*}On the other hand, by Cauchy, \[e_1^2 + \dots + e_q^2 \ge \tfrac{1}{q} (e_1 + \dots + e_q)^2 = \tfrac{1}{q} (2q + 1)^2 = 4q + 4 + \tfrac{1}{q},\]a contradiction. Thus the sequence $\{a_n + nk\}_n$ contains at least $\tfrac{1}{2}p$ residues modulo $p$, as desired.

Fix \(p\), and note that we can basically consider the entire problem\(\pmod p\). Moreover, assume for contradiction that no such \(k\) exists. There are only \(p\) values of \(k\) to consider, as we are considering the problem in\(\pmod p\). WLOG pick those \(p\) values to be integers from \(0\) to \(p-1\). Now, let \(i\neq j\) be two positive integers such that \(a_i+ik_1\equiv a_j+jk_1\) for some \(k_1\). Now, if there exists a \(k_2\) such that \(a_i+ik_2\equiv a_j+jk_2\), we can subtract the congruences to obtain that \((i-j)(k_1-k_2)\equiv 0\). Note \(0<i,j\le p\), so we must have \(k_1\equiv k_2\pmod p\). Thus, for every pair \(i,j\), \(a_i+ik\equiv a_j+jk\) for exactly 1 value of \(k\) (among the \(p\) "relevant" values). There are \(\dbinom{p}{2}\) different such pairs \(i,j\). Thus, by pigeonhole, there exists at least one value of \(k\) such that the number of pairs \(i,j\) for that particular \(k\) is at most \(\frac{p-1}{2}\). Now, we can compute the number of pairs in a different way. Consider the set \(b_1, b_2, \ldots b_q\), such that \(q<p/2\) is the number of different residues of \(a_1+k, a_2+2k, \ldots a_p+pk\), and each \(i\) corresponds to a residue such that \(b_i\) is the number of occurences of that residue. This means that \(\sum\limits_{i=1}^q b_i=p\) Note that the number of pairs is going to be \[\sum_{i=1}^q \dbinom{b_i}{2}=\frac{\sum\limits_{i=1}^q b_i^2-\sum\limits_{i=1}^q b_i}{2}=\frac{\sum\limits_{i=1}^q b_i^2-p}{2}.\] By Cauchy-Schwarz, the remaining summation is greater than or equal to \((\sum\limits_{i=1}^q b_i)^2/q=\frac{p^2}{q}\), which is at least \(p^2\cdot \frac{2}{p}\), because \(q<p/2\). Thus, the number of pairs is at least \(\frac{2p-p}{2}\), which is strictly greater than \(\frac{p-1}{2}\), contradiction.

Trivially assume $p$ odd and throw out $a_p.$ We claim that we can find $\frac{p+1}{2}$ distinct values among the other values for some choice of $k$; assume this is false for the sake of contradiction. We assume $0\leq k\leq p-1.$ Let $x_{ik}$ be the number of things in the set $a_j+jk,1\leq j\leq p-1$ that equal $i.$ Trivially $\sum_{i=0}^{p-1}x_{ik}=p-1.$ Now note that $a_i+ik\equiv a_j+jk \mod p$ holds for exactly one value of $k$ for fixed $i,j.$ Thus, double counting pairs, we get $\sum_{k=0}^{p-1}\sum_{i=0}^{p-1}\binom{x_{ik}}{2}=\binom{p-1}{2}.$ By pigeonhole, there exists a $k$ such that $\sum_{i=0}^{p-1}\binom{x_{ik}}{2}\leq \frac{(p-1)(p-2)}{2p}\leq \frac{p-2}{2}.$ Now by assumption, there are at most $a\leq \frac{p-1}{2}$ $x_{ik}$ not equal to $0.$ By Jensen on these terms, we get $\frac{p-2}{2}\geq \sum_{i=0}^{p-1}\binom{x_{ik}}{2}\geq a\binom{p/a}{2}=\frac{p(p/a-1)}{2}\geq \frac{p}{2},$ an evident contradiction.

Congratulations to CantonMathGuy for proposing this problem!

cool 3000th post

Wow congrats bankan! thx for the only easy problem on Day 2!

Edit: This proof doesn't work Choose $k$ randomly from $\{0, 1, 2, \dots, p-1\}$, and let $X$ be the number of distinct remainders when dividing the numbers by $p$. Proving $E[X] \ge \frac{p}{2}$ shows there exists at least one value of $k$ that makes $X \ge \frac p2$. For each $0 \le i \le p-1$, define the indicator variable $X_i$ to be $1$ if $i$ is a remainder, and $0$ otherwise. Since $X = X_0+X_1+X_2+\dots X_{p-1}$, by linearity of expectation we have $E[X] = E[X_0] + E[X_1] + E[X_2] + \dots E[X_{p-1}]$, so it suffices to show $E[X_i] \ge \frac 12$ for any $i$. Then, \begin{align*} E[X_i] &= P(X_i=1) \\ &= 1 - \prod_{j=1}^p P(a_j + jk \not\equiv i \pmod p) \\ &= 1-\left(1-\frac 1p\right)^{p-1} \cdot P(a_p + pk \not\equiv i \pmod p) \\ &\ge 1-\left(1-\frac 1p\right)^{p-1}, \end{align*}because $P(a_j + jk \not\equiv i \pmod p)$ is $1 - \frac 1p$ for $j \neq p$, and $P(a_j + jk \not\equiv i \pmod p) \le 1$ for $j = p$. Now it suffices to prove $\left(1-\frac 1p\right)^{p-1} \le \frac 12$, which we can do with calculus by showing that $f(x) = \left(1-\frac 1x\right)^{x-1}$ is decreasing over $(2, \infty)$.

Plasma_Vortex wrote: Solution sketch: Choose $k$ randomly from $0$ to $p-1$, and let $X$ be the number of remainders. It suffices to show $E[X] \ge p/2$. Define $X_i$ to be 1 if $i$ is a remainder, and 0 otherwise, for $1 \le i \le p-1$. Then $E[X] = \sum E[X_i]$, so it suffices to show $E[X_i] \ge 1/2$. It's easy to get $E[X_i] = P(X_i=1) \ge 1-(1-1/p)^{p-1}$, and then prove $f(x) = (1-1/x)^{x-1} \le 1/2$ for all $x \ge 2$ by calculus. Is exactly what I did, but doesn't that give the wrong bound for $p=5$?

v_Enhance wrote: However, each $\{i,j\}$ appears in exactly one graph $G_k$, so some graph has at most $\frac 1p \binom p2 = \frac{1}{2}(p-1)$ edges (by ``pigeonhole''). This graph at least $\frac{1}{2}(p+1)$ connected components, as desired. that was what I did... but apparently multiple edges can intersect at once (multiple $a_i+ik$ are the same mod $p$) and I forgot to consider that case (even though it's solved quite easily), how many points will I lose?

brainiac1 wrote: Plasma_Vortex wrote: Solution sketch: Choose $k$ randomly from $0$ to $p-1$, and let $X$ be the number of remainders. It suffices to show $E[X] \ge p/2$. Define $X_i$ to be 1 if $i$ is a remainder, and 0 otherwise, for $1 \le i \le p-1$. Then $E[X] = \sum E[X_i]$, so it suffices to show $E[X_i] \ge 1/2$. It's easy to get $E[X_i] = P(X_i=1) \ge 1-(1-1/p)^{p-1}$, and then prove $f(x) = (1-1/x)^{x-1} \le 1/2$ for all $x \ge 2$ by calculus. Is exactly what I did, but doesn't that give the wrong bound for $p=5$? The bound still holds, because $\left(1-\frac{1}{5}\right)^{5-1} \le \frac{1}{2}$

Really enjoyed this problem; here's my full solution, which is similar to others . Thanks CantonMathGuy!!!!

Fun problem. I did pretty much the same thing as lucasxia01--pigeonhole on the number of "intersections," which I defined as a triple (x, y, k) such that 0 < x < y <= p, 0 <= k < p, and a_x + xk = a_y + yk (mod p). Congrats to CantonMathGuy on the successful proposal!

Isn't the min p+3/2?? Would I get marked down if I got that instead of p+1/2?

I think I miswrote the proof for each intersection subtracting at most 1 from the number of distinct remainders. How many points would that cost?

Superwiz wrote: Isn't the min p+3/2?? Would I get marked down if I got that instead of p+1/2? I think $\frac{p + 1}{2}$ is just a weaker bound. Edit: I mean the bound as the following quote says, not as the bound for the whole problem. zephyrcrush78 wrote: Feel like I'd have to clarify that $\tfrac{p+3}{2}$ would be for the following: For $a_1, a_2, \dots, a_{\frac{p-1}{2}}$ such that $\sum a_i = p$, then $\sum \tbinom{a_i}{2} \ge \tfrac{p+3}{2}$.

Superwiz wrote: Isn't the min p+3/2?? Would I get marked down if I got that instead of p+1/2? Pretty sure I got something along those lines also, so you're good

Well, p+1/2 is perfectly fine. Obviously, if $p>2$ we have to show "at least" p/2. FYI if you used expected value and received p/2, then that's (implicitly) fine (otherwise the exp. val. would be (p-1)/2, if none of them were (p+1)/2).

Here is my solution: https://calimath.org/pdf/USAMO2018-4.pdf And I uploaded the solution with motivation to: https://youtu.be/uTYhJVLG924

Let $f(i, j, k)$ be an indicator function such $f(i, j, k)$ is $1$ if $a_i + ik \equiv a_j + jk \pmod{p}$ and otherwise $0$. Then, the number of distinct remainders for a fixed $k$ is at least \[ p - \sum_{1 \le i < j \le p} f(i, j, k) \] Then, note that for fixed $i \ne j$ and $1 \le k \le p$, that $\mathbb{E}\left[(f(i, j, k)\right] = \frac{1}{p}$ since the $k$ with nonzero output is uniquely determined by $i$ and $j$. As such, \begin{align*} \mathbb{E}\left[p - \sum_{1 \le i < j \le p} f(i, j, k)\right] &\ge p - \mathbb{E}\left[\sum_{1 \le i < j \le p} f(i, j, k)\right] \\ &\ge p - \sum_{1 \le i < j \le p} \mathbb{E}\left[f(i, j, k)\right] \\ &= p - \sum_{1 \le i < j \le p} \frac{1}{p} = p - \frac{1}{p} \cdot \frac{p(p-1)}{2} = \frac{p+1}{2} \end{align*}by the probailistic method.

A nice Combo-NT exercise . The problem is vacuous when $p = 2$. Henceforth, we assume $p \ge 3$ and take all integers modulo $p$. For any $1 \le i < j \le k$, we have $$a_i + i \cdot k \equiv a_j + j \cdot k \pmod{p} \Longleftrightarrow a_i - a_j \equiv k(j-i) \pmod{p}.$$Because $1 \le j-i \le p-1$ holds, $j-i$ must be relatively prime to $p$. Thus, if we fix $i$ and $j$, we know $k(i - j)$ cycles through all residue classes modulo $p$ as $k$ ranges from $0$ to $p-1$. This means there exists a unique $s \in \{0, 1, \ldots, p-1\}$ such that $a_i - a_j \equiv s(j-i) \pmod{p}$. Notice there are precisely $1 \cdot \binom{p}{2} = \binom{p}{2}$ ordered triples $(i, j, k)$ such that $a_i + i \cdot k \equiv a_j + j \cdot k \pmod{p}$. Moreover, since there are $p$ possible values of $k$ modulo $p$, the PHP implies that there exists a value of $k$ whose corresponding sequence contains at most $\frac{1}{p} \cdot \binom{p}{2} = \frac{p-1}{2}$ pairs of terms which are equivalent modulo $p$. For this particular $k$, suppose the sequence produces exactly $m$ distinct remainders $r_1, r_2, \ldots, r_m$ modulo $p$ which appear $f(r_q)$ times, respectively. Then clearly $\sum_{q=1}^{m} f(r_q) = p$ and $$\frac{p-1}{2} \ge \sum_{q = 1}^{m} \binom{f(r_q)}{2} = \frac{1}{2} \left(\sum_{q=1}^{m} f(r_q)^2 - \sum_{q=1}^{m} f(r_q) \right)$$$$\ge \frac{1}{2} \left( \frac{1}{m} \cdot \left( \sum_{q=1}^{m} f(r_q) \right)^2 - p \right) = \frac{p^2}{2m} - \frac{p}{2}$$by Cauchy-Schwarz, whence $m \ge \frac{p^2}{2p-1} > \frac{p}{2}$. $\blacksquare$ Remark: I just noticed that finishing with a graph theoretical interpretation is far more natural than utilizing Cauchy-Schwarz, as adding an edge decreases the number of connected components by $0$ or $1$.

Global? It suffices to consider the expected value of distinct residues. Note that any two residues are distinct if and only if, \begin{align*} a_i + ik \equiv a_j + jk \pmod{p}\\ a_i - a_j \equiv k(j - i) \pmod{p} \end{align*}Note that there is exactly one value of $k$ which satisfies this for any pair $(i, j)$. Thus any pair leave the same residue with probability $\frac{1}{p}$. Over all pairs, which there are $\binom{p}{2}$ of, we find that we have an expected $\frac{1}{p} \cdot \binom{p}{2} = \frac{p-1}{2}$ pairs $(i, j)$ such that $a_i + ik \equiv a_j + jk \pmod{p}$. Then by probabilistic pigeonhole there is some $k$ such that we have at most $\frac{p-1}{2}$ such pairs. Thus we have some $k$ such that we have at least $p - \frac{p-1}{2} = \frac{p+1}{2}$ distinct residues.

Note that the problem condition is obviously true for $p=2$. Now, assume $p$ is an odd prime. For the sake of contradiction, assume that there's no such integer $k$. Hence, the numbers of remainder in the sequence $a_1 + k, a_2 + 2k, \dots, a_p + pk$ is always $\le \frac{p-1}{2}$. We denote $a_i+ik=U_i$ for all $i=1,2,...,p$. Observe that $U_i\equiv U_j(mod p)$ for some $1\le i<j\le p$ if and only if $-k\equiv \frac{a_j-a_i}{j-i} (mod p)$. Consider all the numbers $\frac{a_j-a_i}{j-i}$ in modulo $p$ where $1\le i<j\le p$. There are $\binom{p}{2}=\frac{p(p-1)}{2}$ numbers. By pigeonhole principle, we have a number $s$ that only occur $m\le \frac{p-1}{2}$ times. We take $k=-s$. Hence, we get $m$ pairs of numbers $(x,y)$ where $1\le x<y\le p$ for which $(a,b)$ is one of them if and only if $U_a\equiv U_b (mod p)$. Let $X(t)$ be the number of terms in the sequence $a_1 + k, a_2 + 2k, \dots, a_p + pk$ that has remainder $t$ upon division by $p$ (for $t\in\{0,1,2,...,p-1 \}$). Hence, $X(0)+X(1)+...+X(p-1)=p$. By our first assumption, there are at least $\frac{p+1}{2}$ terms in the sequence $X(0),X(1),...,X(p-1)$ which is $0$. Now, we have $b_1,b_2,...,b_n$ where $n\le \frac{p-1}{2}$ such that $X(b_1)+X(b_2)+...+X(b_n)=p$ for which $X(b_i)\ge 1$ for all $i=1,2,...,n$. Now, the number of pairs $(x,y)$ where $1\le x<y \le p$ and $U_x\equiv U_y (mod p)$ is $$\binom{X(b_1)}{2}+\binom{X(b_2)}{2}+...+\binom{X(b_n)}{2}=\frac{X(b_1)^2+X(b_2)^2+...+X(b_n)^2-p}{2}=m\le \frac{p-1}{2}$$This implies $X(b_1)^2+X(b_2)^2+...+X(b_n)^2\le 2p-1$. By $AM\le QM$ inequality, we get $$\frac{X(b_1)+X(b_2)+...+X(b_n)}{n}\le \sqrt{\frac{X(b_1)^2+X(b_2)^2+...+X(b_n)^2}{n}} \implies \frac{p}{n}\le \sqrt{\frac{2p-1}{n}}\implies p^2\le n(2p-1)$$Recalling $n\le \frac{p-1}{2}$, we get $p^2\le n(2p-1)\le \frac{2p^2-3p+1}{2}$. This implies $3p\le 1$ which is a clear contradiction. Hence, there has to be an integer $k$ that satisfies the condition given.

On this one, you make a lemma regarding which of these terms can be equal, and you finish it off with Jensen's

62861 wrote: This problem was proposed by me. There is nothing to prove for $p = 2$, so assume $p = 2q + 1$ is odd. Create a $p \times p$ table of numbers, as follows: \begin{tabular}{cccc} $a_1 + 1 \cdot 1$ & $a_2 + 2 \cdot 1$ & $\cdots$ & $a_p + p \cdot 1$\\ $a_1 + 1 \cdot 2$ & $a_2 + 2 \cdot 2$ & $\cdots$ & $a_p + p \cdot 2$\\ $\vdots$ & $\vdots$ & $\ddots$ & $\vdots$\\ $a_1 + 1 \cdot p$ & $a_2 + 2 \cdot p$ & $\cdots$ & $a_p + p \cdot p$\\ \end{tabular}Interpret all the numbers above modulo $p$. Examine two different columns, say $\{a_i + ik\}_k$ and $\{a_j + jk\}_k$. We claim they agree (modulo $p$) in only one row. Indeed, if $a_i + ik \equiv a_j + jk \pmod{p}$, then $(i - j)k \equiv a_j - a_i \pmod{p}$, so since $p$ is prime and $i \not\equiv j \pmod{p}$, it follows that $k \equiv \tfrac{a_j - a_i}{i - j} \pmod{p}$. Thus, there are $\tbinom{p}{2} = \tfrac{p(p - 1)}{2} = pq$ pairs of equivalent entries in the same row in the table. Since there are only $p$ rows, some row, say $\{a_n + nk\}_n$, must have at most $q$ pairs of equivalent entries. We claim that this $k$ is as desired. Suppose not; and let $e_1, \dots, e_q$ be the multiplicities (possibly zero) of the remainders appearing in $\{a_n + nk\}_n$. Then \begin{align*} e_1 + \dots + e_q & = p = 2q + 1,\\ \binom{e_1}{2} + \dots + \binom{e_q}{2} & \le \frac{p - 1}{2} = q. \end{align*}Thus \begin{align*} e_1(e_1 - 1) + \dots + e_q(e_q - 1) & \le 2q,\\ e_1^2 + \dots + e_q^2 & \le 4q + 1. \end{align*}On the other hand, by Cauchy, \[e_1^2 + \dots + e_q^2 \ge \tfrac{1}{q} (e_1 + \dots + e_q)^2 = \tfrac{1}{q} (2q + 1)^2 = 4q + 4 + \tfrac{1}{q},\]a contradiction. Thus the sequence $\{a_n + nk\}_n$ contains at least $\tfrac{1}{2}p$ residues modulo $p$, as desired. Thank you for good solution

Note that if $a_i+k \equiv a_j+k \mod{p}$ then $a_i \equiv a_j \mod{p}$. So the probability of these two being the same is $\frac{1}{p}$. That means the expected value of the number of pairwise nondistinct remainders upon division by $p$ is $\binom{p}{2}\frac{1}{p}=\frac{p-1}{2}$. That means the EV of the number of distinct remainders is $p-\frac{p-1}{2}=\frac{p+1}{2}$ which means there exists some integer $k$ such that there are at least $\frac{p+1}{2}>\frac{p}{2}$ distinct remainders.

Note that $p = 2$ is trivial, so consider $p$ odd. We consider $k \pmod{p}$ in the argument that follows. Our key insight is to look at when two residues are the same for a fixed $k$. Indeed, $$a_i + ik \equiv a_j + jk \pmod{p} \iff k \equiv - \frac{a_i - a_j}{i-j} \pmod{p}.$$In particular, for any $i\ne j$, there exists a fixed $k$ with $a_i + ik \equiv a_j + jk \pmod{p}$. This motivates us to count $$| \{(i, j, k) : a_i + ik \equiv a_j + jk \pmod{p}\} |,$$which is $\binom p2$. So $\exists k$ so that $$| \{ (i, j) : a_i + ik \equiv a_j + jk \pmod{p} \} | \le \frac{p-1}2.$$Now we focus on this value $k_0$ of $k$. Suppose this value of $k$ gives us $\le \frac p2$ residues in the set $\{a_1 + k, a_2 + 2k, \dots, a_p + pk\}$. Call these residues $r_1, \cdots, r_{\frac{p-1}{2}}$, where it is permitted for a residue to not occur. Let $r_i$ occur $c_i$ times, and note that $\sum_i c_i = p$. Then $$\frac{p-1}{2} \ge| \{ (i, j) : a_i + ik \equiv a_j + jk \pmod{p} \} | $$$$ = \sum_i \binom{c_i}2$$$$\ge \left( \frac{p-1}{2} \right) \left(\frac{ \left( \frac{2p}{p-1} \right) \left( \frac{2p}{p-1} - 1\right)}{2} \right) \text{ (by Jensen) }$$$$ = \frac{p(p+1)}{2(p-1)}$$$$> \frac{p+1}{2},$$contradiction. So this value of $k$ does give us at least $\frac p2$ residues. $\square$

When $p=2$, there is obviously at least $1$ distinct remainder, so assume $p$ odd. Note that for distinct $x,y$, $a_x+xk\equiv a_y+yk \pmod{p}$ happens at $k\equiv \frac{a_x-a_y}{y-x}\pmod{p}$. For every $k$ from $1$ to $p$, let undirected graph $G_k$ have an edge joining $x$ and $y$ iff $k\equiv \frac{a_x-a_y}{y-x}\pmod{p}$. Note that by transitive property, every connected component of $G_k$ must be a clique. Then, we want to prove that it is impossible for every $G_k$ to have less than $\frac{p}{2}$ cliques. Also note that, for every $x$ and $y$, $x$ and $y$ are only connected in $1$ graph $G_k$. Therefore, the sum of edges from every $G_k$ must be $\binom{p}{2}$. If a graph has at most $\frac{p-1}{2}$ cliques, then the minimum number of edges it can have is $\frac{p-3}{2}\binom{2}{2}+\binom{3}{2}=\frac{p+3}{2}$ by Jensen's. Since $p\frac{p+3}{2}>\binom{p}{2}$, we have proven the desired impossibility.

v_Enhance wrote: For each $k = 0, \dots, p-1$ let $G_k$ be the graph on $\{1, \dots, p\}$ where we join $\{i,j\}$ if and only if \[ a_i + ik \equiv a_j + jk \pmod p \iff k \equiv - \frac{a_i - a_j}{i-j} \pmod p. \]So we want a graph $G_k$ with at least $\tfrac{1}{2} p$ connected components. However, each $\{i,j\}$ appears in exactly one graph $G_k$, so some graph has at most $\tfrac 1p \tbinom p2 = \tfrac{1}{2}(p-1)$ edges (by pigeonhole). This graph has at least $\tfrac{1}{2}(p+1)$ connected components, as desired. Remark: Here is an example for $p=5$ showing equality can occur: \[ \begin{bmatrix} 0 & 0 & 3 & 4 & 3 \\ 0 & 1 & 0 & 2 & 2 \\ 0 & 2 & 2 & 0 & 1 \\ 0 & 3 & 4 & 3 & 0 \\ 0 & 4 & 1 & 1 & 4 \end{bmatrix}. \] OG! I guess you meant to write disconnected in place of connected.

It holds for $p=2$ hence we let $p>2$. Consider the complete graph with colours $k_1,k_2,\dots,k_p$ and vertices $a_1,\dots,a_p$ such that each edge is coloured into exactly one of $k_i$. \[\text{Colour the edge between} \ a_i \ \text{and} \ a_j \ \text{into} \ k_m\iff a_i+ik_m\equiv a_j+jk_m(mod \ p)\iff \frac{a_i-a_j}{j-i}\equiv k_m(mod \ p)\]Since there are $\binom{p}{2}$ edges and $p$ colours, there exists a colour with $\leq \frac{p-1}{2}$ edges. Let $k_l$ be that colour. If $a_i$ has $k_l$ coloured edge between itself and $a_j,a_m$, then the edge between $a_j$ and $a_m$ must be coloured into $k_l$. If there are $\geq \frac{p+1}{2}$ components, then $k_l$ satisfies the conditions. Suppose that there are $\leq\frac{p-1}{2}$ components. Denote by $C_1,\dots,C_x$ the components. \[\frac{p-1}{2}\geq \sum_{i=1}^{m}{\binom{|C_i|}{2}}\iff p-1\geq \sum{|C_i|^2}-\sum{|C_i|}=\sum{|C_i|^2}-p\geq \frac{(\sum{|C_i|})^2}{m}-p\geq \frac{2p^2}{p-1}-p\]However this implies $2p^2-3p+1\geq 2p^2$ which is impossible as desired.$\blacksquare$

Assume $p$ odd, as $p=2$ is trivial. Consider the matrix formed by iterating $k = 1, 2, \ldots, p$: \[\begin{matrix} a_1+1 & a_2+2 & \cdots & a_p+p \\ a_1+2 & a_2+4 & \cdots & a_p+2p \\ \vdots & & & \vdots \\ a_1+p & a_2+2p & \cdots & a_p+p^2 \end{matrix}\] Notice that any two columns agree on exactly one residue, which gives a total $\binom p2$ pairs of congruent residues in the same row, and thus there exists a row in which we have at most $\binom p2 \cdot \frac 1p = \frac{p-1}{2}$ pairs. We finish by noting that each pair eliminates at most one new residue, meaning the number of distinct residues in this row must be at least \[p - \frac{p-1}{2} = \frac{p+1}{2} > \frac p2. \quad \blacksquare\]