B Geometry Puzzle with 20 points in a cross pattern

[bob012345]

TL;DR Summary

Geometry puzzle with 20 points in a cross pattern.

Given the following pattern of points, it is easy to find the number of squares that can be formed with the points as corners. The question is to find the minimum number $n$ of points you can remove such that no squares can be formed among the remaining points. Extra credit is to find how many sets of $n$ points there are. This puzzle is adapted from the book

100 Geometric Games (Dover Math Games & Puzzles)​

by Pierre Berloquin

 

[.Scott]

There are 20 points that I have lettered across the rows then down the columns from "a" to "t".
Thus ...
"a" is at x=2, y=5; "b" is at x=3, y=5; ...
"s" is at x=2, y=0; "t" is at x=3, y=0;

I will not claim to have found the minimum number but:

Spoiler

I have found several cases where eliminating 7 point kills all of the squares.
For example: Eliminating "aeghlor" will do it. So will "bdgikmq" or "afglors".
However, in all cases, after eliminating 4 or 5 points, the remaining points are spread thinly among the remaining squares - so I suspect that it can be optimized to just 6.

BTW: the full 20 points yields 21 squares as follows: 9 with area 1; 4 with area 2; 4 with area 8; 2 with area 5; and 2 with area 13.

 

[FactChecker]

Does this do it with 6? (I hope I didn't overlook something obvious.)

Spoiler: Solution with 6?

 

[bob012345]

Does this do it with 6? (I hope I didn't overlook something obvious.)

Spoiler

Yes, the minimum number of points to remove is six points. Now, if you’re interested, how many sets of six points are there?

[EDIT] I also like your graphic use of @.Scott ’s labeling system.

 

[DaveE]

Symmetry again. I think 5.



Note that because of the cross shape, there are no big squares.

 

[FactChecker]

Symmetry again. I think 5.


View attachment 361917

I see 3 squares remaining. With the labeling established by @.Scott, they are ajtk, bpse, and doqf.

 

[DaveE]

I see 3 squares remaining. With the labeling established by @.Scott, they are ajtk, bpse, and doqf.

Yes! There are big squares, thanks!

 

[anuttarasammyak]

I see 3 squares remaining. With the labeling established by @.Scott, they are ajtk, bpse, and doqf.

By deleting three points these aquares vanish, so 8 is enough.

By changig an original deleting point

Two more points deletion so 7 is enough though it might not be least.

 

[FactChecker]

View attachment 361919
By deleting three points these aquares vanish, so 8 is enough.

By changig an original deleting point
View attachment 361920
Two more points deletion so 7 is enough though it might not be least.

I think I found a solution with 6 in post #3.

 

[anuttarasammyak]

RE:#8
One more change of deleting point

One more deleting a point on the square, six in all as ansered in post #3.

 

[bob012345]

There are 20 points that I have lettered across the rows then down the columns from "a" to "t".
Thus ...
"a" is at x=2, y=5; "b" is at x=3, y=5; ...
"s" is at x=2, y=0; "t" is at x=3, y=0;

I like your labeling system. It’s very efficient!

 

[.Scott]

I have the full answer:

Spoiler

There are fundamentally two solutions:
April Fog (aprfog) as reported by @FactChecker ; and April Function (aprfnc)

Correction: If you mirror aprfog across the 0,0 5,5 axis, you will get aprfnc.

So there is only one fundamental solution.
It can be rotated 0, 90, 180, or 270 degrees and mirrored - for a total of 8 variants.
So, total number of solutions (including variants): 8.

 

[bob012345]

I have the full answer:

Here is my solution.

Spoiler

The solution aprfnc is a reflection plus a rotation of aprfog. I got only half as many solutions as you indicated. I took arpfog and reflected it about the y axis, the x axis and both to get four figures. Then I rotated all four 90 degrees around the z axis to get four more for a total of 8 figures. The z axis figures are identical to arpfnc and its reflections. I found all other rotations or reflections gave the same figures. I connected the remaining dots for clarity to see the symmetries.

[/spoiler

 

[.Scott]

.

Here is my solution.

Spoiler

The solution aprfnc is a reflection plus a rotation of aprfog. I got only half as many solutions as you indicated. I took arpfog and reflected it about the y axis, the x axis and both to get four figures. Then I rotated all four 90 degrees around the z axis to get four more for a total of 8 figures. The z axis figures are identical to arpfnc and its reflections. I found all other rotations or reflections gave the same figures. I connected the remaining dots for clarity to see the symmetries.

Just for the record: I posted my correction 3 minutes before you posted it.

Spoiler

The "April Fog" and "April Function" actually assisted me in discovering the error. I do a 2-hour walk every night, and those mnemonics helped me in reconstructing the problem during my walk. Basically, the pairs a/p, r/f, o/c, and n/g all reflect along the same axis.

 

[FactChecker]

I got one solution with a (sort of) heuristics. But I don't see a good, reliable way to solve it.
And verifying a solution seems to be a brute-force, exhaustive search for squares.
Are there smarter ways?

 

[Gavran]

I got one solution with a (sort of) heuristics. But I don't see a good, reliable way to solve it.
And verifying a solution seems to be a brute-force, exhaustive search for squares.
Are there smarter ways?

You can label 21 squares with 21 different labels and after that you can join every point with particular labels, depending on belonging to particular squares. When you discard a point you discard every square which contains that point which is visible through labels joint with that point.

 

[anuttarasammyak]

I got one solution with a (sort of) heuristics. But I don't see a good, reliable way to solve it.
And verifying a solution seems to be a brute-force, exhaustive search for squares.
Are there smarter ways?

The way found seems smart enough to me. The 9 unit squares configuration require 5 missing points at least so that no unit squares are formed. Then we can choose these five points so that larger squares vanish as post #5, #8 and #10 which reveals that one more point is necessary.

 

[.Scott]

I got one solution with a (sort of) heuristics. But I don't see a good, reliable way to solve it.
And verifying a solution seems to be a brute-force, exhaustive search for squares.
Are there smarter ways?

I went with brute force - using JavaScript - which really isn't that much of a brute.

The four large squares do not share any points in common. So the first four points selected cover those four squares. The first point on the first square is taken as point "a" - since the other three possibilities will be handled by rotations from anything we find. Each of the next three points is one of 4, so after four points, you have only 64 possibilities. Then I sorted the remaining points (all 16) in descending order by the number of remaining squares they supported. I looked at the two highest scoring points and added up their square counts. If it was less that the number of remaining squares, I dropped that possibility. Finally, I considered all points in that sorted list with scores high enough to cover half the remaining squares - and printed (ie, console.log) a report on each one.
That gave me my final answer(s). The duplicate was because there really aren't 64 possible fundamental solutions after the first 4 points are selected - there are only 32.

 

[anuttarasammyak]

there are only 32.

Fighre in post #10 shows that there are four choices of the sixth missing point. WIth x- inversion, y- inversion and xy-inversion the number of patterns is
4 \times 2 \times 2 \times 2 = 32

[edit]xy-exchange, not -inversion.

 

[.Scott]

Fighre in post #10 shows four choice of the sixth missing point. WIth x- inversion, y- inversion and xy-inversion the number of patterns is
4 \times 2 \times 2 \times 2 = 32

My "32" was the number of fundamental combinations after choosing the first 4 of the 6 points, each from one of the 4 largest squares. So, it's four to the fourth power (one point from each of the four squares) divided by 8 (the number of rotation/mirror combinations). So, 4^4/8 = 32.

It didn't occur to me to use that small middle square ("ghmn") as a fifth. Since it shares no points with first four squares, it would have qualified - and it would have simplified the algorithm.

 

[anuttarasammyak]

If the different thoughts take us to the same answer, we are happy.

 

[bob012345]

You can label 21 squares with 21 different labels and after that you can join every point with particular labels, depending on belonging to particular squares. When you discard a point you discard every square which contains that point which is visible through labels joint with that point.

I did that graphically but still it was too unwieldy to quickly get an answer. I tried asking Google Gemini to find the six point sets that eliminated all the squares but it choked.

 

[Gavran]

I did that graphically but still it was too unwieldy to quickly get an answer. I tried asking Google Gemini to find the six point sets that eliminated all the squares but it choked.

If you apply my approach you will see that all this thread is about the set cover problem which can be solved by using one of the algorithms. For example, it can be solved by using a greedy algorithm.

The set cover problem is a part of combinatorics, computer science, operation research and complexity theory. The set cover problem is to identify a smallest number of sets of a given m sets in the way that the union of these identified sets contains all the elements that are contained in the given m sets. The set which contains all the elements that are contained in the given m sets is called the universe.

$\begin{array} \\ & & S_{1} & S_{2} & & \\ & & S_{3} & S_{4} & & \\ S_{5} & S_{6} & S_{7} & S_{8} & S_{9} & S_{10} \\ S_{11} & S_{12} & S_{13} & S_{14} & S_{15} & S_{16} \\ & & S_{17} & S_{18} & & \\ & & S_{19} & S_{20} & & \\ \end{array} \,\,\,\, \Leftrightarrow \,\,\,\, \begin{array} \\ & & \{f,n,u\} & \{f,p,t\} & & \\ & & \{f,g,j,o,s\} & \{f,g,l,q,r\} & & \\ \{a,n,t\} & \{a,b,j,p,r\} & \{b,c,g,k,l\} & \{c,d,g,j,m\} & \{d,e,l,n,s\} & \{e,p,u\} \\ \{a,o,u\} & \{a,b,k,q,s\} & \{b,c,h,j,m\} & \{c,d,h,k,l\} & \{d,e,m,o,r\} & \{e,q,t\} \\ & & \{h,i,k,n,r\} & \{h,i,m,p,s\} & & \\ & & \{i,o,t\} & \{i,q,u\} & & \\ \end{array}$

The 20 points are the 20 sets $S_{1}$, $S_{2}$, $S_{3}$, $S_{4}$, $S_{5}$, $S_{6}$, $S_{7}$, $S_{8}$, $S_{9}$, $S_{10}$, $S_{11}$, $S_{12}$, $S_{13}$, $S_{14}$, $S_{15}$, $S_{16}$, $S_{17}$, $S_{18}$, $S_{19}$ and $S_{20}$. The 21 squares are the 21 elements $a$, $b$, $c$, $d$, $e$, $f$, $g$, $h$, $i$, $j$, $k$, $l$, $m$, $n$, $o$, $p$, $q$, $r$, $s$, $t$ and $u$. The universe is $U=\{a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u\}$.
The problem is to pick a smallest sub-collection of the collection of the given 20 sets where the union of the sets from the picked sub-collection is equal to the universe.

 

[PeroK]

It can be done with 6 points. We have to show it can't be done with 5 points.

If we take each square as a line, then we would need to find a set of 5 points that intersects every line. As every line has 4 points, this can only be done if we can find 5 lines that cover all 20 points. We would, therefore, need 5 mutually disjoint lines.

Is it difficult to show that no such set of 5 lines can be found?

PS there appear to be three ways to cover all 20 points with 5 lines. This idea didn't help as much as I'd hoped, as it still leaves a lot to be checked.

 

[bob012345]

If you apply my approach you will see that all this thread is about the set cover problem which can be solved by using one of the algorithms. For example, it can be solved by using a greedy algorithm.

The set cover problem is a part of combinatorics, computer science, operation research and complexity theory. The set cover problem is to identify a smallest number of sets of a given m sets in the way that the union of these identified sets contains all the elements that are contained in the given m sets. The set which contains all the elements that are contained in the given m sets is called the universe.

$\begin{array} \\ & & S_{1} & S_{2} & & \\ & & S_{3} & S_{4} & & \\ S_{5} & S_{6} & S_{7} & S_{8} & S_{9} & S_{10} \\ S_{11} & S_{12} & S_{13} & S_{14} & S_{15} & S_{16} \\ & & S_{17} & S_{18} & & \\ & & S_{19} & S_{20} & & \\ \end{array} \,\,\,\, \Leftrightarrow \,\,\,\, \begin{array} \\ & & \{f,n,u\} & \{f,p,t\} & & \\ & & \{f,g,j,o,s\} & \{f,g,l,q,r\} & & \\ \{a,n,t\} & \{a,b,j,p,r\} & \{b,c,g,k,l\} & \{c,d,g,j,m\} & \{d,e,l,n,s\} & \{e,p,u\} \\ \{a,o,u\} & \{a,b,k,q,s\} & \{b,c,h,j,m\} & \{c,d,h,k,l\} & \{d,e,m,o,r\} & \{e,q,t\} \\ & & \{h,i,k,n,r\} & \{h,i,m,p,s\} & & \\ & & \{i,o,t\} & \{i,q,u\} & & \\ \end{array}$

The 20 points are the 20 sets $S_{1}$, $S_{2}$, $S_{3}$, $S_{4}$, $S_{5}$, $S_{6}$, $S_{7}$, $S_{8}$, $S_{9}$, $S_{10}$, $S_{11}$, $S_{12}$, $S_{13}$, $S_{14}$, $S_{15}$, $S_{16}$, $S_{17}$, $S_{18}$, $S_{19}$ and $S_{20}$. The 21 squares are the 21 elements $a$, $b$, $c$, $d$, $e$, $f$, $g$, $h$, $i$, $j$, $k$, $l$, $m$, $n$, $o$, $p$, $q$, $r$, $s$, $t$ and $u$. The universe is $U=\{a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u\}$.
The problem is to pick a smallest sub-collection of the collection of the given 20 sets where the union of the sets from the picked sub-collection is equal to the universe.

That’s exactly what I did but manually with graphics. I tried to put it in Wolfram Alpha but it was too long of an input.

 

[FactChecker]

This idea didn't help as much as I'd hoped, as it still leaves a lot to be checked.

I get stopped at manually finding the list of all possible squares and knowing that none were missed.

 

[anuttarasammyak]

It can be done with 6 points. We have to show it can't be done with 5 points.

Say five points are enough. Taking a look at the largest squares shown in the second figure of post #8, we know that two points be chosen from the outest eight. Deleting all the unit squares in mind, the two points cannot be on the same unit square or on the opposite. 90 degree neighbor case as one shown below should be investigated. With two more points which should delete remaining unit squares, we cannot delete the square shown in the figure.

 

[bob012345]

In order to show that 5 points cannot work, I also used the outer two squares and two squares surrounding the central four points. Since every possible solution to eliminate all squares must have at least one point missing from each of these squares giving 64 possibilities only for the permutations of the four points. I drew them all and found none that didn’t have at least one square remaining after removing one point.

Spoiler: “data”

 

[Gavran]

That’s exactly what I did but manually with graphics. I tried to put it in Wolfram Alpha but it was too long of an input.

The problem in the original post can be transformed into the set cover problem, but it still can only be solved by heuristics. Try the online tool https://www.tutorialspoint.com/data_structures_algorithms/dsa_set_cover_problem.htm (Python tab at the end of the page).

Replace
X=[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
with
X=[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21]
and replace
S = [
{1, 2},
{2, 3, 4},
{4, 5, 6},
{6, 7, 8},
{8, 9, 10}
]
with
S = [
{6, 14, 21},
{6, 16, 20},
{6, 7, 10, 15, 19},
{6, 7, 12, 17, 18},
{1, 14, 20},
{1, 2, 10, 16, 18},
{2, 3, 7, 11, 12},
{3, 4, 7, 10, 13},
{4, 5, 12, 14, 19},
{5, 16, 21},
{1, 15, 21},
{1, 2, 11, 17, 19},
{2, 3, 8, 10, 13},
{3, 4, 8, 11, 12},
{4, 5, 13, 15, 18},
{5, 17, 20},
{8, 9, 11, 14, 18},
{8, 9, 13, 16, 19},
{9, 15, 20},
{9, 17, 21}
]

The application gives only one solution. By changing the order of sets in S you can get more than one solution and this can be exhausting.

 

[Gavran]

In order to show that 5 points cannot work, I also used the outer two squares and two squares surrounding the central four points. Since every possible solution to eliminate all squares must have at least one point missing from each of these squares giving 64 possibilities only for the permutations of the four points.

I do not understand your statement.
There are four squares and every square has four points. Every option must have at least one point from each of these four squares. That means there are $$ \binom{4}{1}\cdot\binom{4}{1}\cdot\binom{4}{1}\cdot\binom{4}{1}=4\cdot4\cdot4\cdot4=256 $$ different options which include one point from each of the four squares. If you exclude mirror and rotation options there will be $256/8=32$ possibilities (the post #20).

 

[bob012345]

I do not understand your statement.
There are four squares and every square has four points. Every option must have at least one point from each of these four squares. That means there are $$ \binom{4}{1}\cdot\binom{4}{1}\cdot\binom{4}{1}\cdot\binom{4}{1}=4\cdot4\cdot4\cdot4=256 $$ different options which include one point from each of the four squares. If you exclude mirror and rotation options there will be $256/8=32$ possibilities (the post #20).

If I remember, that was so two weeks ago, probably what I meant by the permutations, was the relative rotations of the squares with missing points which was quicker and easier than checking for mirroring cases first. My 64 drawings include the mirrored cases.

 

[Gavran]

If I remember, that was so two weeks ago, probably what I meant by the permutations, was the relative rotations of the squares with missing points which was quicker and easier than checking for mirroring cases first. My 64 drawings include the mirrored cases.

Okay.