Easy one.

陈题(???????????)

i don't speak chinese so i'll try to write my own solution

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

the power of a prime is like opposite of squarefree though

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.

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.

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.

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?

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

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$

We uploaded our solution https://calimath.org/pdf/ChinaTST2024-4.pdf on youtube https://youtu.be/TZ2QkC8Nsh0.

This is really not a difficult problem.

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.