Introduction
Introduction
A friend of mine, along with his son, invented the following interesting puzzle:
Let' s call a stripe a checkered polygon that can be traversed entirely by starting from one of its cells and then moving in only two directions: up or to the right. Several such identical stripes can be inserted into each other, shifting them by the vector (-1, 1). Prove that for any stripe consisting of an even number of cells, there exists an odd k such that if you combine k similar stripes, inserting them sequentially into each other, then the resulting polygon can be divided by grid lines into two congruent parts .
Their solution gives an explicit procedure to find such , but does not guarantee its minimality. My friend’s request to me was to help him find examples of such stripes with small number of cells (say, 6, 8, or 10) that require at least 5 (or 7) copies to have a cut.
k
Constructing and displaying the stripes
Constructing and displaying the stripes
Let’s write a function to construct and display the stripes. We can assume that the first direction is always “up”, and encode each stripe with a pair of integers : the binary representation of encodes moving “up” as 1 and “right” as 0, and is the number of copies (default is 1):
nk
n
k
In[]:=
ClearAll[StripePolygon];StripePolygon[n_Integer,k_Integer]:=Module[{moves=IntegerDigits[n,2]/.{0->{1,0},1->{0,1}},compress},compress[moves_]:=(moves//.{{a:___,{0,b_},{0,c_},d:___}:>{a,{0,b+c},d},{a:___,{b_,0},{c_,0},d:___}:>{a,{b+c,0},d}});{{0,0},Splice@Accumulate@compress@{{0,1},Splice@Flatten[Table[{{-1,0},{0,1}},k-1],1],Splice@moves,Splice@Flatten[Table[{{1,0},{0,-1}},k],1],Splice[-Reverse[moves]]}}];StripePolygon[n_Integer]:=StripePolygon[n,1]
Here is the drawing primitive - we pay extra effort to fill the copies of the original stripe with alternating colors:
In[]:=
ClearAll[DrawStripePolygon];DrawStripePolygon[n_Integer,k_Integer]:=Module[{poly=StripePolygon[n],polyK=StripePolygon[n,k],shade,grid,d=0.2},shade[points_,face_]:={EdgeForm[],FaceForm[face],Polygon[points]};grid[{x1_,x2_},{y1_,y2_}]:={Table[Line[{{x1-d,y},{x2+d,y}}],{y,y1,y2}],Table[Line[{{x,y1-d},{x,y2+d}}],{x,x1,x2}]};Graphics[{Table[shade[poly+Threaded[{-2l,2l}],LightBlue],{l,0,(k-1)/2}],Table[shade[poly+Threaded[{-2l+1,2l-1}],LightYellow],{l,1,k/2}],EdgeForm[{Darker@Gray}],FaceForm[],Polygon[polyK],Thin,EdgeForm[LightGray],grid[MinMax@polyK[[All,1]],MinMax@polyK[[All,2]]]},PlotLabel->StringTemplate["``x``"][n,k]]];DrawStripePolygon[n_Integer]:=DrawStripePolygon[n,1]
Below are the drawings for strip 67 with different number of copies:
In[]:=
IntegerDigits[67,2]GraphicsRow[Table[DrawStripePolygon[67,k],{k,1,7,2}]]
Out[]=
{1,0,0,0,0,1,1}
Out[]=
When analyzing the cuts of different stripes, we can ignore symmetrical stripes such as this, which has an obvious cut going through the center - these stripes are encoded with a binary number that is a palindrome:
n
In[]:=
DrawStripePolygon[FromDigits[{1,1,0,0,0,1,1},2]]
Out[]=
The remaining stripes can be split in congruent pairs, and we can consider only the first stripe of each pair
In[]:=
congruentStripes[base_,n_]:=Module[{b=IntegerDigits[n,2]},Sort@Select[{n,FromDigits[Reverse@b,2],FromDigits[Reverse[b/.{0->1,1->0}],2]},#>=base&]]
In[]:=
stripePairs[n_]:=GatherBy[Select[Range[2^(n-2),2^(n-1)-1],With[{b=IntegerDigits[#,2]},b!=Reverse@b]&],(*selectnonpalindromes*)congruentStripes[2^(n-2),#]&];
Here are some examples of two congruent polygons pairs, 69 and 81, and 70 and 78:
In[]:=
GraphicsRow[Join[DrawStripePolygon/@{69,81},DrawStripePolygon/@{70,78}]]
Out[]=
And of course their copies will also be congruent:
In[]:=
GraphicsRow[Join[DrawStripePolygon[#,3]&/@{69,81},DrawStripePolygon[#,3]&/@{70,78}]]
Out[]=
Here are all the unique non-symmetrical stripes of length 6, 8, and 10:
In[]:=
ClearAll[uniqueStripes]uniqueStripes[n_]:=First/@stripePairs[n]
In[]:=
ClearAll[showGrid]showGrid[lst_,w_:6]:=GraphicsGrid[Partition[lst,UpTo@w],ImageSize->Large]
In[]:=
showGrid[DrawStripePolygon/@uniqueStripes[6]]
Out[]=
In[]:=
showGrid[DrawStripePolygon/@uniqueStripes[8]]
Out[]=
Finding the minimum amount of copies to have a cut
Finding the minimum amount of copies to have a cut
We see that for stripes with 6 cells, 3 copies is always enough:
For 8 and 10 cells, 5 and 7 copies are enough, respectively. Note that needing that many copies is more of an exception: out of 120 unique non-symmetrical stripes with 10 cells, only 8/120 = 6.7% require 7 copies.
And, finally, here are all unique non-symmetrical polygons shown with the minimal number of copies that is required to have a cut:
The bisecting algorithm
The bisecting algorithm
Kimmo Eriksson in his article Splitting a Polygon into Two Congruent Pieces, published in The American Mathematical Monthly, 103:5, 393-400, DOI: 10.1080/00029890.1996.12004758, describes an algorithm to determine if a given polygon can be split in two properly congruent (or mirror congruent) connected pieces.
Stephen Wolfram likes to say that he doesn’t understand something unless he can program it himself (or something along these lines) — this was certainly my experience! While the algorithm is intuitively clear, it leaves some details unspecified, which requires some thinking. Also, it does NOT guarantee to always find all cuts (see an example in Lemma 3). However, we can fix this particular problem for square grid polygons by adding every grid point of those line segments whose two angles sum up to 180° to set S, instead of just mid-points as defined in the paper.
The algorithm works roughly as follows. Define S as a set of all vertices plus all grid points for those line segments whose two angles sum up to 180°. For example, here is an original polygon and the same polygon with all elements of S marked:
At some point the congruent path might go outside of the polygon - in that case, we would need to abort this attempt. If Pb ever goes inside the polygon, continue following Pa until Pb reaches the side of the polygon again - that creates a candidate.
This picture illustrates the case when A = 1 and B = 4; Pb (red line) followed Pa (black line) up to vertex 7, but at this point Pb would need to turn left and it would bring Pb outside of the polygon.
On the other hand, when A = 4 and B = 1, we get a successful attempt, and indeed, the red cut is the one that divides the polygon in two congruent paths.
To check whether the candidate is valid, we can take Pb (the red path), and continue going back to vertex 1 in clockwise direction (i.e., go to 9 10 1), getting path FullPb. Now, build a congruent path FullPa starting from A; if FullPb and FullPa collectively contain all the sides of the polygon and intersect only at the cut, we have a solution.
The mirror cases work similarly, with two changes: (a) when Pa goes clockwise, Pb goes counter-clockwise, and vice versa, and (b) If Pa hits Pb when Pb is already inside the polygon (thus starting the cut), it should continue along that path; otherwise (if Pb still goes along the sides), discard the attempt.
Here is an example where Pa (black line) hits Pb (red line) when it already started to cut the polygon, and so it continues along the cut from 23 10 as opposed to continue 23 22.
CITE THIS NOTEBOOK
CITE THIS NOTEBOOK
Bisecting Square Grid Polygons in Two Congruent Parts
by Victor Kryukov
Wolfram Community, STAFF PICKS, April 25, 2024
https://community.wolfram.com/groups/-/m/t/3164310
by Victor Kryukov
Wolfram Community, STAFF PICKS, April 25, 2024
https://community.wolfram.com/groups/-/m/t/3164310