43
This:
Just to break down the first version of this:
So we have with 3 eggs:
40
It's definitely not optimal! Here's a counterexample:
Start from the white area.
Greedy algorithm would make you do all the colours on the top right (5 moves: yellow, green, dark green, blue, dark blue), then the red (1) and then all the other colours (6 moves), making a total of 12 moves.
There is an obviously more efficient method: orange, yellow, green, ...
38
That problem is NP-hard, so an efficient strategy to calculate the optimal moves would be a major breakthrough in computer science. Of course, there might be a greedy strategy, but not an efficient one, e.g. that works in exponential time.
To prove that it really is NP-hard, we will reduce vertex cover to your problem.
Let $G$ be the input graph. We will ...
35
You need to ask
35
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 ...
34
Solution for $n$ bananas, where $n$ is the number of bananas you own, and $c$ is the number of bananas the camel can carry:
This is because, if the camel moves the bananas 1 mile at a time, he needs to make two trips for each load beyond his current capacity.
Define $t = \lfloor\frac{n}{c}\rfloor$ Therefore, the total number of miles the camel can reach is:...
31
4.8264 km
Plough a $120°$ section of the circle, extending both ends in a straight line by a distance of $\sqrt{1/3}$ km to meet the vertices of a hexagon enclosing the circle. Two more lines of length $1$ km and $\sqrt{1/3}$ km are ploughed as shown to cover paths through the other half of the circle. The total length ploughed is equal to:
$$\frac{2\pi}{3}...
30
Building off of Kevin's answer, I can get it to 33:
###|.#.|.#.
###|...|...
###|...|...
---+---+---
.#.|###|.#.
...|###|...
...|###|...
---+---+---
.#.|.#.|###
...|...|###
...|...|###
Keeping his assumption "that a completely empty 3x3 box can always be solved as long as there are four completely full 3x3 boxes in the same major row or column."
and we can ...
28
As remarked by sth, this is an open problem, a topic of ongoing research. It is known as Moser's worm problem. The Math Overflow thread Smallest area shape that covers all unit length curve cites some recent result.
A known result is that the smallest possible convex blanket has an area between 0.227498 to 0.231999. (In comparison, a half-circle of diameter ...
27
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:
26
First of all, the brute-force approach does not work. If the Camel starts by picking up the 1000 bananas and try to reach point B, then he will eat up all the 1000 bananas on the way and there will be no bananas left for him to return to point A.
So we have to take an approach that the Camel drops the bananas in between and then returns to point A to pick ...
24
4.8205 km (or 4.8189 km with slightly more work).
Let $ABCDE$ be a circumscribed regular pentagon around the circle, let $M$ be the point of tangency between segment $BC$ and the circle, and let $N$ be the point of tangency between segment $DE$ and the circle. Let $X$ be the midpoint of line $BE$.
Plow the arc of the circle connecting $M,N$, and plow the ...
23
No idea if this is optimal (also have no proof), but it's possible to do
Example:
23
21
I can do a little better, using coins of
I can pay amounts up to (and including)
(without change).
Explanation:
One can ask what $N$ is as function of the # of different coin values and maximum # of coins in a single payment.
20
20
I believe Spencerkatty's solution is maximal...
Any net may be constructed by choosing which of the 81 cells to mask.
There are $\sum_{k=0}^{81}{81\choose k}=2^{81}$ ways to construct a net.
Rather than attempt to search this vast space we can attempt to partition the space in a way that will allow us to find out where we may need to look in more detail.
...
20
Trivially, 50 will make the game impossible, since positions 50 and 51 will be unmovable.
Therefore the solution is:
(Thanks to Hakdo for making me realize I was off by one, and justhalf for pointing it out!)
20
Quick lower bound:
If you were to
19
I think it is possible to do with
Which look like
19
Strategy:
Expectated gain:
Conclusion:
18
In addition to explicit solutions existing for parking 28 cars (of which there are very many), some very simple rules that drivers can use when parking, always seem results in achieving this number, so a very large family of possible solutions can be generated by having 28 cars obey the following rules:
If you can park next to a wall without blocking anyone ...
18
Edit: A lot of credit is due to @ffao for devising a better way to deal with the case where there is just one room and reducing the solution by one. (Subsequently, @Lawrence has managed to do even better in their answer).
I now think it can be done with
Strategy
If we are allowed to assume that there is more than one room, then it can be done with
...
18
The soldiers starting on the slabs marked with an x must all end up at different slabs. Therefore, there will be at least 9 occupied slabs and therefore at most 16 empty slabs.
One solution involves every soldier ending up on one of the slabs marked O. Notice that every slab is adjacent to some O, so this is possible.
x . . x x . O O . .
x . . . . . . ...
17
The minimum number of questions of the special form “Person $i$, is Person $j$ a knight?” that will guarantee to find everyone's identity is $3(N-1)/2$. This was first proved by P. Blecher in this paper.
Suppose we know for sure that at most $J$ jokers are present, where $J < N/2$. My paper on the problem shows that $N+J-1$ is the minimum number of ...
17
Alternatively:
17
The greatest X for which you can find the stack with the fake coins in 3 weighings is:
Unfortunately, the strategy isn't as easy to describe as the one in my previous answer (you can read it in the edit history if it helps understanding this one). Here it is:
An example on how to interpret the weighing results:
To brute-force find the selections (a list ...
17
This game
Here's why:
In summary,
16
While the amount of bananas is larger than 2000, the camel will have to make 5 trips to shift them. At a cost of 1 banana per mile, this will cost 5 bananas per mile in total.
While the amount of bananas is larger than 1000, it takes 3 trips to shift them, so a total cost of 3 bananas per mile.
For the final stretch, it just takes a single banana per mile.
...
16
We use the following two tools:
Tool 1: Every real number $x$ satisfies $\lfloor x\rfloor>x-1$ (with strict inequality).
Tool 2: All positive real numbers $y$ and $z$ satisfy
$\frac{x}{y}+\frac{y}{x}\ge2$; indeed this inequality is equivalent to $y^2+z^2\ge2yz$ and $(y-z)^2\ge0$.
Now the expression $E$ that is to be minimized can be estimated (by using ...
Only top voted, non community-wiki answers of a minimum length are eligible
