# Tag Info

## Hot answers tagged optimization

50

I think this arrangement works for the bonus question:

47

@hexomino's answer is correct and well-reasoned, as always. Here's another approach, which to me feels much more.. "axe-to-the-head" is what I'd call it in my native language, so I thought it might be interesting enough to warrant posting. Lower bound: (This is what @trolley813's encrypted comment is saying.) Upper bound:

46

I think this will do it

44

This: Just to break down the first version of this: So we have with 3 eggs:

42

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:...

40

Here's a solution that only takes 28 points:

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 ...

37

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 ...

36

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 ...

35

You need to ask

32

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} ...

31

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 ...

30

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 ...

29

First solution - 50 moves Second solution - 59 moves Current solution - 66 moves (beaten by Retudin - 70 moves and Rewan Demontay - 139 moves) Moves:

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

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 ...

26

It might be possible to do a little better, but I think I can get Explanation:

25

No idea if this is optimal (also have no proof), but it's possible to do Example:

25

You're

25

The rules of the question state that: On your final grid, a letter (actually several is also mathematically possible) will be more frequent than all the other letters. Your aim is that this letter appears as much as possible. If we interpret this to mean that all letters appearing with the greatest frequency contribute to the score then it is possible to ...

25

Since we are talking about a standard game of chess (although with both players co-operating), we know that there are four pieces that cannot possibly make a capture in the series: the two bishops on the wrong coloured squares one of the kings (the other can be the last to capture) the first piece that gets captured (cannot be any of the above). ...

24

24

Eeny meeny myny moo (or however you want to spell that)

23

(Kind of) analytical solution that only requires small amount of calculations, (potentially) doable by hand. First step: we can safely drop 2, 3 and 7 from the equation as those digits are used in 23 and 17. Now, we need to build a prime from: 5, 11, 13, 17, 19, 23, 29 and 31. Second step: let's try to build the shortest number possible from these numbers. ...

22

The answer is I wrote a Java program to find it:

22

UPDATE 2: To put OP out of their misery find now at the very bottom of this post an answer to what they probably mean. UPDATE: OP has changed the rules, so this is no longer valid, but see bottom of this post for an answer to the modified question which I assume is still not what OP has in mind. I say it is "Proof": With the new rules the answer ...

21

21

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. ...

Only top voted, non community-wiki answers of a minimum length are eligible