New answers tagged optimization
7
I did it in 38 moves:
For the update, I did it in 43 moves:
3
For starters,
1
Solution in
plies:
Remark: the alternative try
isn't allowed because
2
-1
9*9 solution:
Looks like:
14*14 solution:
Looks like:
5
For $14$x$14$ I got...
With this ...
Or with this...
3
I assume
Then one solution would be
As shown below
And
No idea if this is minimal though
9
I think the answer for $14 \times 14$ is
Achieved as follows
While the best I've achieved for $9 \times 9$ is
Achieved as follows
3
3
Intended solution
Note: This answer is here for potential future solvers. Due to the high elegance of this solution I thought it would be ideal to post it as an alternative to @Dark-Thunder's solution. You can see many similarities between these answers, the general movement is the same! All other potential valid solutions should be caught under these ...
7
3
Generalizing my comment on Gareth's solution, we can
arrange Pascal's triangle as a right triangular array and ignore the right half ($n < 2k$) to obtain something like this:
1
1
1 2
1 3
1 4 6
...
We then, for any $N$,
0
Gareth has found the optimal solutions, but here is an R script if anyone wants to mess around with the upper bounds for n, just change the value of the variable"UpperBound".
require(pracma)
UpperBound<-500
n<-rep(1:UpperBound,each=UpperBound)
k<-rep(1:UpperBound,times=UpperBound)
data<-as.data.frame(cbind(n,k))
colnames(data)<-c("n","k")
...
5
Choosing
gets to within about
of the desired answer. I think this is best possible with <= 100 cards.
Found with the help of a computer, but purely as an aid to calculation. My approach was to
[EDITED to add:]
Out of curiosity, I also ran a more automated search for the larger bound of n=500 mentioned in the OP. For this,
The automated search also ...
1
An initial lower Bound
Finding a better lower bound
Doing a bit better with some brute force
The code used : https://pastebin.com/8nQ9UgBP
Notes about the code:
6
Edit: as @DarkThunder pointed out, this is incorrect.
My most perfect soup contains
-3
since they are 1/64th increments, you can be left with a minimum of 1/64th of a cup. Add 1 cup, remove 1/2 cup, remove 1/4 cup, remove 1/8 cup, remove 1/16 cup, remove 1/32 cup, remove 1/64 cup, there is 1/64th of a cup left.
1
A naive approach somehow manages to get them up the mountain in
9
If the answer isn't 8, then how about
5
An upper bound
This can surely be improved substantially because
Another (smaller) upper-bound
Applying a bit of brute force,
A smaller upper bound still
And smaller still
2
0k I'll start with my intuition which probably is not the best one, but you can outdo me now ;) .
Idea:
Java code:
Result:
Note:
Other idea:
3
A) If the board were instead very large (many billions of cells, for example), what limit could we place on the maximum sign density?
B) Again on a very large board, what limit could we place on the sign density if we eliminate the 4th rule and allow older signs to be blocked?
C) Solutions for odd-size boards, with and without rule 4
4
Alternative solution with 8 steps:
Rotate the highlighted regions, first the left figure, then the right.
4
This is not a (new) answer to the original question, but I don't have enough reputation to comment. I tried to address the call for generalization using a similar technique as Jaap. Below the results for the board sizes that fit in my main memory. Unfortunately, 6 x 6 does not fit.
size # configs w b
=========================
3 x 2 180 12 13
...
3
I have found a better answer than this answer by just playing with it:
with
not sure this is optimal though, but most likely. gonna write a program if noone does that until I wrote :D
8
Edit: my answer was inadequate. Only downvotes now please.
@Oray asked to follow up his answer and I found a fault in my previous work, resulting in
My original and obsolete answer was
3
I think the longest prime length rope we can have is of length
Reasoning
6
The answer is
Moreover,
First note that
Step 1
Step 2
Step 3
Step 4
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 ...
1
EDIT: As @greenturtle pointed out in a comment, it seems that everyone else is doing the count by ply, and not the whole moves. The question is unclear to me about this on how the count is done. So thus my count is wrong by the majority's decision.
As such, just for fun, here is a symmetrical solution of 20 moves that uses the same notations as my below ...
9
Got 19 by moving around... might be possible to do better:
4
Found a 19 move solution, but no idea about optimum.
Where the columns are a, b, c, d and rows are 1, 2, 3, 4, starting from bottom left.
4
Found a solution in 20, though I have no idea if it's optimal. One of my assumptions was that "Chess rules apply" meant I had to alternate black and white moves.
4
Postscript: in hindsight I was able to run an exhaustive search with the minimum distance between signs set to 17 km and no restriction on the first sign.
Edit: a revised solution
Some reasoning:
My first solution
1
Edit:
The maximum distance marker I have managed to construct is
Using the following placement of stickers (in bold as suggested).
Progression on the upper bound
Original
I had originally thought I had a solution with distance
Using the following signs
But as Weather Vane correctly pointed out in the comments, I had constructed a new sign using only ...
9
Here's the solution, and a proof of its optimality:
First, an important fact:
Now, analysing the grid:
Constructing the solution:
3
I will start the ball rolling with 36 corners
Top 50 recent answers are included
