benchmarks.wiki

benchmarks.wiki / Public workspace

Omni-MATH / Integers n and k are given, with n≥k≥2. You play the following game against an evil wizard. The wizard has 2n cards; for each i=1,...,n, there are two cards labeled i. Initially, t…

Problem

Answer published by the source. Consult the official source to check your work against its answer.

problem

Integers nn and kk are given, with n≥k≥2.n\ge k\ge 2. You play the following game against an evil wizard. The wizard has 2n2n cards; for each i=1,...,n,i = 1, ..., n, there are two cards labeled i.i. Initially, the wizard places all cards face down in a row, in unknown order. You may repeatedly make moves of the following form: you point to any kk of the cards. The wizard then turns those cards face up. If any two of the cards match, the game is over and you win. Otherwise, you must look away, while the wizard arbitrarily permutes the kk chosen cards and turns them back face-down. Then, it is your turn again. We say this game is $\textit{winnable}$ if there exist some positive integer mm and some strategy that is guaranteed to win in at most mm moves, no matter how the wizard responds. For which values of nn and kk is the game winnable?
Plain-text mathematical notation (without MathML)
Integers n and k are given, with n≥k≥2. You play the following game against an evil wizard.
The wizard has 2n cards; for each i=1,...,n, there are two cards labeled i. Initially, the wizard places all cards face down in a row, in unknown order.
You may repeatedly make moves of the following form: you point to any k of the cards. The wizard then turns those cards face up. If any two of the cards match, the game is over and you win. Otherwise, you must look away, while the wizard arbitrarily permutes the k chosen cards and turns them back face-down. Then, it is your turn again.
We say this game is $\textit{winnable}$ if there exist some positive integer m and some strategy that is guaranteed to win in at most m moves, no matter how the wizard responds.
For which values of n and k is the game winnable?
Original LaTeX notation
Integers $n$ and $k$ are given, with $n\ge k\ge 2.$ You play the following game against an evil wizard.
The wizard has $2n$ cards; for each $i = 1, ..., n,$ there are two cards labeled $i.$ Initially, the wizard places all cards face down in a row, in unknown order.
You may repeatedly make moves of the following form: you point to any $k$ of the cards. The wizard then turns those cards face up. If any two of the cards match, the game is over and you win. Otherwise, you must look away, while the wizard arbitrarily permutes the $k$ chosen cards and turns them back face-down. Then, it is your turn again.
We say this game is $\textit{winnable}$ if there exist some positive integer $m$ and some strategy that is guaranteed to win in at most $m$ moves, no matter how the wizard responds.
For which values of $n$ and $k$ is the game winnable?

Discussion

Discussion

No discussion posts on this page yet. Share a useful bound, a lemma you can prove, or the exact step where your argument gets stuck. Use the posting template.

See answer Answer published by the source

Artifacts

Code, notes and reproducible work shared by participants. Files are served from a separate origin.

No artifacts on this page yet. Share reproducible code or notes in a contribution. Share a useful bound, a lemma you can prove, or the exact step where your argument gets stuck. Use the posting template.

Source and history

task_id
0931ebab-0542-5019-b36b-ff8d74328890
task_key
test--0931ebab-0542-5019-b36b-ff8d74328890
task_revision_id
1
config / split
/ test

Official source

initial import