Magicman and his helper want to do some magic trick. They have special card desk. Back of all cards is common color and face is one of $2017$ colors. Magic trick: magicman go away from scene. Then viewers should put on the table $n>1$ cards in the row face up. Helper looks at these cards, then he turn all cards face down, except one, without changing order in row. Then magicman returns on the scene, looks at cards, then show on the one card, that lays face down and names it face color. What is minimal $n$ such that magicman and his helper can has strategy to make magic trick successfully?
Problem
Source: All Russian Olympiad 2017,Day1,grade 11,P4
Tags: combinatorics
rafayaashary1
02.05.2017 01:13
What is meant by the one locked card?
RagvaloD
02.05.2017 01:17
I edited problem.
MellowMelon
02.05.2017 06:42
I interpret the last part of the problem to mean that the magician only has to determine the color of one face-down card of his choice.
Generalize to $c > 1$ colors numbered 1 to $c$. If $c \geq 4$, the answer is $c+1$, obtained by a trivial strategy where the assistant shows the card in position $i+1$ if card 1 has color $i$, $1 \leq i \leq c$ and the magician always guesses card 1. (The answer is also $c+1$ for $c = 3$, but it requires some steps different from the proof below.)
Let $S = \{(x,y) \mid 1 \leq x \leq n, 1 \leq y \leq c\}$, where $x$ is a position and $y$ is a color. For an arrangement of cards by the viewers, call an ordered pair $(x,y)$ in $S$ valid if the card in position $x$ has color $y$. A strategy is a function $f : S \to S$ so that $a,f(a)$ have different positions for all $a \in S$, and for any card arrangement, there is at least one $a \in S$ such that $a,f(a)$ are both valid.
Assume for the sake of contradiction that a strategy $f$ exists when $n < c+1$.
Claim 1: $n = c$, and for each card arrangement, there is exactly one $a \in S$ where $a,f(a)$ are both valid.
Proof: $S$ has $cn$ elements, and there are $c^n$ card arrangements. For each $a \in S$, the number of card arrangements for which $a,f(a)$ are both valid is $c^{n-2}$. Therefore, we have at most $nc^{n-1}$ card arrangements covered by our strategy $f$. This must be at least $c^n$, so $n \geq c$. Since $n < c+1$, we have $n = c$ and the previous bound is tight, which implies the second part of the claim.
Claim 2: For any $a,b$ with different positions, some two of $a,f(a),b,f(b)$ have the same position.
Proof: If not, all four of $a,f(a),b,f(b)$ could be simultaneously valid in one arrangement, violating claim 1.
Claim 3: There exists a position $x$ such that for any color $y$ and position $z \neq x$, $f(z,y)$ has position $x$.
Proof: Let
\[ T = \{\{x,z\} \mid f(x,y) = (z,w), \ (x,y) \in S\}. \]That is, $T$ is the set of all unordered pairs of positions such that $f$ can go from one to the other. Claim 2 translates to any two pairs in $T$ having a common element. Since the union of all pairs in $T$ has $c$ elements and $c > 3$, there is some position $x$ in all elements of $T$. This is exactly what we wanted.
Claim 4: For any $a \in S$, $a$ and $f(f(a))$ have the same position but different colors.
Proof: If not, all three of $a,f(a),f(f(a))$ could be simultaneously valid in one arrangement, violating claim 1.
Claim 5: $n < c+1$ is impossible.
Proof: Take the $x$ in claim 3, and let $z$ be any of the other $n-1$ positions. Set $a = (z,1)$, and consider \[f(a),f(f(a)),f(f(f(a))),f(f(f(f(a)))).\]By claims 3 and 4, we know that these are all distinct and that they have positions $x,z,x,z$ respectively. In particular, $f(a), f(f(f(a)))$ are two distinct position $x$ pairs in $S$ which map to position $z$ under $f$. There are $n-1$ choices for $z$, so this implies there are at least $2n-2$ position $x$ pairs in $S$. But there are actually only $n$ position $x$ pairs in $S$, so this is a contradiction, and the claim has been proved.
CommentsDespite the length and amount of notation, the solution is straightforward to find once you have claim 1. Relentlessly hunting for card arrangements that allow two potential correct guesses will quickly pile up constraints on $f$. I suspect there are many possible contradictions that can be found.
math90
02.05.2017 06:43
Are both sides of each card from the list of $2017$ colors?
MellowMelon
02.05.2017 06:55
The answer is still $c+1$, and everything in my last post holds except the strategy. Let the back of the cards have color $c$, so that if the assistant turns over a card with color $c$ the magician has no idea what card was turned over.
- If card 1 has color $i$ and card $i+1$ does not have color $c$, the assistant leaves card $i+1$ face up and the magician guesses card 1 has color $i$.
- If card 1 has color $i$ and card $i+1$ has color $c$, the assistant turns over card 1 and the magician guesses card $i+1$ has color $c$. (This includes the case where the magician is faced with a row of cards all showing color $c$; he correctly assumes that card 1 was left face up.)
RagvaloD
02.05.2017 14:03
Face of card is from list of $2017$ colors, and back of every card is common color not from list.
IAmTheHazard
12.07.2023 16:00
One of the most surprising solutions I have ever found. Amazing problem. The answer is $n=2018$, which works due to the following strategy: number the colors $1$ through $2017$. When the helper receives his cards, he adds one to the number on the first (leftmost) card and then keeps the card whose position equals that number. The magicman then sees the position of the card unturned and can exactly deduce the color of the first card. I will now show that $n=2017$ is impossible. This finishes, since if the magicman and helper can find a strategy for some $n<2017$, they can adapt this strategy to $n=2017$ by simply ignoring the last few cards. Magicman and his helper's strategy can be described as a directed graph $G$ on vertices each representing a pair $(i,j)$, where $1 \leq i,j \leq 2017$, where we have $(a,b) \to (c,d)$ if, upon entering and seeing the $a$-th card face up showing color $b$, magicman will name the $c$-th card's color as $d$ (therefore we need $a \neq c$ for there to exist edges). Obviously, the outdegree of each vertex is at most $1$. Furthermore, if we have two edges $(a,b) \to (c,d)$ and $(c,d) \to (a,b)$, we may clearly arbitrarily delete one, since if the helper is presented with some cards and is able to keep the $a$-th card with color $b$ face up to win, they may also always keep the $c$-th card with color $d$ to win. The key idea is to now consider a randomly, independently, and uniformly distributed coloring of the $2017$ cards, where each receives each of the $2017$ colors equally often. We consider the expected value of the number of edges of $G$ such a coloring "covers", where a coloring covers an edge $(a,b) \to (c,d)$ iff the $a$-th card is colored $b$ and the $c$-th card is colored $d$ (the natural interpretation of covering is that if a coloring covers an edge, this gives the helper a way to win). By linearity of expectation, this expected value is $$\sum_{(a,b) \to (c,d)} \frac{1}{2017^2}=\sum_{(a,b) \text{ has outedge}} \frac{1}{2017^2}\leq \frac{2017\cdot 2017}{2017^2}=1,$$with equality holding only when every vertex $(a,b)$ has an outwards edge. On the other hand, this expected value must be at least one, else we can find some coloring which covers no edges, leaving the helper with no valid ways to win. Therefore, the expected value is exactly one. If we can find two edges $(a,b) \to (c,d)$ and $(e,f) \to (g,h)$ such that $a,c,e,g$ are pairwise distinct, we can construct a coloring (where the $a$-th card is color $b$, etc.) where there are at least two valid ways for the helper to win. Similarly, if we find three vertices $(a,b)$, $(c,d)$, and $(e,f)$ forming a "cherry" where an edge exists between $(a,b)$ and both $(c,d)$ and $(e,f)$, with $a,c,e$ pairwise distinct, then there are at least two valid ways for the helper to win in an appropriately constructed coloring. However, the existence of either situation implies that there must also be some coloring where there are no valid ways to win, so if the magicman and his helper can win we cannot have either of these. Therefore, construct a directed graph $G'$ on vertices numbered $1$ through $2017$ such that $a \to b$ iff there exist $i,j$ where $(a,i) \to (b,j)$ is an edge in $G$. Since every vertex in $G$ has outdegree $1$, every vertex in $G'$ has outdegree at least $1$. If $G'$ has two disjoint edges (edges that don't share a vertex), then this corresponds to two edges with $a,c,e,g$ distinct in the notation above, so suppose henceforth that any two of $G'$ share a vertex. By induction, it is easy to show that the only directed graphs on $2017$ vertices where every vertex has outdegree at least $1$ and every pair of edges share a vertex are variants on "star graphs", i.e. there exists some vertex $v$ which is contained in every edge (for $3$ vertices there is also a triangle, but this doesn't generalize to $n=4$), so $G'$ must be of this form. For every $w \neq v$, we must have a single edge from $w$ to $v$ in $G'$ (and no other edges from $w$). Therefore, construct a nonempty set $S_w$ where $i \in S_w$ iff there exists an edge $(w,j) \to (v,i)$ in $G$ for some $j$. These $S_w$ must all be disjoint, otherwise we can find a "cherry" as described before. On the other hand, by construction, we must have some edge $v \to u$ in $G'$, and for these $u$, we must have $|S_u|>1$: if $S_u=\{i\}$, then in $G$ the outedge of $(v,i)$ cannot go to $(u,j)$ for any $j$, else we get two oppositely directed edges between the same two vertices, which we should've already deleted. On the other hand, we also cannot have $(v,i) \to (w,j)$ for any $w \neq u,v$, since there also exists $(u,k) \to (v,i)$, so we find a cherry. On the other hand, since the union of all the $S_w$ is a subset of $\{1,\ldots,2017\}$, there must exist exactly one such $u$ for size reasons. Then pick some $w \neq u,v$ and find an edge $(w,i) \to (v,j)$ in $G$. By the uniqueness of $u$, we must also have $(v,j) \to (u,k)$ in $G$ for some $k$, but this is also a cherry. Therefore, we can always either find a cherry or two disjoint edges in $G$, hence the magicman and his helper will not be able to perform the trick for some appropriately selected coloring if $n=2017$. $\blacksquare$ Remark: Try stupid stuff first! I'm not sure what the motivation to consider linearity of expectation (which is the key step in the problem, since after that you just keep on squeezing out constraints) is, aside from the fact that everything else you try doesn't work and it seems like computing linearity of expectation is pretty straightforward. Maybe if you're good enough you can intuitively notice that you can get something, since the consideration of the graph is natural and this has $2017^2$ edges, which is a number that pops up elsewhere (maybe there is some reverse-engineering to be done here: if you have $2017\cdot 2018$ edges, this seems much less special, so you want to find something that uses $2017^2$ specifically), specifically in the probability that an edge gets covered randomly—maybe this was actually my thought process during the problem; I don't remember since I did it right before falling asleep.