Let $p$ and $q$ be two given positive integers. A set of $p+q$ real numbers $a_1<a_2<\cdots <a_{p+q}$ is said to be balanced iff $a_1,\ldots,a_p$ were an arithmetic progression with common difference $q$ and $a_p,\ldots,a_{p+q}$ where an arithmetic progression with common difference $p$. Find the maximum possible number of balanced sets, so that any two of them have nonempty intersection. Comment: The intended problem also had "$p$ and $q$ are coprime" in the hypothesis. A typo when the problems where written made it appear like that in the exam (as if it were the only typo in the olympiad). Fortunately, the problem can be solved even if we didn't suppose that and it can be further generalized: we may suppose that a balanced set has $m+n$ reals $a_1<\cdots <a_{m+n-1}$ so that $a_1,\ldots,a_m$ is an arithmetic progression with common difference $p$ and $a_m,\ldots,a_{m+n-1}$ is an arithmetic progression with common difference $q$.
Problem
Source: Romania TST 1 2012, Problem 5
Tags: arithmetic sequence, algebra proposed, algebra
27.06.2012 09:52
First, I talk about the case $p$ and $ q$ are coprime. With each $a_1=a$, we can find all of the terms of the sequence: $a_i = a + (i-1)q$ with $1 \le i \le p$ $a_i = a + (p-1)q + ip$ with $1 \le i \le p$ And we can compare two such term of two specific sequence. I guess the answer is $p+q$. For example: (*) $p=2,q=3$: 1 4 6 8 10 - 3 6 8 10 - - 5 8 10 12 14 - - - 7 10 12 14 16 - - - - 10 13 15 17 19 (*) $p =3,q=2$ 1 3 6 9 12 - 4 6 9 12 15 - - 7 9 12 15 18 - - - 10 12 15 18 21 - - - - 12 14 17 20 23
13.08.2017 00:30
I only give the proof when $p,q$ is co-prime. The answer is $p+\max\{p,q\}$. The case when $p\ge q$ is trivial. As for the case $p<q$, the construction is trivial, too. Define $0=x_1<x_2<\ldots<x_k$ are all minimal elements in each balanced set. It's not hard to prove for any incidences $i<j$, there is unique pair of integers $0\le u\le q,0\le v\le p-1$ such that $x_j-x_i=up+vq$. Specifically, we have $x_i=x_i-x_1=u_i p+v_i q$(where $u_i,v_i$ are defined before). Easy to prove $$0=u_1+v_1<u_2+v_2<\ldots<u_k+v_k$$Since above are all integer,we get $u_k+v_k\ge k-1$. Thus $$2pq-q\ge x_k\ge u_k p+(k-1-u_k)q=(k-1)q-u_k(q-p)\ge (k-1)q-q(q-p)\implies k\le p+q$$
02.12.2017 15:31
smy2012 wrote: The answer is $p+\max\{p,q\}$. The case when $p\ge q$ is trivial.