Let's assume the mempool is low when you do the transaction for the puzzle.  If I send the coins with a fee of .1BTC and someone else finds the private key 30 seconds later and sends the transaction with a 1BTC fee, would they both be in the same block and the first transaction would win because it has an earlier timestamp, or would that not matter?