I got Click to reveal hidden text

KaiDaMagical336 wrote:

I got Click to reveal hidden text

I don't think so.Since for $n=3$ ,$2$ domino works:: $21,13$

Shoot forgot about self-cycles

I got $\frac{3n-5}{2}$ oops

twinbrian wrote: I got $\frac{3n-5}{2}$ oops I got this as well. I believe the construction is \[ (1, n); (n, 2); (2, 3); (3, n); (n, 4); (4, 5); \cdots; (n-3, n-2); (n-2, n); (n, n-1) \]

The answer is $\frac{3n-5}{2}$. A construction is $$[n,1],[1,2],[2,3],[3,1],[1,4],[4,5],[5,1], \cdots, [1,n-3],[n-3,n-2],[n-2,1],[1,n-1]$$which works since $n$ is odd, and then the only remaining domino with $1$ is $[1,1]$ so it cannot be placed by Anton. Now suppose Amin places $ k < \frac{3n-5}{2}$ dominos. Let a domino be bad if it has the same number twice, and all other dominos be good. First remove all bad dominoes in Amin's path. If $k'$ is the number of remaining dominoes, we have $ k' < \frac{3n-5}{2}$. Note that the sequence of good dominos is equivalent to a path on $K_n$, the complete graph on n vertices. Let the set of edges left after Amin creates a sequence be $G$. We essentially want to show Anton can create a Eulerian path (using each edge exactly once) on $G$ (excluding bad dominos for now), starting on the vertex $v_f$ that Amin finished on. Lemma: G is connected. Proof: By contradiction: suppose $n>1$ connected groups are in G. Choose some connected group, and let it have $x$ vertices. Then at least $x(n-x)$ edges must be removed as these are edges between different connected groups. For $x=2$ or $x=n-2$, note that $k' \geq x(n-x) = 2(n-2) \geq \frac{3n-5}{2}$ since $n \geq 3$. But $x(n-x)$ increases on $x<\frac{n}{2}$ and decreases on $x>\frac{n}{2}$, so for $2 \leq x \leq n-2$, $k' \geq x(n-x) \geq \frac{3n-5}{2}$. The only remaining cases are $x=1$ or $x=n-1$. Here, one connected group has $n-1$ vertices while the other has $1$ vertex $v$. But Amin's sequence is a path on $K_n$ that does not repeat edges, so after every edge ending on $v$, the next edge must start on $v$, and the following edge must not contain $v$. So optimally to minimize the number of edges, Amin's path would be of the form $I,O,X,I,O,X, \cdots, I,O$ where $I$ is an inbound edge, $O$ is an outbound edge, and $X$ is an edge not containing $v$. To remove all $n-1$ edges between $v$ and another vertex, Amin's path would have length $k_{min} = \frac{3}{2}(n-1) - 1 = \frac{3n-5}{2}$, so again $k' \geq k_{min} = \frac{3n-5}{2}$. We have that shown if $G$ is not connected, $k' \geq k_{min} = \frac{3n-5}{2}$. But $ k' < \frac{3n-5}{2}$, contradiction, so $G$ is connected. $\blacksquare$ Now, we show there exists a Eulerian path on $G$ starting at $v_f$. Since all vertices on $K_n$ have even degree as $n-1$ is even, and Amin follows a path, it is easy to see all vertices in Amin's path have even degree except the first and last vertex $v_i$ and $v_f$ respectively. So on G, we find all vertices have even degree except $v_f$ and $v_i$, which either both have odd degree (if $v_i, v_f$ are distinct) or both have even degree (if $v_i,v_f$ are the same vertex). By Euler's Theorem in graph theory, we know that for any connected graph with all even degrees, there exists a Eulerian cycle (the proof is not hard as well through induction, by removing a cycle $C$ in $G$ to form $H$, inductively constructing Eulerian cycles for each connected component in $H$, and then traveling along these cycles while traversing along $C$ to form a Eulerian cycle on $G$). So if $v_i,v_f$ are the same vertex, we can just use a Eulerian path by this theorem. On the other hand if $v_i, v_f$ are distinct, we can extend Euler's theorem to the following: Claim: For any connected graph $G$ with all even degrees except for two vertices $x,y$ that have odd degrees, there exists a Eulerian path from $v_x$ to $v_y$. Proof: Casework on if $e_{v_x,v_y}$ (the edge between $v_x$ and $v_y$) is in $G$: Case 1: $e_{v_x,v_y}$ is not $G$. Then adding $e_{v_x,v_y}$ to $G$ to get $G'$, by Euler's theorem we have a Eulerian cycle on $G'$ since $G'$ has all even degrees and is also a connected graph. We can then remove $e_{v_x,v_y}$ to get a Eulerian path between $v_x$ and $v_y$. We can reverse the path if needed to get a Eulerian path from $v_x$ to $v_y$. Case 2: $e_{v_x,v_y}$ is in $G$. Remove $e_{v_x,v_y}$ to $G$ to get $G'$, which has all even degrees. If $G'$ is also connected, similar to Case 1 we have a Eulerian cycle on $G'$ by Euler's Theorem. Shifting along the cycle to start and end at $v_x$ and then adding on $e_{v_x,v_y}$ at the end, we have a Eulerian path from $v_x$ to $v_y$. On the other hand, if $G'$ is not connected, it is formed of $2$ connected components where $v_x$, $v_y$ are in different connected components. Let $c_{v_x}$ and $c_{v_y}$ be these two connected components, each of which also has a Eulerian cycle $C_{v_x}$ and $C_{v_y}$ respectively by Euler's Theorem. Then shifting $C_{v_x}$ and $C_{v_y}$ so that $C_{v_x}$ starts and ends on $v_x$ and $C_{v_y}$ starts and ends on $v_y$, we can take the path $C_{v_x} \cup e_{v_x,v_y} \cup C_{v_y}$ which is a Eulerian path in $G. \blacksquare$ So using the Lemma and the Claim, Anton can create a Eulerian path on $G$ starting on $v_f$, where Amin ended, so combined with Amin's sequence, we have a Eulerian path on $K_n$. Finally, to add back the bad dominos, since $G$ is connected by the Lemma, for any number $i$ with $1 \leq i \leq n$, Anton will have at least one good domino $d_i$ remaining with $i$ as one of its numbers. Adding back Amin's bad dominos (which does not change the value of $v_i,v_f$), Anton can add any bad dominos that Amin has not already placed by adding it in between a corresponding good domino that he places. This creates a row of all $\frac{n(n+1)}{2}$ dominos with Amin's sequence as the first part of this row, showing that $\frac{3n-5}{2}$ is indeed the minimum such value of $k$, as desired.

Solved with eisirrational and goodbear. The answer is $k = (3n-5)/2$. Here is a possible construction: \[(2,1), (1,3), (3,4), (4,1), (1,5), (5,6), \dots, (n-1, 1), (1,n).\]This works, since the only remaining domino with $1$s is $(1,1)$, which cannot be placed anywhere. We now show $k \geq (3n-5)/2$. Now consider the obvious $K_n$ graph interpretation with self-loops, where the domino $(i,j)$ represents the edge between nodes $i$ and $j$. Then the problem asks for the largest path $P$ which is not part of any Eulerian path. Let $K_n \backslash P$ denote the graph after deleting the edges of $P$. The following claim is crucial. Claim.The graph $K_n \backslash P$ is disconnected. Proof. Note that any node in $P$ has even degree, except for the endpoints $x$ and $y$ of $P$. Thus, the same holds for $K_n \backslash P$. If this graph is also connected, then by Euler's theorem there is an Eulerian path from $x$ to $y$. Stringing this with $p$ yields an Eulerian path (actually, an Eulerian cycle), which is a contradiction. $\square$ Now split $K_n$ into two components $A$ and $B$ which are mutually disconnected. Then if $|A|, |B| \geq 2$, then $P$ has at least $|A||B| \geq 2(n-2) \geq (3n-5)/2$ edges. Thus, without loss of generality $A$ consists of a single vertex $v$. Then the $n-1$ edges from $v$ must all be removed; moreover, for three consecutive edges of $v$, at most two of them have an endpoint at $v$. So we have $\tfrac23(k+1) \geq n-1$, or $k \geq (3n-5)/2$, as desired.