Sad Combinatorics

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

3564 posts

#1 h Apr 19, 2018, 11:00 PM • 63 Y

Y by lucasxia01, fishy15, wu2481632, lifeisgood03, aftermaths, trumpeter, ccx09, AOPS12142015, AforApple, kingofgeedorah, Generic_Username, Math-Ninja, hwl0304, checkmatetang, thepiercingarrow, acegikmoqsuwy2000, Mudkipswims42, Vfire, Ankoganit, rocketscience, PiDude314, rkm0959, rafayaashary1, Davi-8191, Ultroid999OCPN, adihaya, reaganchoi, mathmaster2000, Happy2020, Unlimited, GeneralCobra19, yugrey, Mathuzb, naw.ngs, TheCosineLaw, Vietjung, Wizard_32, Williamgolly, Aryan-23, Lol_man000, Abidabi, suvamkonar, rachelshi, HamstPan38825, icematrix2, megarnie, jhu08, spicemax, centslordm, pog, rama1728, HWenslawski, CyclicISLscelesTrapezoid, rayfish, mathmax12, jmiao, aidensharp, Adventure10, Mango247, Sedro, Tastymooncake2, zhaooao, Lcz

Let $p$ be a prime, and let $a_1, \dots, a_p$ be integers. Show that there exists an integer $k$ such that the numbers
$a_1 + k, a_2 + 2k, \dots, a_p + pk$ produce at least $\tfrac{1}{2} p$ distinct remainders upon division by $p$ .

Proposed by Ankan Bhattacharya

This post has been edited 5 times. Last edited by 62861, Apr 17, 2019, 11:47 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

brainiac1

1945 posts

brainiac1

#2 h Apr 19, 2018, 11:00 PM • 5 Y

Y by icematrix2, jhu08, megarnie, Adventure10, Mango247

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

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

v_Enhance

6868 posts

v_Enhance

#3 h Apr 19, 2018, 11:00 PM • 58 Y

Y by 62861, lifeisgood03, expiLnCalc, Ankoganit, rkm0959, Ultroid999OCPN, Number1, yugrey, samoha, rzlng, Sskkrr, MathbugAOPS, AIME12345, zsgvivo, btcaf, Wizard_32, Toinfinity, AlastorMoody, Polynom_Efendi, Chryss, Aryan-23, Frestho, myh2910, mathlogician, Spakian, Lol_man000, Atpar, Avlon, menpo, Abidabi, hamburgerwhizz, mijail, v4913, Pitagar, TETris5, HamstPan38825, centslordm, suvamkonar, math31415926535, icematrix2, jhu08, megarnie, kante314, rayfish, jrsbr, mathmax12, jmiao, sabkx, ike.chen, Adventure10, aidan0626, Mango247, Sagnik123Biswas, Upwgs_2008, Assassino9931, Tastymooncake2, zhaooao, MS_asdfgzxcvb

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 post has been edited 3 times. Last edited by v_Enhance, Feb 27, 2023, 7:42 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

62861

3564 posts

62861

#4 h Apr 19, 2018, 11:01 PM • 89 Y

Y by v_Enhance, Th3Numb3rThr33, lucasxia01, wu2481632, trumpeter, Vfire, whatshisbucket, lifeisgood03, AOPS12142015, jam10307, samuel, Generic_Username, jonlin1000, DrMath, hwl0304, claserken, ghghghghghghghgh, acegikmoqsuwy2000, Mudkipswims42, Ankoganit, sriraamster, Math-Ninja, Abdollahpour, mira74, adihaya, Superguy, zazazazazazazaza, lzh20010227, Happy2020, 277546, rkm0959, Unlimited, Ultroid999OCPN, Mathnerd1223334444, ishankhare, AforApple, samoha, Mathuzb, MNJ2357, Sskkrr, MathbugAOPS, JasperL, talkon, expiLnCalc, Vietjung, btcaf, Wizard_32, khina, Pluto1708, Toinfinity, AlastorMoody, Polynom_Efendi, rashah76, Aryan-23, myh2910, mathlogician, Lol_man000, tree_3, Avlon, ProblemSolver2048, mijail, fidgetboss_4000, Wizard0001, hamburgerwhizz, tigerzhang, icematrix2, math31415926535, centslordm, jhu08, pog, megarnie, rayfish, CyclicISLscelesTrapezoid, Quidditch, mathmax12, jmiao, sabkx, miguel00, aidensharp, Adventure10, aidan0626, rg_ryse, Mango247, Sagnik123Biswas, bjump, giratina3, MathRook7817, Tastymooncake2, MS_asdfgzxcvb

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.

This post has been edited 1 time. Last edited by 62861, May 10, 2018, 5:43 AM
Reason: typo

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

hwl0304

1840 posts

hwl0304

#5 h Apr 19, 2018, 11:01 PM • 7 Y

Y by Mathnerd1223334444, Diorite, rashah76, icematrix2, jhu08, Adventure10, Mango247

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

aftermaths

80 posts

aftermaths

#6 h Apr 19, 2018, 11:02 PM • 5 Y

Y by kidcrumb10, icematrix2, jhu08, Adventure10, Mango247

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.

This post has been edited 1 time. Last edited by aftermaths, Apr 20, 2018, 12:05 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

wu2481632

4233 posts

wu2481632

#7 h Apr 19, 2018, 11:02 PM • 47 Y

Y by hwl0304, lucasxia01, 62861, checkmatetang, mathwizard888, Superwiz, Th3Numb3rThr33, qbzvavba, EulerMacaroni, fishy15, tapir1729, hotstuffFTW, Vfire, aftermaths, mathisawesome2169, kingofgeedorah, samuel, Plasma_Vortex, thedoge, summitwei, Mudkipswims42, Math-Ninja, flyingpurplepeopleeater, PiDude314, rkm0959, flyrain, ishankhare, Happy2020, ShineBunny, GeneralCobra19, katzrockso, Pluto1708, Toinfinity, myh2910, whiteguard, Abidabi, hamburgerwhizz, HamstPan38825, icematrix2, megarnie, jhu08, OlympusHero, aidan0626, jmiao, sabkx, Adventure10, Sedro

Congratulations to CantonMathGuy for proposing this problem!

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

fishy15

2219 posts

fishy15

#8 h Apr 19, 2018, 11:05 PM • 5 Y

Y by icematrix2, jhu08, megarnie, Adventure10, Mango247

cool 3000th post

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

pandadude

710 posts

pandadude

#9 h Apr 19, 2018, 11:09 PM • 7 Y

Y by KenV, AlastorMoody, icematrix2, jhu08, megarnie, Adventure10, Mango247

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

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Plasma_Vortex

268 posts

Plasma_Vortex

#10 h Apr 19, 2018, 11:10 PM • 4 Y

Y by icematrix2, jhu08, Adventure10, Mango247

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)$ .

This post has been edited 8 times. Last edited by Plasma_Vortex, Apr 21, 2018, 11:46 PM
Reason: :'(

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

brainiac1

1945 posts

brainiac1

#11 h Apr 19, 2018, 11:11 PM • 4 Y

Y by icematrix2, jhu08, Adventure10, Mango247

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$ ?

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

mathisawesome2169

1823 posts

mathisawesome2169

#17 h Apr 19, 2018, 11:16 PM • 4 Y

Y by icematrix2, jhu08, Adventure10, Mango247

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?

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Plasma_Vortex

268 posts

Plasma_Vortex

#18 h Apr 19, 2018, 11:18 PM • 4 Y

Y by icematrix2, jhu08, Adventure10, Mango247

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}$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

lucasxia01

908 posts

lucasxia01

#19 h Apr 19, 2018, 11:22 PM • 11 Y

Y by 62861, AOPS12142015, Mudkipswims42, Math-Ninja, enhanced, MathbugAOPS, icematrix2, megarnie, jhu08, Adventure10, Mango247

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

. Thanks CantonMathGuy!!!!
Solution

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

iNomOnCountdown

1030 posts

iNomOnCountdown

#20 h Apr 19, 2018, 11:24 PM • 7 Y

Y by yrnsmurf, 62861, icematrix2, megarnie, jhu08, Adventure10, Mango247

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!

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

YaoAOPS

1497 posts

YaoAOPS

#105 h Jun 15, 2023, 12:04 AM

Y by

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

ike.chen

1162 posts

ike.chen

#106 h Jul 15, 2023, 2:01 AM

Y by

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$ .

This post has been edited 6 times. Last edited by ike.chen, Dec 31, 2024, 1:45 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

AtharvNaphade

341 posts

AtharvNaphade

#108 h Aug 6, 2023, 11:09 PM

Y by

outline

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

pinkpig

3761 posts

pinkpig

#109 h Nov 29, 2023, 11:17 PM

Y by

sol

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Shreyasharma

666 posts

Shreyasharma

#110 h Dec 13, 2023, 4:26 AM

Y by

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

amazingtheorem

17 posts

amazingtheorem

#111 h Jan 20, 2024, 4:22 PM • 1 Y

Y by ATGY

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Mr.Sharkman

490 posts

Mr.Sharkman

#112 h Apr 11, 2024, 2:04 AM

Y by

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

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Math_.only.

22 posts

Math_.only.

#113 h Jul 18, 2024, 7:20 AM

Y by

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

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

de-Kirschbaum

184 posts

de-Kirschbaum

#114 h Jul 24, 2024, 5:58 PM

Y by

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

AshAuktober

934 posts

AshAuktober

#115 h Aug 31, 2024, 10:01 AM

Y by

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$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

RedFireTruck

4220 posts

RedFireTruck

#116 h Sep 19, 2024, 1:21 AM

Y by

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

sansgankrsngupta

127 posts

sansgankrsngupta

#117 h Oct 26, 2024, 6:48 PM

Y by

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

bin_sherlo

665 posts

bin_sherlo

#119 h Dec 8, 2024, 2:59 PM

Y by

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$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

shendrew7

792 posts

shendrew7

#120 h Dec 31, 2024, 12:33 AM

Y by

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$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Zany9998

6 posts

Zany9998

#121 h Friday at 1:30 PM

Y by

Note that if $p=2$ the claim is trivially true, so let's assume $p \geq 3$
Let $N(G)$ denote the number of edges in a simple graph $G$ .

Consider $p$ different simple graphs $G_0,G_2 , \dots G_{p-1}$ . Each of these graphs have $p$ nodes labelled from $1$ to $p$ . Graph $G_k$ has an edge between $i$ and $j$ iff

$a_i + ik \equiv a_j + jk \mod p$ .

note that edge between node $i$ and node $j$ is only present in graph $G_k$ where $k \equiv (a_i - a_j)(j-i)^{-1} \mod p$ .Hence all of the edges of each graph are disjoint and every possible edge is present in at least one graph.

this implies
$\sum_{i=0}^{i=p-1} N(G_i) = p(p-1)/2$ hence by pigeonhole there exists a graph $G_k$ such that $N(G_k) \leq (p-1)/2$ . As number of connected components is at least (nodes - edges) therefore we get number of connected components at least $(p+1)/2$ which proves our original claim

Z K Y