14
I can do it in
This is optimal because:
More detailed argument for symmetry:
11
You can build a structure something along the lines of a da Vinci bridge, where the weight of the structure itself keeps it from falling apart:
It's easiest to build on the tabletop; you can then pick it up by the bottom nail, watch how gravity locks the structure into place, and then balance the whole on the vertical nail.
11
Kevin Ferland and I have a paper on this:
Maximal Crossword Grids, Journal of Combinatorial Mathematics and Combinatorial Computing (Feb. 2019)
See also OEIS A243826, which has a link to Ferland's earlier paper.
Here are a summary table and selected examples from
Illustrations of solutions for 3 ≤ n ≤ 50 PDF
at OEIS A243826.
$$ \small\begin{array}{rccc|rccc|...
7
I choose to play
My strategy is as follows:
Continue until this is no longer possible or doing so would end the game. That means
So if I take
6
As with pretty much all the nim variants, this one can be solved by starting from the end and working backwards. With the original total number of stones being an odd number (15, as given in the title) the players will have the same parity whenever there's an odd number of pebbles left, so it's easy to work out the best strategies: they are the ones that put ...
5
The strategy is to do a move that
In particular, for $15$ pebbles, your first move would be
The reason this works is more interesting than with other single-pile nim variants.
5
Alice can achieve a victory probability of
Proof:
Proof that there is no better strategy:
3
For the maximum score:
On observation:
Doing the math:
3
The simplest strategy is to
As an analogy, one can
3
This is known as the Two Generals' Problem.
Tom Scott made a video on this topic in 2019. He suggests solving this problem by making use of an idempotency key.
Otherwise, it is impossible because the generals would be led to an infinite regress of recieving and transmitting acknowledgement.
3
Take the string as "abcbc" and k=5. Now, according to the algorithm we have "aabbccbc"(three extra characters). But, due to the repitition of "bc", we can take the string as "abcbcbc"(which has just two characters extra). This will give us exactly 5 subsequences of "abcbc".
2
Well here's 2 ways I thought of...
2
Q1: Base algorithm.
We can then apply the following optimizations:
Optimization 1:
Optimization 2:
Optimization 3:
Q2: Proof that the optimized algorithm is always optimal (partial)
Minimum number of steps:
Maximum number of steps per move:
Number of steps performed by the algorithm per move;
However:
2
I arrived at the same solution as Desouvi, but I reasoned it from the other direction.
The final answer is
To start with, I observe
This splits the problem into two smaller problems.
But since I already know
I can subdivide the problem again
At this point, a pattern emerges:
I believe this to be minimal because
1
What I tried is the same game where you have 101 stones but instead of winning more than five would make you lose I tried it with 3.
Working on @Rand al' Thor's strategy by picking 5 first, I figured out we can always lose if we copy our opponent's move every time.
For eg.
If I first play 5, then we are left with 96 stones in total.
Our opponent might take 3 ...
1
Here's one possibility:
Our strategy dictates the final string should be
But we can do better:
1
1
So, here's what I might do:
Only top voted, non community-wiki answers of a minimum length are eligible
