I wrote a computer program and it showed that $18$ moves is the optimum.
Here is one such solution:
Oddly enough, even if you relax the condition of alternating white and black moves, it cannot be done in fewer moves.
For $3\times3$ the optimal number of moves is $16$.
Without the need to alternate moves the optimum is $14$ moves, for example just by ...
You can do better than the greedy algorithm. With coins of value
you can get N =
I wrote a search program for this but it isn’t going to finish searching the entire space in reasonable time, so I don’t know whether that’s optimal. Here are all the optimal solutions for up through seven coins:
I can do a little better, using coins of
I can pay amounts up to (and including)
One can ask what $N$ is as function of the # of different coin values and maximum # of coins in a single payment.
The answer is 7, It's a simple extension of the Magic Calculator trick.
Each card represents a bit, with the upper left index value being the value of that bit.
To perform it as a trick, you ask the volunteer to pick a number between 1 and 64, and hand you the cards on which their number appears. Add up the index values on the selected cards, and you have ...
I can improve a little bit further using the coins
With those coins I can express (with at most 8 coins, and no change) every non negative integer up to (and including)
I'm not sure this is the definitive answer, as I was able to outperform the greedy algorithm for a smaller number of coins.
Explanation of how the program works:
I can ensure that I receive at least
To get this amount of coins, I could apply the following strategy:
My friend can also ensure that I do not get more coins than this in the following way:
So it appears that I should have chosen a fairer game to distribute the coins...
Between 10 friends, there are only 45 unique pairs.
Each friend will participate exactly 9 times, which means after 45 rounds everyone will be level 10.
Since it's impossible to get an item on the first & last run, there is a theoretical maximum of 43 items you can get.
However, due to some restrictions, it seems to me like it's impossible to get this ...
The optimal solution is
This set of coins allows N =
This set of coins is given in this paper: Some Extremal Postage Stamp Bases, by Michael F. Challis and John P. Robinson.
This paper was found by @alephalpha.
I may need some clarification on counting but I think I've found a solution in which the landlord needs to repair 38 squares while filling just 3 other apartments with water.
Anders Kaseorg's answer on the 8/8 list has the most optimal N/N answers up to N = 7 in a spoiler. And he has...
With a little enumeration, it's easy to see that you can use that set to get up to...
It's actually pretty simple to reason this out without brute forcing it (too much).