#bongardproblem — Public Fediverse posts

I think this was one of my best (meta) Bongard problems :-) 🥳

Sub-BP solutions (rules just about the left sides):
1: deleting the circlet closer to the cross, you get the vertices of an equilateral triangle;
2: the vertices of the polygon lay on the line of their axis of symmetry;
3: the cross is on the line of the major axis of the ellipse;
4: at least one circle lays on the center of another circle;
5: the black objects are linearly separable from the empty (stroked) ones;
6: the 3 segments lay on lines that intersect (approximately) in one point;
- - - -
7: the biggest number of points is divisible by the other number;
8: the right figure is the convex hull of the figure on the right;
9: every triangle vertex is outside the other triangle or lays on a side of the other;
10: platonic solids;
11: the two rectangles intersect in 4 points;
12: there are three groups of white pills (ellipses), that are separated by black pills (or by background space).

So the solution to my meta-Bongard problem 47 is: to solve the sub-Bongard problems on the left you need to add one or more imaginary points, segments or lines. While for the problems on the right you can find points, but (I think) you don't need to add primitives.

In mathematics you can find examples of both kinds of problems :-)

See also about auxiliary constructs:
https://en.wikipedia.org/wiki/Auxiliary_line

#bongardproblem #mathpuzzle #puzzle #visualmath

The solutions of the sub-problems (left side / right side):
1: two triangular objects / one rectangular object;
2: some odd prime numbers / some even numbers;
3: big stroked objects / small filled objects;
4: horizontal convex objects / vertical concave objects;
5: open curved lines / closed polygonal chains;
6: polygons with tree dots each inside / ellipses with two dots each inside;
- - - -
7: aligned crosses / unaligned crosses;
8: stroked objects / filled objects;
9: horizontal ellipses / vertical ellipses;
10: cyclic graphs / acyclic graphs;
11: even integers / odd integers;
12: platonic solids / regular polygons.

So for example in the sub-problem of box 1 a solution could be "triangles on the right, rectangles on the left" or "two objects on the left, one object on the right".

So the solution to my meta-Bongard problem 46 is: sub-problems with two solutions in the left boxes, with just one solution in the right boxes.

#bongardproblem #mathpuzzle #puzzle #visualmath

The solutions of the sub-problems (left side / right side):
1: cyclic graphs / acyclic graphs;
2: planar graphs / not planar graphs;
3: open lines / closed lines;
4: stroked figures / filled figures;
5: unknots / knots;
6: cubic graphs / not cubic graphs;
- - - -
7: unit distance graphs / other graphs;
8: Ellipses with horizontal major axis / vertical;
9: regular stroked polygons / irregular ones;
10: star polygons / polygonal compounds;
11: platonic solids / regular polygons;
12: platonic solids / Archimedean solids (Truncated tetrahedron, Truncated cube).

So the solution to my meta-Bongard problem 45 is: topological Bongard problems vs geometrical Bongard problems.

#bongardproblem #mathpuzzle #puzzle #visualmath

Solution to my BP 44: Combinatorics on the left, versus Geometry on the right.

Detailed boxes contents:
1: Number the urns from 1 to u. Line up the indistinguishable balls in a row. Split this row up into u sections by inserting u-1 separators. All balls to the left of the j-th separator and to the right of the (j-1)-st separator (counting from, say, the left end) go into the j-th urn. You now have a row of b+u-1 objects of which b are balls and u-1 are separators. There are C(b+u-1,b) ways to choose the locations for the b balls among the b+u-1 objects. This example: 4 balls (o), 3 urns, 2 separators (|). C(6,4) = C(6,2) = 15 ways;
2: permutations of 4 objects, alternative visualization (as string diagrams);
3: Petersen graph;
4: Cayley table of the symmetric group S_3 (drawn as string diagrams), that is all the compositions of the permutations of 3 items;
5: the 11 bracelets with 2 white, 2 black and 2 grey beads. Five are chiral, so there are 16 necklaces in total. See:
https://en.wikipedia.org/wiki/Necklace_(combinatorics)
6: Young diagrams associated to the (unlabeled) partitions of the positive integer 8. See:
https://en.wikipedia.org/wiki/Integer_partition
https://oeis.org/A000041
- - - -
7: an euclidean construction from Euclid 'Elements':
https://schoolworkhelper.net/euclidean-geometry-math-history/
8: Diagram of a truncated cone, with its radius and height;
9: a shaded tetrakis hexahedron (a Catalan solid);
10: origami crease pattern based on the Circle packing technique. See:
https://abrashiorigami.com/crease-pattern/
11: Koch snowflake, iteration 4;
12: a little square drawn with the turtle geometry (see my Bongard problem n. 36).

#bongardproblem #mathpuzzle #puzzle #visualmath

Solution to my BP 43: the boxes on the left show the successive steps of sorting arrays of integers using one basic version of Merge Sort (you can see the visible halving from the recursion). The boxes on the right show steps of sorting arrays of integers using a non-adaptive Bubble Sort (that's one of the simplest sorting algorithms, with two nested loops plus a test to swap or not two adjacent items).

I've written both Python functions to keep the intermediate steps as simple (readable) as possible. I have created the graphics output using Pillow.

See also:
https://en.wikipedia.org/wiki/Merge_sort

#bongardproblem #mathpuzzle #puzzle #visualmath

For Computer Science lovers this problem should ring a bell :-)

Solution to my BP 42: the boxes on the left show representations of Depth-first searches. In the right boxes of Breadth-first searches.

Creating so much pixel art has taught me how little space and pixels you need to represent things, diagrams and ideas. The representations of maze explorations don't waste any pixel :-)

See also:
https://en.wikipedia.org/wiki/Depth-first_search
https://en.wikipedia.org/wiki/Breadth-first_search

#bongardproblem #mathpuzzle #puzzle #visualmath

Solution to my BP 41: all nonempty boxes contain State diagrams of automata with binary inputs. The states represented with double stroked circles are accepting states. Under the state diagrams there are some of their input strings (words). In the boxes on the left the words are accepted, so they end in accepting states. In the boxes of the right, they don't. '' is the empty word (often represented with a lambda). To spicy things up a bit I have expressed some input words a little more generally using a basic regular expression syntax. So o* means zero or more zero bits, o+ one or more zero bits, and () defines a group of bits.

Lot of fun to create pixel art for this Bongard problem. Computer science lovers should remember this stuff enough :-) I'm still exploring computer science and algorithms in the current batch of problems.

See also:
https://en.wikipedia.org/wiki/Finite-state_machine

#bongardproblem #mathpuzzle #puzzle #visualmath

Solution to my BP 40: all boxes represent elementary 1D cellular automata with a contiguous three-cell neighborhood, so 8 triples of bits are enough to specify the next output bit. This is represented in the upper part of the boxes. Under the line there's a a row of 98 uniformly random bits (P=0.5), and each successive row is a window (no circular) to the next automaton state. The left boxes automata show immediate death (Class 1), boring infinite stable repetitions (Class 2), or chaotic noise (Class 3, like in a random bits generator). The right boxes automata show structures that move and are not fully chaotic nor fully repetitive (Class 4).

If you convert the bits of the output into a 0..255 decimal number, you can identify the automaton with this Wolfram code.

All boxes contents:
1: rule 34 (Class 1 or 2, probably 1);
2: rule 160 (Class 1);
3: rule 126 (Class 3);
4: rule 108 (Class 2);
5: rule 73 (Class 2);
6: rule 15 (Class 1 or 2, probably 1);
- - -
7: rule 110 (Class 4, proved P-complete);
8: rule 54 (Class 4).

To recognize the various classes you need to see the random chaos and the just repetitive structures, the cases as box 5 where the changes get trapped in isolated zones, so information can't travel long distances. And the true class 4 cases where there's a balance between chaos and order, where structures and information can move long distance.

See also:
https://en.wikipedia.org/wiki/Elementary_cellular_automaton

A nice paper on the topic with a strong result:
Neary, Turlough, Damien Woods, "P-completeness of cellular automaton Rule 110." International Colloquium on Automata, Languages, and Programming. 2006:
https://mural.maynoothuniversity.ie/id/eprint/15737/1/DW_P-completeness.pdf

#bongardproblem #mathpuzzle #puzzle #visualmath

If you have studied some computer science (or even taken a look at the CS-Unplugged practical experiments) you probably have recognized the boxes contents at once :-)

Solution to my BP 39: All boxes represent Sorting Networks. The ones in the right boxes are correct, so they sort any permutation of the input values (they are also optimal). The sorting networks in the left boxes have some structural "mistake" or missing comparison, so they don't sort correctly any possible input permutation.

Each one of the wrong networks has a different kind of mistake, and the mistake is based on some standard idea. You can implement a test for the correctness of such small networks in few easy lines of Python code that use the Zero-one principle.

See also:
https://en.wikipedia.org/wiki/Sorting_network
https://bertdobbelaere.github.io/sorting_networks.html

#bongardproblem #mathpuzzle #puzzle #visualmath

One of the most laborious Bongard problems to create (despite I've used ideas and data from two different Twitter/X messages, a Mathstodon message, and a Wikipedia page). Solving it is much faster.

Solution to my BP 38: the boxes represent resistor nets, where all resistors are 1 Ohm. In the boxes on the left between the left and right terminals there are rational approximations, of various precision (like 22/7 and 377/120), of Pi Ohms. The circuits in the right boxes have other total resistance values.

With twelve 1 Ohm resistors the best you can do is 22/7 Ohms.

Ideas from:
https://mathstodon.xyz/@davidphys1/115479833494488141
https://x.com/shapoco/status/1984484578296545646
https://www.wolframcloud.com/obj/81d1cb66-9e1e-4121-ba54-721881fead2b

# Example Python solution for the box 3:
para = lambda *s: 1.0 / sum(1.0 / x for x in s)
ser = lambda *s: sum(s)
a = ser(para(1, 1), 1)
b = para(1, ser(1, 1))
c = ser(b, 1)
d = para(1, 1)
x = ser(1, 1)
r1 = a
r2 = 1
r3 = 1
ra = r2 + r3 + (r2 * r3) / r1
rb = r1 + r3 + (r1 * r3) / r2
rc = r1 + r2 + (r1 * r2) / r3
p = ser(para(rb, c), para(ra, d))
result = ser(x, para(rc, p))
print(result) # 3.1415929

See also:
https://en.wikipedia.org/wiki/Y-%CE%94_transform

#bongardproblem #mathpuzzle #puzzle #visualmath

Solution to my BP 37: the boxes on the left contain seed-texture pairs generated by the "Wave Function Collapse" algorithm. The boxes on the right are similar pairs, but the seed doesn't match.

See also:
https://github.com/mxgmn/WaveFunctionCollapse
https://en.wikipedia.org/wiki/Model_synthesis

#bongardproblem #mathpuzzle #puzzle #visualmath

Detailed contents of the right boxes:
7: similar to the square of box 2 but the image is wrong because at the end the turtle should point north (2 * 3 commands);
8: it could look like the program to draw a fractal tree, but it lacks a function to stop the iteration, so the drawing diverges, and the result looks very different from the image shown;
9: at a first glance the code may look correct to draw an infinite spiral with an infinite loop, but the code doesn't specify that the length of the segments should increase, so the again image is not congruent to the actual result;
10: the code looks correct to draw a Koch snowflake at iteration level 2. But in all other boxes the length of the forward segments are larger (27 instead of 6), so the image result should be much bigger than the one shown.

I have generated the box contents writing Python scripts that use the standard Turtle module. Designing a compact graphical language was fun.

See also:
https://en.wikipedia.org/wiki/Turtle_graphics
https://docs.python.org/3/library/turtle.html

#bongardproblem #mathpuzzle #puzzle #visualmath

Solution to my BP 36: all boxes show examples of the graphical result (output) of running some turtle geometry (a minimal Logo) code/commands. The left boxes show correct graphical results of the underlying code, that sometimes defines subroutines. In each of the right boxes there are errors or inconsistencies.

Detailed contents of the left boxes:
1: the up arrow in the code at the bottom represent the "forward 27" command for the turtle. The other uppercase-Gamma-like symbol represents a "rotate 90" command. At the end the commands don't restore the forward facing direction of the turtle (there are only 7 commands in total), so it's heading on the right;
2: the same, but it defines a subroutine (that's 2 commands long), that gets called 4 times (second row). So now at the end the turtle is heading north;
3: the same, but the rotation angle is different (360 / 5), and the subroutine gets called 5 times;
4: the same again, but the rotation is bigger;
5: drawing of the beginning of a fractal tree, with two subroutines;
6: infinite drawing loop, so the turtle doesn't show up (but the amount of black pixels doesn't change anymore);

#bongardproblem #mathpuzzle #puzzle #visualmath

I'm a little late with this answer today. This problem was easy enough...

Solution to my BP 35: the boxes on the left represent magic squares (with magic constants 15, 34, 18, 34, 34, 34), unlike the boxes on the right (the boxes on the right contain just permutations of the first 9 and 16 integers).

See also:
https://en.wikipedia.org/wiki/Magic_square

#bongardproblem #mathpuzzle #puzzle #visualmath

Solution to my BP 34: the boxes on the left represent good approximations of the minimal solution of the (Euclidean) Travelling salesman problem. The boxes on the left show dots with missing paths, open paths, or very bad approximations of TSP solutions.

The Travelling salesman problem: given a set of cities (points), with known distances between each pairs of them, find the shortest closed path that passes through them all, once each.

See also:
https://en.wikipedia.org/wiki/Travelling_salesman_problem

#bongardproblem #mathpuzzle #puzzle #visualmath