New answers tagged combinatorics
1
Heavily based on Trenin's answer (in hexagons and heptagons). I got the final number to be 73. Trenin used one mirrored hexagon twice (the crossed on my image).
Then there is:
Triangles: 8
Quadrilaterals: 16
Pentagons: 23
Hexagons: 21
Septagons: 5
Octagons: 0
Sum = 73
5
EDIT: All solutions up to mirror symmetry, rotation, colour permutation found by brute force:
End of EDIT.
One possibility (I write X,O,+ for 0,1,2):
A bit on how this was found:
2
It feels like this can be improved but the best I've been able to do so far is
As follows
4
Using a modified version of Albert Lang's method on the previous question, the best I've managed so far is
As follows
7
One possible answer is
It doesn't look very symmetric at first glance, but if you look more closely,
I think it's likely that there isn't any answer which does not follow this pattern. I'm pretty sure this property holds for all answers, with the following reasoning:
Let's classify the cells into four categories.
A B C D
C D A B
B A D C
D C B A
And let's ...
1
I finally wrote a heuristic solver that finds good solutions. I found many solutions that achieve the longest chain length of
Here are some example solutions
4
Another proof of Albert's lemma (and one that I believe is much more elegant than the others presented):
I will prove a stronger lemma instead. Namely:
Proof:
(A proof of the reduced statement follows. This proof is similar to Gareth's answer to the same question, but does not rely on an arbitrary choice of "leftmost".)
4
Here's (what I think is) a simpler proof of Albert's lemma than the one in loopy_wall's answer. We'll find either a king-path of 0-squares connecting N and S sides, or a king-path of 1-squares connecting W and E sides. The basic idea is to walk along the boundary between 0-squares and 1-squares until we reach an edge of the board. So here's an example board; ...
3
Proof of Albert's lemma (which solves the bonus question; please note that some repetitive details are omitted to keep down overall length to something reasonable):
1
A "systematic" solution. Bit tedious but no guessing no computer required.
Only 4 cases are serious contenders:
The remaining cases are easily dismissed:
and we recover @hexomino's result
3
My attempt
We can verify this is the best we can do mathematically because
Edit: I just wrote a short program to check this and the following colourings also achieve the same result.
2
Every pair of zeros and every pair of ones are connected via some King chain
is confusing. If you mean that every $1$ can be reached from every other $1$ by the traversal rules (similarly for $0$), then I think 8 is a minimum. If we can have disconnected pairs,
gets you to 7.
As for a proof, there might be fertile ground in looking at what can stop a path (...
0
4
Here is an obviously true but devilishly hard to actually prove lemma from which optimality of
for the bonus question follows:
Lemma:
No proof :-(
Also, alternative solution for the main question:
7
As a first attempt, longest king chain of 8:
As for the bonus,
0
5
(Note: I have treated the question as a classical covering problem, while OP apparently intended that the occupied squares need to be attacked as well. I'm leaving the answer up anyway, since this interpretation yields an interesting puzzle too.)
UPDATE:
Here's the biggest one I got:
It took surprisingly long to fiddle the placements so that everything fit, ...
9
I'll get things started with
Improvement:
7
I can manage to get
Methodology:
20
I used integer linear programming to minimize the number of unattacked squares. Here is one optimal solution (unique up to symmetry), with
5
@RobPratt's answer is correct. Here are the alternative arrangements I've found, all of which are only slightly different from each other.
7
You can solve the problem via integer linear programming as follows. Define a graph with one node per cell and an edge for each pair of cells that are a knight's move away from each other. For node $i\in N$, let $N_i \subset N$ be the neighbors of $i$, and let binary decision variable $x_i$ indicate whether node $i$ is selected. The problem is to minimize ...
6
I think this will work as a solution
1
Here is another solution.
If the center square is a 1, then all four middle-edge squares must be 0; then the four corners can each be 0 or 1 independently, leading to $2^4=16$ configurations.
If the center square is a 0, then we are counting the number of cyclic bitstrings of length 8 with no two consecutive 1s. The number of cyclic bitstrings of length $n$ ...
8
I think I can do it in
How to achieve it:
Now, why is this optimal?
4
I solved this thanks to the help in the comments. There are additional cases given by (up to rotation):
$$\pmatrix{\color{red}{\bullet} & \color{blue}{\bullet} & 0 \\ 0 & 0 & \color{red}{\bullet} \\ \color{blue}{\bullet} & \color{red}{\bullet} & \color{blue}{\bullet}}$$
The only new cases are these (up to rotation and symmetry):
$$\...
1
Same method as for this previous similar question:
How can we do this? For example,
1
Yes.
OXXXX
XXOOO
XOXOO
XOOXO
XOOOX
This extends to any $n \times n$ grid, on which you can paint $3(n - 1)$ cells.
7
The answer to both main and bonus question is given by the following fact:
As follows:
This is the $n=5$ case of the no-three-in-a-line problem (link contains spoilers, obviously). In general, one might ask whether it's always possible to get $2n$ dots on an $n\times n$ grid (the theoretical maximum is $2n$, since each row and column can contain at most 2 ...
4
Alternate solution to @Anonymous' correct solution:
The gray dots represent the 10 dots. This also proves the bonus question of being able to solve it in different ways (non-mirror)
9
I hope this is the solution (I will work for the Bonus Part) :-
1
I'm pretty sure it's:
No proof, though, but a few remarks and a suggestive plot:
2
AMBIGRAMS. Ambigrams are dope. The 6 on this die is a simple one - upside down, it looks like a 9, as a six is wont to do. To get higher than 87, we need more of these.
BEHOLD!
If we add more ambigrams, we can fit more numbers. The first is either a 4 or a 7, and the second a 2 or 3, depending on orientation. So, consider these dice:
[0, 1, 2/3, 4/7, 5, 6/9]...
1
I believe the answer is:
Details:
Edit: Paul Panzer is correct. He should get the tick. Here's a justification:
7
I can cover it with
which can be done like this:
1
Well... Just using my knowledge of binary... I think the answer is:
Because:
Top 50 recent answers are included
