Let $n$ be a positive square free integer, $S$ is a subset of $[n]:=\{1,2,\ldots ,n\}$ such that $|S|\ge n/2.$ Prove that there exists three elements $a,b,c\in S$ (can be same), satisfy $ab\equiv c\pmod n.$ Created by Zhenhua Qu
Problem
Source: 2024 CTST P4
Tags: number theory, 2024 CTST, China TST
07.03.2024 12:02
Easy one.
07.03.2024 14:16
陈题(???????????)
07.03.2024 14:20
i don't speak chinese so i'll try to write my own solution
07.03.2024 14:29
2023). Given prime number $p$ and positive integer $m,$ $A$ is a subset of $[p^m]$ such that $p^m\nmid ab-c$ holds for all $a,b,c\in A.$ Find the maximum value of $|A|.$
07.03.2024 14:31
the power of a prime is like opposite of squarefree though
07.03.2024 15:06
07.03.2024 17:13
Let $n=p_1\ldots p_r$ and for each vector $\vec{v} \in \{0,1\}^r$ define $S_{\vec{v}}=\{k \in [n] : p_i \mid k \iff v_i=1\}$. Obviously if $n \in S$ then we are done by taking $a=b=c=n$, so suppose otherwise. Then some $\vec{v}\neq (1,\ldots,1)$ has $|S_{\vec{v}} \cap S|>\tfrac{1}{2}|S_{\vec{v}}|$. Let $S_{\vec{v}} \cap S=\{x_1,\ldots,x_t\}$ and note that if no $p,q,r$ exist with $x_px_q \equiv x_r \pmod{n}$ then $\{x_1x_1,x_1x_2,\ldots,x_1x_t\}$ and $\{x_1,\ldots,x_t\}$ (taken modulo $n$) are disjoint, but both are subsets of $S_{\vec{v}}$ and their union has size $2t>|S_{\vec{v}}|$: contradiction.
07.03.2024 18:03
Let $Q$ be the set of units in $\mathbb{Z}_n$. It follows inductively that $\mathbb{Z}_n \setminus Q$ only has at most half the elements required. So WLOG reduce to the multiplicative subgroup of $\mathbb{Z}_n$ be $\mathbb{Z}_{s_1}^{r_1} \times \mathbb{Z}_{s_2}^{r_2} \times \dots \times \mathbb{Z}_{s_k}^{r_k}$. Then $|S + S| \ge |S| \ge \frac{n}{2}$ finishes by Kneser's theorem.
07.03.2024 23:59
If $n$ is even, take either the even or odd numbers, whichever has size at least $\frac n4$, and solve the problem modulo $\frac n2$. If $n$ is odd, there are at least $|S|\geq\frac{n+1}2$ values of the left hand side and $\frac{n+1}2$ values of the right hand side, so at least two of them must be equal.
08.03.2024 00:44
DottedCaculator wrote: If $n$ is odd, there are at least $|S|\geq\frac{n+1}2$ values of the left hand side We can't simply fix $a$ and vary $b$, since not everything generated is unique; is there some other way to prove this easily?
08.03.2024 01:00
YaoAOPS wrote: Let $Q$ be the set of units in $\mathbb{Z}_n$. It follows inductively that $\mathbb{Z}_n \setminus Q$ only has at most half the elements required. So WLOG reduce to the multiplicative subgroup of $\mathbb{Z}_n$ be $\mathbb{Z}_{s_1}^{r_1} \times \mathbb{Z}_{s_2}^{r_2} \times \dots \times \mathbb{Z}_{s_k}^{r_k}$. Then $|S + S| \ge |S| \ge \frac{n}{2}$ which finishes. explain your ring theory magic
03.04.2024 20:33
Thats easy for a china TST p4, first assume $n \not \in S$ , We can safely assume $S$ is not empty. Now i define $S_a=\{k|k \in S ,(k,n)=a\} \forall a \in \mathbb{Z}^+,a \geq 2$ Its easy to observe $S_a$'s are disjoint. Now assume the contrary to the orginal problem We prove Claim: The union of all $S_a$ gives $S$ Assume the contrary this forces there exists an element in $S$ which is coprime to $n$ say its $e$ now say $S'$ is the set formed by multiplying each element in $S$ with $e$ obviously working mod $n$ Observe first the gcds of each term with $n$ stays same and the no of distinct terms does too just use that with the cardinality condition to conclude the two sets must have atleast one common element which contradicts Claim 2: the no of elements in $S_a$ is $ \leq \phi(\frac{n}{a})$ assuming $a|n$ This is easy hence i leave it as an excercise to the reader Claim 3: The exist $a|n$ such that $|S_a| \geq \frac{\phi(\frac{n}{a})}{2}$ Assume the contrary and use the claim 1 and cardinality condition u basically get something like $\frac{n}{2} \geq \frac{n}{2}$ where $p_i$ denotes the prime divisors of $n$ The solution can henceforth be finished by induction on the number of prime divisors of $n$
10.05.2024 21:39
We uploaded our solution https://calimath.org/pdf/ChinaTST2024-4.pdf on youtube https://youtu.be/TZ2QkC8Nsh0.
25.05.2024 05:12
This is really not a difficult problem.
25.06.2024 23:32
Case: $n$ is prime If $p\in S$ then then we can chose $b=c=p$ finishing the problem so assume that $p\notin S$. Then fix $a\in S$ and notice that $ab$ can take on $|S|$ different values for $b\in S$ so by PHP we are done. Now let $n=p_1p_2\dots p_n$ and we induct on $n$. Let $G\subseteq \{1,2,\dots,n\}$ and let $S_G$ consist of all the elements of $x\in S$ for which $p_i|x$ iff $i\in G$. Now assume that no such triplet $a,b,c\in S$ work. Using a similar argument as above, $S_{\emptyset}$ can contain at most $\frac{1}{2}\prod_{i=1}^{n}(p_i-1)$ elements. Using the inductive hypothesis, $S_G$ can contain at most $\frac{1}{2}\prod_{i\notin G}(p_i-1)$ elements and $S_{[n]}$ can not contain any elements. Summing over all subsets $G$ we get that $S$ can not contain more than $\frac{n-1}{2}$ elements, a contradiction.