Difficult combinatorics problem about distinct sums under shifts

Art of Problem Solving

AoPS Online

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

No tags match your search

M

Difficult combinatorics problem about distinct sums under shifts

G H J

Reveal topic tags

Additive combinatorics

L

G H BBookmark kLocked kLocked NReply

Source: Korea

The post below has been deleted. Click to close.

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

87 posts

#1 h Apr 27, 2025, 5:22 AM • 1 Y

Y by kiyoras_2001

Problem. Let $a_1, ..., a_n$ be the nonnegative integers in $\{0, 1, ..., m\}$ where $m=\left\lceil \frac{n^{2/3}}{4} \right\rceil$ . Define $A=\{a_i+a_j+(j-i)|1\leq i<j\leq n\}$ . Prove that $|A|\geq m$ .

Bonus problem (Open). Can we prove a tighter result than the one above? That is, is there a function $f(n)$ such that $f(n)=O(n^\alpha)$ where $\alpha>\frac{2}{3}$ , and the statement is still true when $m=f(n)$ ?
Or, is there a function $f(n)$ such that $f(n)\geq C \cdot n^{2/3}$ where $C>\frac{1}{4}$ , and the statement is still true when $m=f(n)$ ?.

This post has been edited 10 times. Last edited by CBMaster, Apr 27, 2025, 5:43 AM
Reason: .

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a