4
$\begingroup$

Let $N \gg n \geq 2$ be fixed natural numbers. In the Gacha stamp game, players are given an $N \times N$ square grid, with each point occupied by a unique stamp.

On every turn, they may choose a subsquare of size $n \times n$, and they are given uniformly at random a copy of one of the stamps from the subsquare.

Question: Under a strategy that is optimal for minimising the expected time taken, what is the expected time taken to get one of each stamp?

As detailed in the comments, the simple non-optimal strategy of filling in each subsquare before moving on gives expected time $\sim N^2 \log n$. The exact result is actually $N^2 H_{n^2}$.

In any case, it is clear one cannot get better than $\Theta_n (N^2)$ with any strategy.

So the natural next question is whether one can improve the $\log n$ factor. Failing that, one can ask for precise constants, which I think is also interesting.

Improve this question
$\endgroup$
14
  • $\begingroup$ Is the strategy open loop? $\endgroup$
    – user479223
    Commented Oct 18 at 2:40
  • $\begingroup$ Sure, if you want, though if probably only depends on the collection of stamps you currently have, counted without multiplicity. So you could get a Markov strategy. @user479223 $\endgroup$
    – Nate River
    Commented Oct 18 at 2:52
  • 1
    $\begingroup$ @user196574 Oh i guess it may not have been clear - $n$ is fixed by the game host. $\endgroup$
    – Nate River
    Commented Oct 18 at 5:55
  • 1
    $\begingroup$ @user196574 I agree with the $\Theta(N^2)$, now the interesting part is the coefficient of this $N^2$ in $n$… $\endgroup$
    – Nate River
    Commented Oct 18 at 5:56
  • 1
    $\begingroup$ @NateRiver Thanks, that makes sense! Then one has at least $N^2 H_n$ as a non-optimal strategy, so the best strategy is no worse than $\sim N^2 \log(n)$. I'm curious if you can get better than $\log(n)$. $\endgroup$
    – user196574
    Commented Oct 18 at 5:57

1 Answer 1

Reset to default
2
$\begingroup$

One can improve the $\log n$ factor by at most a constant.

Divide the $N \times N$ board into $n\times n $ squares. (Even if $n$ is not a divisor of $N$, one can divide at most a quarter of the board in this way). Call these the fixed squares.

Each $n \times n$ move intersects each of the fixed squares. The progress we make from the $n\times n$ move is at most the progress we make if we could make four simultaneous moves in the four fixed squares it intersects, with the stamps in the four subsquares we obtain possibly correlated.

But this version of the problem takes time at least $N^2 H_{n^2}/4$.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ Elegant as always… $\endgroup$
    – Nate River
    Commented Oct 26 at 11:31

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .