Bariz - Problem

SAUDITYA

01.04.2017 18:09

Nice Problem(I don't know if my solution's correct) Solution:

For $n = 2k+1$, Boris has a winning strategy! Strategy: See that Boris plays the first as well as the last move.So it's possible for Boris to color the $k+1$ points white such that no two black point are adjacent to one another.Also see that as there are $k+1$ white points , so there exists exactly two adjacent points which are white. Proof: Let the two adjacent white points be $A_{2k+1}$ and $A_{1}$.Let us arrange the rest of the $2k-1$ points $A_2 , A_3 ,\cdots ,A_{2k}$ in clockwise manner such that $A_{i-1}$ and $A_{i+1}$ are adjacent to $A_{i}$ , $\forall i \in (1,2,\cdots,2k+1)$. Now, according to our strategy $(A_{1},A_{3} , \cdots ,A_{2k-1},A_{2k+1})$ are white and ($A_2,A_4,\cdots,A_{2k}$) are black. Claim : In $\widehat {A_{2i-1}A_{2i+1}}$ , the length of the black arc and the white arc are the same , $\forall i =(1,2,\cdots,k)$ Proof : Let $X$ and $Y$ be the midpoint of $\widehat {A_{2i-1}A_{2i}}$ and $\widehat{A_{2i}A_{2i+1}}$.See that all points in $\widehat {XY}$ are black while the rest is white.Also $\widehat {XY} = \frac{\widehat {A_{2i-1}A_{2i+1}}}{2}$.So the claim is true! See that this shows that the length of white and black arc in $\widehat {A_{1}A_{2k+1}}$ is same!.As all the points between $\widehat{A_{2k+1}A_1}$ are white. So Boris wins! For $n=2k$, Eugene can prevent Boris from winning! Strategy: For every turn that Boris colors a point white ,Eugene must color the diametrically opposite point with black! Proof: Let us arrange the points $A_1 , A_3 ,\cdots ,A_{2k}$ in clockwise manner such that $A_{i-1}$ and $A_{i+1}$ are adjacent to $A_{i}$ , $\forall i \in (1,2,\cdots,2k)$. According to our strategy $A_iA_{i+k}$ is a diameter whose endpoints are of different colors,also $\widehat{A_iA_{i+1}} = \widehat{A_{i+k}A_{i+k+1}}$,$\forall i \in (1,2,\cdots ,k)$ So if the length of black arc and white arc is $x$ and $y$ in $\widehat{A_iA_{i+1}}$, then the length of black arc and white arc is $y$ and $x$ in $\widehat{A_{i+k}A_{i+k+1}}$ From here we conclude that the total length of black and white arc's are equal! [Note : the indices are taken modulo n and $\widehat{XY}$ denotes the clockwise arc from $X$ to $Y$]

test20

01.04.2017 19:24

proximo wrote: When they both mark $n$ points ... What does this mean? 1. As soon as each of them has colored $n$ points, ... 2. As soon as $n$ points have been colored, ...

proximo

01.04.2017 20:31

It means "As soon as each of them has colored $n$ points". Thanks for noticing this. Sorry if I confused somebody

Buikimanh

01.07.2017 11:14

SAUDITYA wrote: Nice Problem(I don't know if my solution's correct) Solution:

For $n = 2k+1$, Boris has a winning strategy! Strategy: See that Boris plays the first as well as the last move.So it's possible for Boris to color the $k+1$ points white such that no two black point are adjacent to one another.Also see that as there are $k+1$ white points , so there exists exactly two adjacent points which are white. Proof: Let the two adjacent white points be $A_{2k+1}$ and $A_{1}$.Let us arrange the rest of the $2k-1$ points $A_2 , A_3 ,\cdots ,A_{2k}$ in clockwise manner such that $A_{i-1}$ and $A_{i+1}$ are adjacent to $A_{i}$ , $\forall i \in (1,2,\cdots,2k+1)$. Now, according to our strategy $(A_{1},A_{3} , \cdots ,A_{2k-1},A_{2k+1})$ are white and ($A_2,A_4,\cdots,A_{2k}$) are black. Claim : In $\widehat {A_{2i-1}A_{2i+1}}$ , the length of the black arc and the white arc are the same , $\forall i =(1,2,\cdots,k)$ Proof : Let $X$ and $Y$ be the midpoint of $\widehat {A_{2i-1}A_{2i}}$ and $\widehat{A_{2i}A_{2i+1}}$.See that all points in $\widehat {XY}$ are black while the rest is white.Also $\widehat {XY} = \frac{\widehat {A_{2i-1}A_{2i+1}}}{2}$.So the claim is true! See that this shows that the length of white and black arc in $\widehat {A_{1}A_{2k+1}}$ is same!.As all the points between $\widehat{A_{2k+1}A_1}$ are white. So Boris wins! For $n=2k$, Eugene can prevent Boris from winning! Strategy: For every turn that Boris colors a point white ,Eugene must color the diametrically opposite point with black! Proof: Let us arrange the points $A_1 , A_3 ,\cdots ,A_{2k}$ in clockwise manner such that $A_{i-1}$ and $A_{i+1}$ are adjacent to $A_{i}$ , $\forall i \in (1,2,\cdots,2k)$. According to our strategy $A_iA_{i+k}$ is a diameter whose endpoints are of different colors,also $\widehat{A_iA_{i+1}} = \widehat{A_{i+k}A_{i+k+1}}$,$\forall i \in (1,2,\cdots ,k)$ So if the length of black arc and white arc is $x$ and $y$ in $\widehat{A_iA_{i+1}}$, then the length of black arc and white arc is $y$ and $x$ in $\widehat{A_{i+k}A_{i+k+1}}$ From here we conclude that the total length of black and white arc's are equal! [Note : the indices are taken modulo n and $\widehat{XY}$ denotes the clockwise arc from $X$ to $Y$]

for n=2k, we still don't know if Eugene can win

Grim-the-Ripper

10.10.2018 17:14

This is an interesting problem! There is a pitfall in this problem. To understand this potential pitfall, consider the case when $ n =2 $. Define the distance between two points as the length of the shorter circular arc between the two points. One can modify the "diametrically-opposite" strategy outlined in #2 to get a winning strategy for Eugene: 1. Eugene marks his first point to be diametrically opposite Boris' point. 2. Suppose the distance between Boris' first and second point is $ d $. Eugene marks his second point to be any point that is distance $d' > d $ from his first point. This way, Eugene has a larger sum of arc length. Herein lies the trap: for larger $ n $, the strategy above (of picking diameters) does not generalize easily - in fact slight modifications only give us the possibility of a draw. The main idea is to realize that the initial step of the diameter functions effectively as an degenerate regular 2-gon, and the general strategy is to consider picking points to form a regular $n$-gons in the initial step. We exhibit the strategy as follows. Stage 1: After Boris marks his first point $v$, Eugene constructs a regular $n$-gon that contains $v$. Call these points good. Eugene's strategy for this step is to try to pick good points, unless all $ n $ good points have already been picked by either Eugene or Boris in which case he moves to Stage 2. Let us note that since there are only $ n - 1 $ good points remaining (besides $ v $), Eugene's last move will necessarily be in Stage 2. Stage 2: We do the intuitive step of letting Eugene "breaking up" contiguous white points. In more concrete terms, Eugene will place his points, that is not the last, between 2 adjacent good white points (with no other points between them on either of the arcs) if possible. If there are no such white points, Eugene places his point between two contiguous (non-good) white points and if such points do not exist then he can pick his point arbitrarily. Let us note that Eugene will be able to break all the contiguous good white point before his last move: if Eugene marked $ m $ good black points in Stage 1, then Boris would have marked $ n - m $ good white points in Stage 1, so there will be at most $ n - m - 1 $ pairs of contiguous good white points, and so in total Eugene would have made less than $ n - m - 1 + m = n - 1 $ moves. Now, the crucial last move for Eugene to win the game mimics the second step of the strategy for the $ n = 2 $ case. Since there must exist 2 good points (call this pair great) between which no other points have been placed (why?), Eugene does the following: 1. If one of the points in the great pair is white, Eugene places his point such that its distance $ \epsilon $ to the white point is arbitrarily small. 2. If no such great pair exists, Eugene places his point between two consecutive (non-good) white points if possible; if such white points do not exist, he arbitrarily selects a point. I'm pressed for time and will write up why this strategy works when I have more time.

noboru

09.12.2018 17:27

Hello, proximo. Where can i find other years belarusian math olympiad problems"? Is there website?