You should randomize over all available hiding spots so that the probability of putting the coin in some spot is proportional to the effort needed to search that spot. This way future you won't have any preferred place to start. I think this strategy maximizes the expected effort spent by future you, assuming he knows your strategy and acts optimally.

You randomize it at the Nash equilibrium. The more obvious the place, the less probability you give to hiding it there.

The Nash equilibrium is based on the idea that your opponent will know your strategy, and fight specifically against it, and it will still be the best strategy. In this case, if you hide it using that probability distribution, no matter how you look for the coin later, you'll be exactly as likely to find it.

If interpreted as it's probably intended, this is basically about maximizing the amount of information lost in the memory-wipe stage. A good strategy might be to choose some large volume that can't easily be scanned -- your lawn if you have a house, the cracks between the floorboards, et cetera -- and use some indexing system to pick random coordinates. Better yet, pick several such volumes and pick randomly between them. Add some random debris to throw off metal detection. Move furniture around to create red herrings. Hire a friend to rearrange your stuff for a day and let them do the hiding. If you live in an environment conducive to it and the reward's big enough, move to a different but internally identical space -- another apartment in the same building, say -- and match the old space's internal configuration as best you're able, with the target left in the old one. There are a lot of options, but most of the reasonably good ones already constitute a near-guarantee of success.

A more creative strategy might be to set up consequences for retrieval which exceed the reward you'd be getting: for example, to hide the coin in your compost pile and then mine it with explosives, with the mined region clearly marked and a deactivation timer set to go off after the deadline has expired. The threat can always be made credible because you have essentially perfect information about the personality making it.

This reminds me of Berry's Paradox: the most arbitrary hiding place you can think of is by definition not very arbitrary.

Here's a deterministic solution that does at least as well as hiding the coin randomly (I think?). Take the expected amount of time t it would take to find the coin by random search. Write down all the deterministic coin-hiding algorithms you can think of on a piece of paper as fast as you can, starting with the most obvious. Continue until t time units have elapsed, and then use the last algorithm you thought of.

This does assume we're counting the time it takes your future self to compute your hiding algorithm towards the time it takes him/her to find the coin.

If I extend the finite familiar environment to shops nearby my house, I thought of an interesting idea:

Generate a list of the nearest third party coin counting machines near my house. Like one of those Coin Star machines you see at a Grocery store. Roll a random die and select that element off the list. Deposit the coin along with other coins. If I have time, do this at multiple coinstar machines.

The store manager probably doesn't have the keys. Even if I think of this exact idea, I still have to either break the law and smash the machine (And then it's still a needle in a haystack problem, except the cops are hunting for me.) or socially engineer 1 or more Coin Star employees (Who isn't even in the grocery store, I have no talent at this, And then it's still a needle in a haystack problem.) and that's assuming I picked the RIGHT grocer store.

Even if I think "I would have put it into a randomly chosen third party coin counting change machine." I won't have any way of confirming the theory easily. or even being sure WHICH third party coin counting machine. If I spend hours and hours trying to check one, it could turn out it wasn't even at that grocery store. So it takes me less than an hour to generate this heuristic, but DAYS to solve, if it's even possible for me to do it at all.

I can still apply this reasoning to my house if my backyard is allowed.

Roll dice determine where I actually dig a deep hole. Put the coin in that hole. Disturb my entire yard so that I can't tell the difference. I can dig a single hole and disturb my yard in a much shorter time then I can actually dig out my hole yard.

If I can't leave the house, randomly select a toilet, or sink drain or tub drain and flush it down with water. Disturb all plumbing covers. The coin is probably SOMEWHERE in my houses plumbing. (Plumbing pipes often have catches for that sort of thing.) I have no idea where. It takes a long and effort to disassemble all of the plumbing in my house.

If I have even more time, do MULTIPLE ideas. If my entire backyard has been disturbed and all of my plumbing covers removed, I don't know whether I flushed it or buried it.

If the coin doesn't have to be intact when hidden, but I do have to return all pieces, split the coin into multiple pieces and do multiple ideas.

But if you randomize, then you have the risk of placing the coin at a location where it can be easily found, like on a table or on the floor.

That's not really a problem--you could just randomize over the set of not-obviously-visible locations. You could even rearrange the furniture and objects in your house such that the rearranged version has more hiding spots than the current arrangement of furniture.

I've continued asking people about this problem offline, and I'm finding that they are not very good at assuming the least convenient possible world, but they are very good at spotting loopholes in the problem as formulated. Another classic:

"I would put the coin in a sealed envelope. On the envelope I would record the events prior to my memory being wiped. Then I would leave it in plain sight on my nightstand."

I would hide it in a place that is not too hard to find but really hard to reach so that my future self will stop and think about why I put it there. I (in the future) will then hopefully realize that if the task really was as told then I would have "hidden" the coin at the easiest possible place. Therefore, something about the task is wrong. As the coin is hard to reach, my past self probably doesn't want me to find it. This doesn't make sense unless one of us (past or future self) has been lied to. Having the same mental faculties as I have now, I trust that my future self will make the right decision, which may depend on the specific circumstances.

This approach is quite risky as it assumes that my future self will in fact follow the same line of reasoning I just did, but then again that is kind of the point of this task.

If it's allowed I could of course also just leave a note explicitly saying the above.

You could put it in a safe with a randomized combination.

You could eliminate those risky locations by excluding them as alternatives in your randomization process, but that would mean including a chain of reasoning!

Do I know that while I was trying to hide the coin I tought I would lose if I found it later?

Edit: Gwern said it first.

(You also don't formulate it right. If the memory-wiped self is told that finding the coin wins, and also that a former self placed the coin for him to find, wouldn't he infer that his former self would be trying to help him win and so would begin his search at a Schelling point? He wouldn't even consider trying to beat an adversarial strategy like 'randomize' because he doesn't think there's an adversary!)

I think I would write down a list of places where, if I had hidden it there, they would be hard to find even if I knew where to start looking, (my house has a fair number of these,) assign numbers to each, and then roll a die and hide it in the one with the corresponding number.

I'd probably assign individual numbers to options like "hidden amongst the belongings in any drawer in the house which I do not use regularly," and determine which one to use by number assignment and random number generator if I rolled that option.