Daily

Random

Practice set

Baltic Way 1996 · Problem 9

Number Theory

Let nn and kk be integers, 1<k≤n1<k \leq n. Find an integer bb and a set AA of nn integers satisfying the following conditions:

(i) No product of k−1k-1 distinct elements of AA is divisible by bb.

(ii) Every product of kk distinct elements of AA is divisible by bb.

(iii) For all distinct a,a′a, a^{\prime} in AA, aa does not divide a′a^{\prime}.

Change pool

When you’re ready

Review material becomes available with the next Daily.

Review

Topics

Primes · Divisibility and factorization

Solutions

Solution

Solution: Let p1,…,pnp_1, \ldots, p_n be the first nn odd primes. Then we can take A={2p1,2p2,…,2pn}A = \{2 p_1, 2 p_2, \ldots, 2 p_n\} and b=2kb = 2^k. It is easily seen that the conditions are satisfied.

Contest context

Results from Baltic Way 1996

10 teams

Mean score
4.0 / 5
Scores of 4 or 5
8 / 10
Estonia
5 / 5

Score distribution

02
10
20
30
40
58
All team scores
TeamScore
Poland5 / 5
Latvia5 / 5
Sweden5 / 5
Denmark5 / 5
St. Petersburg5 / 5
Finland5 / 5
Norway5 / 5
Lithuania0 / 5
Estonia5 / 5
Iceland0 / 5