RobPratt
  • Member for 1 year, 10 months
  • Last seen this week
3 answers
votes
701 views
The farmer and the olive trees
7 votes

As in my answer to My Mother's Dish Collection, I used a nonlinear optimization solver, with variables $x_i$, $y_i$ to represent the coordinates of the trees. The constraints are: \begin{align} 0 \le ...

View answer
3 answers
votes
329 views
Filling a grid with skinny trominoes which have arrows on their ends
Accepted answer
6 votes

The maximum is 1 2 2 3 3 . 4 4 5 5 1 1 2 3 6 6 . 4 5 7 8 8 . 9 6 10 10 . 7 7 8 11 12 9 9 10 13 14 15 15 11 11 12 12 . 13 13 14 14 15 16 16 17 17 18 19 20 20 21 ...

View answer
2 answers
votes
587 views
Adding coins inside a ring of coins
6 votes

I'll get things started with

View answer
2 answers
votes
130 views
Numbers side by side
Accepted answer
6 votes

View answer
1 answers
votes
205 views
Create the freest arrangement of white chess pieces on board by consequently moving your pieces
Accepted answer
6 votes

I used integer linear programming as follows. Let $P$ be the set of pieces, with number $n_p$ of pieces available: $n_\text{king}=1, n_\text{bishop}=n_\text{knight}=n_\text{rook}=2, n_\text{queen}=9$....

View answer
1 answers
votes
214 views
My High School's Reunion
Accepted answer
5 votes

If the number of people per table is $p$, then to cover each pair we must have $$\frac{600}{p} \binom{p}{2} \ge \binom{30}{2},$$ which implies that $p \ge \lceil 49/20 \rceil = 3$. The following set ...

View answer
4 answers
votes
761 views
Words with a letter sound at the start but not the letter
5 votes

View answer
3 answers
votes
289 views
The vaccine distribution conundrum
Accepted answer
5 votes

You are looking for a partition of $40$ with the minimum number of parts that is a common refinement of all $154$ partitions of $40$ into at most $3$ parts. You can satisfy all $154$ scenarios with ...

View answer
4 answers
votes
646 views
How many rolls on average to get N dice to all show the same value?
5 votes

Here are results for small $n$: \begin{matrix} n & \text{minimum expected number of rolls} \\ \hline 1 & 1 \\ 2 & 6 \\ 3 & 63/8 = 7.875 \\ 4 & 1388/143 \approx 9.706 \\ 5 & ...

View answer
1 answers
votes
292 views
New maths puzzle
Accepted answer
5 votes

Here's the unique solution, obtained via integer linear programming:

View answer
4 answers
votes
854 views
Knights in a Complete Sudoku Board
5 votes

Still trying various integer linear programming formulations. Along the way, I found that if you ignore the sudoku constraints, you can fit 9 knight paths. Not an answer, but I wanted to share the ...

View answer
3 answers
votes
241 views
4-coloured queens attacking every opponent queen once
5 votes

You asked for 6 queens, but the maximum is at least

View answer
4 answers
votes
350 views
3 Colors of Chess Pieces Attacking Each Other Once Each
5 votes

Via integer linear programming, the maximum for knights is The maximum for queens is at least Other maxima are

View answer
4 answers
votes
391 views
Chess pieces attacking exactly N chess pieces
5 votes

For kings, $N=1$ yields a maximum of

View answer
5 answers
votes
499 views
Find the most unfortunate compact combination of coins to have in LOLandia
4 votes

The maximum number of coins is with a minimum total value of achieved by The integer linear programming solution approach I used might be of interest. Let nonnegative integer decision variable $...

View answer
2 answers
votes
611 views
A school needs a talented student (covering the hamming graph H(3,15) with closed balls of radius 5)
Accepted answer
4 votes

The upper bound for $K_3(13,3)$ here yields This guarantees $10$ correct out of the first $13$ questions, so we can surely do better by considering all $15$ questions. A lower bound is the sphere ...

View answer
1 answers
votes
79 views
A 4x6 grid with adjacent integers with gcd > 1
Accepted answer
4 votes

Another solution, with smallest possible maximum entry subject to minimizing the sum: If you ignore the sum, the smallest possible maximum entry is smaller by $1$:

View answer
1 answers
votes
226 views
Three white queens, two white knights, and one rook on a chess board
4 votes

I used integer linear programming (and, sorry, a computer): The solution is unique up to rotation and reflection.

View answer
1 answers
votes
112 views
How many queens are needed to attack all white squares?
Accepted answer
4 votes

The minimum is

View answer
4 answers
votes
215 views
The Greenhouse Problem version 2
Accepted answer
4 votes

Here's a symmetric solution with

View answer
1 answers
votes
171 views
Visiting streets, not houses
Accepted answer
4 votes

There are 52 edges, so that is a lower bound. There are six odd-degree nodes. If you choose the two middle ones to be the endpoints of the overall path, the other four can be paired up with distance ...

View answer
4 answers
votes
2k views
fill this grid with water!
4 votes

You can solve the problem via integer linear programming as follows. Let $N=\{1,\dots,12\}$, and let $r_i$ and $c_j$ be the required row and column sums, respectively. For $(i,j)\in N \times N$, let ...

View answer
3 answers
votes
670 views
1000 gold coins to share with the knight
4 votes

You can solve the problem via integer linear programming as follows. Let $n$ be the number of coins, and let $k$ be the number of extra coins the knight can use. For $b \in \{1,\dots,n\}$, let ...

View answer
4 answers
votes
506 views
Reconstructing points based on the sum of their coordinates version 2
4 votes

I confirm @AlexeyBurdin's count of 470 solutions, which I obtained via integer linear programming as follows. Let $S=\{2, 4, 5, 6, 7, 8, 10, 11, 12, 13\}$ be the set of desired sums. Let binary ...

View answer
1 answers
votes
132 views
Competitive puzzles
4 votes

Al Zimmermann's Programming Contests match this description. The name includes "programming" but does not require it: You can enter whether you use a computer, manual calculations, or tea ...

View answer
3 answers
votes
320 views
What is the minimum count of steps required to complete this dominoes maze?
Accepted answer
4 votes

Indeed it can be solved as a traveling salesman problem on 13 nodes, but brute force is not required. First define an undirected graph with 145 nodes, one per box, with an edge between each pair of ...

View answer
1 answers
votes
166 views
What's the graph relation? #1
Accepted answer
4 votes

View answer
2 answers
vote
326 views
Scheduling Meetings
Accepted answer
3 votes

Via mixed integer linear programming, I found a solution that uses $76$ meetings and has a total waste of $4230 + 1900 + 45 = 6175$: 1 : 1516 3432 2 : 303 363 2339 3120 3400 3 : 4134 4 : 476 836 1567 ...

View answer
4 answers
votes
399 views
How to get the least number of flips to a plastic chips to get a certain figure?
3 votes

You can solve the problem via a system of eight linear equations, one per chip, with eight binary variables, one per possible movement. The order of operations doesn’t matter, and there is no reason ...

View answer
2 answers
votes
199 views
Maximum number of kings that can exit
3 votes

Via integer linear programming, I found a solution that uses and all such kings can exit in Initial configuration: Covered squares: Animation:

View answer