Clearly the detective can win with $50$ questions: Fix a card $c_1$, and ask if $\{c_1, c_i \}$ are consecutive for all $2 \leq i \leq 51$. If for some pairs the answer is true, then declare that; otherwise declare $\{c_1, c_{52} \}$ to be consecutive. To see that this is the best bound possible, draw a graph with $52$ vertices, and for each question that she asks (and her last guess) about $\{c_i, c_j \}$, draw an edge between $v_i$ and $v_j$. In order to force her into losing, all we need is a hamiltonian path in this graph's complement. But this follows from Ore's theorem.

Kayak wrote: Clearly the detective can win with $50$ questions: Fix a card $c_1$, and ask if $\{c_1, c_i \}$ are consecutive for all $2 \leq i \leq 51$. If for some pairs the answer is true, then declare that; otherwise declare $\{c_1, c_{52} \}$ to be consecutive. To see that this is the best bound possible, draw a graph with $52$ vertices, and for each question that she asks about $\{c_i, c_j \}$, draw an edge between $v_i$ and $v_j$. In order to force her into losing, all we need is a hamiltonian path in this graph's complement. But this follows from Ore's theorem. Right... I knew my “induction” write-up in the last 10 minutes was probably nonsense And, as it turns out, it certainly was!

@above why is the rest solution needed if we write the strategy of detective

Navansh wrote: @above why is the rest solution needed if we write the strategy of detective The question asks "if and only if" ... Not just "if". So u need to prove both ways

Hmm I wrote some partial stuff with an Adjacency matrix and pretty much the same idea. Hope I get partial marks atleast...

I realised Ore's theorem just after INMO finished

Could someone tell me if I can get 1 point by showing that she can guarantee winning after 50 questions ? Tqies

L567 wrote: Navansh wrote: @above why is the rest solution needed if we write the strategy of detective The question asks "if and only if" ... Not just "if". So u need to prove both ways I think detective strategy was also iff not sure though, what partials can I expect

~5 ig because the 'only if' was more important in the question

LOL...It was my first INMO and it had to be the most difficult INMO ever....sed...I guess cut offs are going to be way low this year.what are your thoughts?

Math_god__ wrote: LOL...It was my first INMO and it had to be the most difficult INMO ever....sed...I guess cut offs are going to be way low this year.what are your thoughts? Probably solving 2 problems is going to be enough to clear it this year

Math_god__ wrote: LOL...It was my first INMO and it had to be the most difficult INMO ever....sed...I guess cut offs are going to be way low this year.what are your thoughts? I didn't qualify for INMO but I expect the Cutoff to be around 30. This was indeed very very tough compared to last year

EpicNumberTheory wrote: Math_god__ wrote: LOL...It was my first INMO and it had to be the most difficult INMO ever....sed...I guess cut offs are going to be way low this year.what are your thoughts? I didn't qualify for INMO but I expect the Cutoff to be around 30. This was indeed very very tough compared to last year So what would be the cutoff for the merit list according to u ? ~25 ?

here's an induction proof i hope works(for the claim of n edges and n-2 vertices)- (for the second direction). If there is a vertex of degree 1(say v), delete it and number the rest (which we know works by the induction hypothesis) Now if v was connected to w, and now if w has anything but n-1, the number v as n. otherwise, add 1 to all vertices then add w back in, and number it as 1. if there are no deg 1 vertices, it easy to show there will be a deg 0 vertex-number this n-1. Then we can choose a vertex of at least 2 and number this n. Delete these vertices and the (at least) 2 edges connected to deg 2 vertex. Then we're done by induction.

Take a card and point to every pair of that with another. There are $51$ such pairs and one has to be consecutive so asking $50$ questions and getting no on all of them proves that the final card is consecutive to the first. A yes allows to finish the game earlier than that.

What if card 1 is taken first than 3,4,5,6,...52. 50 chances no alternate

Physicsknight wrote: Take a card and point to every pair of that with another. There are $51$ such pairs and one has to be consecutive so asking $50$ questions and getting no on all of them proves that the final card is consecutive to the first. A yes allows to finish the game earlier than that. I also did same way but as op said, graph theory is required NB2007 wrote: What if card 1 is taken first than 3,4,5,6,...52. 50 chances no alternate the detective can now pick up the remaining card and say as consecutive

Navansh wrote: Physicsknight wrote: Take a card and point to every pair of that with another. There are $51$ such pairs and one has to be consecutive so asking $50$ questions and getting no on all of them proves that the final card is consecutive to the first. A yes allows to finish the game earlier than that. I also did same way but as op said, graph theory is required NB2007 wrote: What if card 1 is taken first than 3,4,5,6,...52. 50 chances no alternate the detective can now pick up the remaining card and say as consecutive How do you prove this is optimal? You need to prove its not possible in less than 50 moves also.

While proving this sum, I proved both the if and only if parts, but it was more of an arguemental proof and wasn't based on graph theory. So the if part is pretty much same as all other solutions but here is what I wrote for the only if: Let's consider that the the detective gets to ask only 49 questions. I used the following fact: To be absolutely sure that a certain pair is consecutive given a scenario where the magician has not already told her so, she must be certain that one of those 2 cards is not consecutive with any other card in the deck. But to be absolutely sure of this (given the cases of the cards being 1 or 52) she needs to ask 50 questions - a contradiction since she can ask only 49. Hence we see that the detective can only be certain of a given pair being consecutive if the magician told her so - but in the worst case scenario this will not happen, leading to the contradiction. This seems pretty similar to the if part, but it does seem to prove the converse.. How many marks can I expect?? @below, Yeah I get what you mean, that's what I felt too.. but if you think logically, its quite clear that there is no other way, right? I mean, the fact I used does seem to be logically correct..

I dont think that your proof for the only if part works... @above, because u only consider one card and u know that the detective has information about not all cards, but its possible that there exists a configuration for which even knowing not all cards is still enough to find a pair of consecutive cards, thats what u need to prove is not possible

Probabilistic method

dabest0209 wrote: While proving this sum, I proved both the if and only if parts, but it was more of an arguemental proof and wasn't based on graph theory. So the if part is pretty much same as all other solutions but here is what I wrote for the only if: Let's consider that the the detective gets to ask only 49 questions. I used the following fact: To be absolutely sure that a certain pair is consecutive given a scenario where the magician has not already told her so, she must be certain that one of those 2 cards is not consecutive with any other card in the deck. But to be absolutely sure of this (given the cases of the cards being 1 or 52) she needs to ask 50 questions - a contradiction since she can ask only 49. Hence we see that the detective can only be certain of a given pair being consecutive if the magician told her so - but in the worst case scenario this will not happen, leading to the contradiction. This seems pretty similar to the if part, but it does seem to prove the converse.. How many marks can I expect?? @below, but why?? Expect a 1 or a 2

dabest0209 wrote: she must be certain that one of those 2 cards is not consecutive with any other card in the deck. But to be absolutely sure of this (given the cases of the cards being 1 or 52) she needs to ask 50 questions If I don't get you wrong, over here you make the following assumption: to be completely sure that two cards are consecutive, once of those cards must be compared to everything else in the deck. This seems to be a common mistake, so I'll give an example where one can deduce that two cards are consecutive, even though both cards are adjacent to more than one card. Of course in this example, more than $n-2$ questions are asked, so it is not a counterexample to the question. It is only a counterexample to the above claim. Suppose there are $5$ cards $A, B, C, D, E$, and the magician has ruled out the possibilities of $AC, AD, EC, ED$ being consecutive. Every card has only been compared to 2 other cards, but one can prove that $C, D$ must be consecutive, and $A, E$ must be consecutive.

ohh, got it now.. thanks

Shorter version of the induction proof: 1) If there is a vertex of degree $1$, delete it and induct. 2) Otherwise, one vertex is unused, delete it and one edge and induct.

As noted in #2 it suffices to show that a graph on $n$ vertices with at least ${n-1 \choose{2}} + 1$ edges is always Hamiltonian. I mostly see inductive proofs of this above, so here is a proof using the probabilistic method: Set $m$ as the number of edges of the graph. For a permutation of the vertices of the graph say, $v_1, v_2, \cdots, v_n$ define it's score as the number of indices $1 \leqslant i \leqslant n$ such that $v_i$ and $v_{i+1}$ are neighbours in the graph. Here we take the convention that $v_{n+1} = v_{1}$. We want to show that there is a permutation with score at least $n-1$. Sample a random permutation and let us compute it's expected score. Defining variables $X_1, X_2, \cdots, X_{n}$ as the expectation of each edge's appearance, we see that $\mathbb{E}[X_i] = \frac{2m}{n(n-1)}$ and thus, by linearity the expected score is $\frac{2m}{n-1}$ which is larger than $n-2$ since $m > {n-1 \choose{2}}$. Thus there is some permutation giving a score strictly larger than $n-2$ and thus at least $n-1$, as desired.

Notice that the final guess is equivalent to all the other guesses, so include it with the other guesses. We claim that we need 51 guesses in order to ensure we chose two consecutive cards. Indeed, notice that with 51 guess we can choose an arbitrary card $C$ and guess the pair $(C,A)$ where $A$ is any other of the $51$ cards. Now, we will show that the task is impossible for $50$ guesses. Let $G$ be a graph on $52$ vertices and an edge between two vertices represents a guess of those two cards. So, there are $50$ edges in total. Let the set of these edged be $E$. If we can construct a Hamiltonian path which uses no edges in $E$, then there is an assignment of the cards where none of the guesses are between consecutive cards. We will prove that such a Hamiltonian path exists on any simple graph on $n$ vertices and $n-2$ edges. We will prove this by induction on $n$. Clearly, the statement holds for $n=2$. Now assume it holds for some positive integer $k$. Consider a graph on $k+1$ vertices and with $k-1$ edges. Clearly there must exists a vertex with degree $\leq 2$ so call it $v$. We now have two cases. Assume $v$ has degree $1$. If we remove $v$ then we have a graph on $k$ vertices and $k-2$ edges. Such a graph has a Hamiltonian path with endpoints $x,y$. Since $v$ has degree $1$, it cannot be adjacent to both $x$ and $y$. So, we add an edge to one of the ends of the Hamiltonian path on the $k$ vertices. This creates a Hamiltonian path on the $k+1$ vertices. Now, assume $v$ has degree $0$. Remove $v$ and an arbitrary edge from the Hamiltonian path on the $k$ vertices excluding $v$. Notice that this subgraph has $k$ vertices and $k-1$ edges, so we can guarantee that the Hamiltonian path intersects the set of edges at most once. If it does not intersect at all then just attach an arbitrary endpoint to $v$. If they intersect once at $e$ with endpoints $x$ and $y$, remove $e$ from the Hamiltonian path and add the edges $\{x,v\}$ and $\{y,v\}$. This creates a new Hamiltonian path passing through all the vertices. $\blacksquare$

Very funny problem. The answer is $50$, strategy being guessing $(v_1, v_i)$ for some fixed $v_1$ and all possible $v_i$. Let $G$ be a graph on $52$ vertices being the cards, and an edge between them if they could possibly be consecutive. Every query of the detective essentially deletes an edge of the graph. The detective can only be sure that she has found a pair of consecutive cards if there are no Hamiltonian cycles in $G$. However, if we delete less than $50$ edges, there will always exist two vertices which have degrees summing to at least $52$, so by Ore''s theorem a Hamiltonian cycle must exist, contradiction.

To win in $50$ questions, the Detective can just fix card $i$, then ask whether it's consecutive to $50$ random other cards. If all of the responses are no, then the detective can point to card $i$ and the one card not guessed, and otherwise just point to whichever two cards are consecutive. Now we prove the only if direction. Suppose the detective only asked $49$ or less questions. Let $G$ be a graph where the vertices are the cards and each pair of cards are connected iff they haven't been guessed together. Notice that the sum of the degrees of two nonadjacent vertices in $G$ is at least $2(52 - 1) - 49 = 53 > 52$ since deleting any edge only affects this sum by at most $1$. Therefore, by Ore's theorem, $G$ has a Hamiltonian cycle. If the Hamiltonian cycle is $v_1, v_2, \ldots, v_{52}$ and $v_1$ has card $i$, then it is possible that $v_2 = i + 1, v_3 = i + 2, \ldots, v_{52} = i + 51$ or $v_2 = i - 1, v_3 = i - 2, \ldots, v_{52} = i - 51$ (taken modulo $52$ where each $0$ is a $52$). In each possibility, the the edges of the cycle consist of every single pair of consecutive cards. However, there are more than $1$ such possibilities, so the detective cannot determine yet any two consecutive cards.

Let the cards be $c_1, c_2, ... , c_{50}$ in any order. If the detective is allowed to ask at least 50 questions, he may simply pick a fixed card $c_1$, and then take the pairs $(c_1, c_2), (c_1, c_3), \dots, (c_1, c_{51})$. If any of these $c_i$ ($2 \leq i \leq 51$) are consecutive with $c_1$, we are done, else point to $(c_1, c_{52})$ $\square$ Now, we prove that the detective is not guaranteed a win for $\leq 49$ questions. Take the "pointing" to be a question, and consider a complete graph with vertices $c_1, c_2, ... c_{52}$. Delete an edge for each question. Claim 1: $\text{deg}_u + \text{deg}_v \geq 52$ for any two non adjacent vertices $(u, v)$. Say the detective inquires $k$ questions about $u$, giving it a new degree of $51 - k$. Now, he can inquire a maximum of $50 - k$ questions for $v$, so we have $\text{deg}_u + \text{deg}_v \geq 51 - k + 51 - (50 - k) = 50$ $\square$ This means there must exist a Hamiltonian cycle, which could contain all the consecutive pairs, so the Detective is unsure about the win. Hence, we are done.

Cool one!!

Represent the cards by the set of vertices $V=\{v_1, v_2,\dots, v_{52}\}$. The Detective draws blue edges between pairs of vertices corresponding to the pairs of cards she inquired about. The Magician draws red edges between pairs of vertices, signifying potential consecutiveness. If a blue edge ever coincides with a red edge, then the Detective wins immediately. I show that the Detective cannot guarantee a win with $49$ questions only. Suppose all her questions were answered in the negative. It suffices to show that the Magician can always draw a Hamiltonian cycle of red edges with none coinciding with blue edges, given that the Magician can Draw a red edge between two vertices, given that they do not already have a blue edge between them. Decide which card a vertex represents (while in reality, the Magician depends on the Detective's terrible luck ). Note that each vertex can be an endpoint of at most $49$ blue edges, so for every vertex in the graph, there are two other vertices not linked to it by blue edges. Say a vertex $v_{i_1}\in V$ is not linked to $v_{i_2}$ or $v_{i_{52}}$ by a blue edge. Let $v_{i_1}=1$. The Magician could consider $(v_{i_2},v_{i_{52}})$ as $(2, 52)$ or $(52, 2)$. If $(v_{i_2},v_{i_{52}})\equiv(2, 52)$, then clearly there exists a red Hamiltonian path $v_{i_1}v_{i_2}\dots v_{i_{52}}$ not coinciding with any blue edges, otherwise the Magician would have had to say yes during the interrogation. But as $v_{i_{52}}$ is not linked to $v_{i_1}$, the Magician can add a red edge between them to get a red Hamiltonian cycle. We obtain the same cycle if $(v_{i_2},v_{i_{52}})\equiv(52, 2)$ as well. Either way, $v_{i_1}v_{i_2}\dots v_{i_{52}}v_{i_1}$ gives us the desired red Hamiltonian cycle. I show that $50$ questions are sufficient. If at some point the Magician says yes, we are done. Indeed, if the Detective inquires about $(v_1, v_i)$ where $i\in[2, 51]$ (This comprises exactly $50$ questions), then in the case that $v_1$ is neither $1$ nor $52$, by PHP, the Magician would have to say yes at some point. Otherwise, if the Magician replied with no each time, the Detective could deduce that $v_1$ and $v_{52}$ are consecutive with $(v_1, v_{52})\equiv(1, 2)$ or $(v_1, v_{52})\equiv(52, 51)$. $\blacksquare$

If $50$ questions were allowed, the asker can fix one card and ask whether any $50$ of the remaining $51$ are consecutive to it. If none of them ever are, the required card must be the One card not inquired about. For the other direction, consider a graph on $52$ vertices and draw an edge between two of them whenever we ask a question about the two. If $49$ edges are insufficient, it must mean that there is a hamiltonian cycle in the complement of the graph we drew. This is immediate by Ore's theorem.