MathDB

1998 Brazil National Olympiad

Part of Brazil National Olympiad

Subcontests

(3)
1
2
3
2

Yet another two-player game! - the maximum gcd-sum

Two players play a game as follows: there n>1n > 1 rounds and d≥1d \geq 1 is fixed. In the first round A picks a positive integer m1m_1, then B picks a positive integer n1≠m1n_1 \not = m_1. In round kk (for k=2,…,nk = 2, \ldots , n), A picks an integer mkm_k such that mk−1<mk≤mk−1+dm_{k-1} < m_k \leq m_{k-1} + d. Then B picks an integer nkn_k such that nk−1<nk≤nk−1+dn_{k-1} < n_k \leq n_{k-1} + d. A gets gcd⁡(mk,nk−1)\gcd(m_k,n_{k-1}) points and B gets gcd⁡(mk,nk)\gcd(m_k,n_k) points. After nn rounds, A wins if he has at least as many points as B, otherwise he loses. For each (n,d)(n, d) which player has a winning strategy?

Lost in berlin - a very beautiful problem :p

Two mathematicians, lost in Berlin, arrived on the corner of Barbarossa street with Martin Luther street and need to arrive on the corner of Meininger street with Martin Luther street. Unfortunately they don't know which direction to go along Martin Luther Street to reach Meininger Street nor how far it is, so they must go fowards and backwards along Martin Luther street until they arrive on the desired corner. What is the smallest value for a positive integer kk so that they can be sure that if there are NN blocks between Barbarossa street and Meininger street then they can arrive at their destination by walking no more than kNkN blocks (no matter what NN turns out to be)?
2
2