{VERSION 2 3 "IBM INTEL NT" "2.3" } {USTYLETAB {CSTYLE "Maple Input" -1 0 "Courier" 0 1 255 0 0 1 0 1 0 0 1 0 0 0 0 }{CSTYLE "2D Math" -1 2 "Times" 0 1 0 0 0 0 0 0 2 0 0 0 0 0 0 }{CSTYLE "2D Comment" 2 18 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 } {CSTYLE "2D Output" 2 20 "" 0 1 0 0 255 1 0 0 0 0 0 0 0 0 0 }{CSTYLE " " -1 256 "" 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 }{PSTYLE "Normal" -1 0 1 {CSTYLE "" -1 -1 "Times" 0 12 0 0 0 1 2 2 2 0 0 0 0 0 0 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "Heading 1" 0 3 1 {CSTYLE "" -1 -1 "" 1 18 0 0 0 0 0 1 0 0 0 0 0 0 0 }1 0 0 0 6 6 0 0 0 0 0 0 -1 0 }{PSTYLE "M aple Output" 0 11 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 }3 3 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "Maple Plot" 0 13 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 }3 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "R3 Font 0" -1 256 1 {CSTYLE "" -1 -1 "Courier" 1 18 0 0 0 0 2 1 2 0 0 0 0 0 0 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "R3 \+ Font 2" -1 257 1 {CSTYLE "" -1 -1 "Lucidabright" 1 19 0 0 0 0 1 1 2 0 0 0 0 0 0 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "R3 Font 3" -1 258 1 {CSTYLE "" -1 -1 "Lucida" 1 14 0 0 0 0 1 1 2 0 0 0 0 0 0 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "R3 Font 4" -1 259 1 {CSTYLE "" -1 -1 "Lucida" 1 14 0 0 0 0 1 1 2 0 0 0 0 0 0 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "R3 Font 5" -1 260 1 {CSTYLE "" -1 -1 "Lucida" 1 14 0 0 0 0 1 1 2 0 0 0 0 0 0 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "R3 \+ Font 6" -1 261 1 {CSTYLE "" -1 -1 "Lucida" 1 14 0 0 0 0 1 1 2 0 0 0 0 0 0 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "R3 Font 7" -1 262 1 {CSTYLE "" -1 -1 "Charter" 1 18 0 0 0 0 1 2 2 0 0 0 0 0 0 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "R3 Font 8" -1 263 1 {CSTYLE "" -1 -1 "Charter" 1 18 0 0 0 0 1 2 2 0 0 0 0 0 0 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "R3 Font 9" -1 264 1 {CSTYLE "" -1 -1 "Charter" 1 18 0 0 0 0 1 2 2 0 0 0 0 0 0 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "R3 \+ Font 10" -1 265 1 {CSTYLE "" -1 -1 "Charter" 1 18 0 0 0 0 1 2 2 0 0 0 0 0 0 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "R3 Font 11" -1 266 1 {CSTYLE "" -1 -1 "Charter" 1 18 0 0 0 0 1 2 2 0 0 0 0 0 0 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "R3 Font 12" -1 267 1 {CSTYLE "" -1 -1 "Lucida" 1 14 0 0 0 0 1 1 2 0 0 0 0 0 0 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "R3 Font 13" -1 268 1 {CSTYLE "" -1 -1 "Lucida" 1 14 0 0 0 0 1 1 2 0 0 0 0 0 0 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "R 3 Font 14" -1 269 1 {CSTYLE "" -1 -1 "Lucida" 1 14 0 0 0 0 1 1 2 0 0 0 0 0 0 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "R3 Font 15" -1 270 1 {CSTYLE "" -1 -1 "Lucida" 1 14 0 0 0 0 1 1 2 0 0 0 0 0 0 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "R3 Font 16" -1 271 1 {CSTYLE "" -1 -1 "Courier" 1 14 0 0 0 0 1 1 2 0 0 0 0 0 0 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "R3 Font 17" -1 272 1 {CSTYLE "" -1 -1 "Courier" 1 14 0 0 0 0 1 1 2 0 0 0 0 0 0 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "R 3 Font 18" -1 273 1 {CSTYLE "" -1 -1 "Courier" 1 14 0 0 0 0 1 1 2 0 0 0 0 0 0 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "R3 Font 19" -1 274 1 {CSTYLE "" -1 -1 "Courier" 1 14 0 0 0 0 1 1 2 0 0 0 0 0 0 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "R3 Font 20" -1 275 1 {CSTYLE "" -1 -1 "Courier" 1 14 0 0 0 0 1 1 2 0 0 0 0 0 0 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "R3 Font 21" -1 276 1 {CSTYLE "" -1 -1 "Lucidatypewrit er" 1 14 0 0 0 0 2 1 2 0 0 0 0 0 0 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 } {PSTYLE "R3 Font 22" -1 277 1 {CSTYLE "" -1 -1 "Lucidatypewriter" 1 14 0 0 0 0 2 1 2 0 0 0 0 0 0 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 } {PSTYLE "R3 Font 23" -1 278 1 {CSTYLE "" -1 -1 "Lucidatypewriter" 1 14 0 0 0 0 2 1 2 0 0 0 0 0 0 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 } {PSTYLE "R3 Font 24" -1 279 1 {CSTYLE "" -1 -1 "Lucidatypewriter" 1 14 0 0 0 0 2 1 2 0 0 0 0 0 0 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 } {PSTYLE "R3 Font 25" -1 280 1 {CSTYLE "" -1 -1 "Lucidatypewriter" 1 14 0 0 0 0 2 1 2 0 0 0 0 0 0 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 } {PSTYLE "R3 Font 26" -1 281 1 {CSTYLE "" -1 -1 "Lucidatypewriter" 1 14 0 0 0 0 2 1 2 0 0 0 0 0 0 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 } {PSTYLE "R3 Font 27" -1 282 1 {CSTYLE "" -1 -1 "Lucidatypewriter" 1 14 0 0 0 0 2 1 2 0 0 0 0 0 0 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 } {PSTYLE "R3 Font 28" -1 283 1 {CSTYLE "" -1 -1 "Lucidatypewriter" 1 14 0 0 0 0 2 1 2 0 0 0 0 0 0 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 } {PSTYLE "R3 Font 0" -1 284 1 {CSTYLE "" -1 -1 "Helvetica" 0 12 255 0 0 1 2 1 2 0 0 0 0 0 0 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "R3 Fo nt 2" -1 285 1 {CSTYLE "" -1 -1 "Courier" 0 12 0 0 0 1 2 2 2 0 0 0 0 0 0 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "R3 Font 0" -1 286 1 {CSTYLE "" -1 -1 "Lucidatypewriter" 1 19 0 0 0 0 2 2 2 0 0 0 0 0 0 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "R3 Font 2" -1 287 1 {CSTYLE " " -1 -1 "Lucidatypewriter" 1 18 0 0 0 0 2 2 2 0 0 0 0 0 0 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "" 3 289 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 }3 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }} {SECT 0 {EXCHG {PARA 289 "" 0 "" {TEXT 256 33 "Tiling with the simplex algorithm" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 130 "Suppose we have tw o tiles, f and g, and wish to tile a region F. This is equivalent to f inding two polynomials A and B such that " }{XPPEDIT 18 0 "F = Af + B g" "/%\"FG,&%#AfG\"\"\"%#BgGF&" }{TEXT -1 57 " where the coefficients \+ of A and B are all 1. " }{MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 8 "restart;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 117 "rect := proc(n,m)\nlocal i,j;\n expand(\n \+ sum(x^'i','i' = 0 .. m-1) \n * sum(y^'j','j' = 0 .. n-1))\nend: \n" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 22 "Now we need some tiles" }} {PARA 0 "> " 0 "" {MPLTEXT 1 0 42 "tile1:=1+x+x^2+y:\ntile2:=y+x*y+x^2 *y+x^2 :" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 34 "Now choose a polynomi al region f.\n" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 16 " f:= rect(4,4); \+ " }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 45 "We need a word to convert f t o a linear form." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 15 " cnv := proc(f)" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 19 " local tmp,tf,i,j;" }} {PARA 0 "> " 0 "" {MPLTEXT 1 0 13 " tmp :=NULL;" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 36 " tf := collect(simplify(f),[x,y]);" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 35 " for i from 0 to degree(tf,x) do" }}{PARA 0 " > " 0 "" {MPLTEXT 1 0 37 " for j from 0 to degree(tf,y) do" }} {PARA 0 "> " 0 "" {MPLTEXT 1 0 40 " if not coeff(coeff(tf,x,i),y ,j)=0" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 11 " then" }}{PARA 0 "> \+ " 0 "" {MPLTEXT 1 0 46 " tmp := tmp,coeff(coeff(tf,x,i),y,j)*z[i,j]; " }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 9 " fi" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 7 " od" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 6 " od;" } }{PARA 0 "> " 0 "" {MPLTEXT 1 0 20 " convert([tmp],`+`);" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 5 "end: " }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 9 "cnv(f); " }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 42 "This word will \+ be used to draw the tiling." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 19 " squares := proc(f)" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 19 " local \+ tmp,tf,i,j;" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 13 " tmp :=NULL;" }} {PARA 0 "> " 0 "" {MPLTEXT 1 0 36 " tf := collect(simplify(f),[x,y]) ;" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 35 " for i from 0 to degree(tf, x) do" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 37 " for j from 0 to degr ee(tf,y) do" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 38 " if 0 < coeff( coeff(tf,x,i),y,j)" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 11 " then" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 78 " tmp := tmp, [[i+.1,j+.1], [i+1-.1,j+.1],[i+1-.1,j+1-.1],[i+.1,j+1-.1]];" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 9 " fi" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 7 " od " }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 6 " od;" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 11 " [tmp]end: " }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 93 "Here is the word to sear ch for a solution using the simplex algorithm. The idea is simple: \+ " }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "> \+ " 0 "" {MPLTEXT 1 0 195 "tileit := proc(f,tile1,tile2)\n local A, B,i, a,b, gf, p,eqns, sol, sln1, sln2, drawing ;\nA := convert([seq(a[i-1]* op(i,f),i=1..nops(f))],`+`);\nB := convert([seq(b[i-1]*op(i,f),i=1..no ps(f))],`+`);" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 43 " gf := cnv(expand (A*tile1+tile2*B -f)) ;" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 46 " eqns: =seq(op(1,op(i,gf))=0 ,i=1..nops(gf)); " }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 45 "sol:=simplex[maximize](1,[eqns],NONNEGATIVE);" }} {PARA 0 "" 0 "" {TEXT -1 1 " " }{MPLTEXT 1 0 121 "if not sol=\{\} then \nsln1 := expand(subs(sol,A));\nsln2 := expand(subs(sol,B));\n dra wing := NULL;\n if not sln1 = 0 then" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 122 "drawing := drawing,seq(plots[polygonplot](squares(expand(\n ti le1*p)),color=tan) ,p=[op(sln1 )]) fi;\nif not sln2 = 0 then" }} {PARA 0 "> " 0 "" {MPLTEXT 1 0 101 "drawing:= drawing, seq(plots[polyg onplot](squares(expand(\n tile2*p)),color=green) ,p=[op(sln2)]) fi;" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 82 "print(plots[display]([drawing])); \nelse RETURN(`no tiling`) fi;\n[sln1,sln2];\nend:\n" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 32 "f :=rect(7,7)-x^3*y^2-y^4-x^6*y;" } }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 35 "tile1 := 1+x+x^2: tile2 := 1+y+y^2:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 32 "tileit(rect(6, 6),1+x+y,y+x*y+x);" }}{PARA 13 "" 1 "" {INLPLOT "6.-%)POLYGONSG6&7&7$$ \"\"\"!\"\"$\"#TF*7$$\"\"*F*F+7$F.$\"#\\F*7$F(F17&7$F($\"#^F*7$F.F67$F .$\"#fF*7$F(F:7&7$$\"#6F*F+7$$\"#>F*F+7$FBF17$F?F1-%'COLOURG6&%$RGBG$ \")`B)e)!\")$\")fqkdFL$\")p:#R%FL-F$6&7&7$$\"#JF*F(7$$\"#RF*F(7$FXF.7$ FUF.7&7$FUF?7$FXF?7$FXFB7$FUFB7&7$F+F(7$F1F(7$F1F.7$F+F.FF-F$6&7&7$FU$ \"#@F*7$FXFdo7$FX$\"#HF*7$FUFho7&7$FUFU7$FXFU7$FXFX7$FUFX7&7$F+Fdo7$F1 Fdo7$F1Fho7$F+FhoFF-F$6&7&7$F(F(7$F.F(7$F.F.7$F(F.7&7$F(F?7$F.F?7$F.FB 7$F(FB7&7$F?F(7$FBF(7$FBF.7$F?F.FF-F$6&7&7$FUF+7$FXF+7$FXF17$FUF17&7$F UF67$FXF67$FXF:7$FUF:7&7$F+F+7$F1F+7$F1F17$F+F1FF-F$6&7&7$F(Fdo7$F.Fdo 7$F.Fho7$F(Fho7&7$F(FU7$F.FU7$F.FX7$F(FX7&7$F?Fdo7$FBFdo7$FBFho7$F?Fho FF-F$6&7&7$F?F67$FBF67$FBF:7$F?F:7&7$FdoF+7$FhoF+7$FhoF17$FdoF17&7$Fdo F67$FhoF67$FhoF:7$FdoF:-FG6&FI\"\"!$\"*++++\"FLF[u-F$6&7&7$F+F?7$F1F?7 $F1FB7$F+FB7&7$F6F(7$F:F(7$F:F.7$F6F.7&7$F6F?7$F:F?7$F:FB7$F6FBFit-F$6 &7&7$F?F?7$FBF?7$FBFB7$F?FB7&7$FdoF(7$FhoF(7$FhoF.7$FdoF.7&7$FdoF?7$Fh oF?7$FhoFB7$FdoFBFit-F$6&7&7$F+FU7$F1FU7$F1FX7$F+FX7&7$F6Fdo7$F:Fdo7$F :Fho7$F6Fho7&7$F6FU7$F:FU7$F:FX7$F6FXFit-F$6&7&7$F+F67$F1F67$F1F:7$F+F :7&7$F6F+7$F:F+7$F:F17$F6F17&7$F6F67$F:F67$F:F:7$F6F:Fit-F$6&7&7$F?FU7 $FBFU7$FBFX7$F?FX7&7$FdoFdo7$FhoFdo7$FhoFho7$FdoFho7&7$FdoFU7$FhoFU7$F hoFX7$FdoFXFit" 2 323 323 323 2 0 1 0 2 9 0 4 2 1.000000 45.000000 45.000000 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 40 15708 0 0 0 0 0 0 }}{PARA 11 "" 1 "" {XPPMATH 20 "6#7$,.*$%\"yG\"\"%\"\"\"*$%\"xG \"\"$F(*&F*F+F&\"\"#F(F(F(*&F*F+F&F'F(*$F&F-F(,.*&F*F(F&F'F(*$F*F'F(F* F(*&F*F'F&F-F(*&F*F'F&F'F(*&F*F(F&F-F(" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 74 " tileit(rect(8,8)-rect(4,4)+rect(2,3)+y^2+x*y^2,rect (1,2) , rect(1,3) );" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 1 " " }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 52 "tileit(rect(6,6)-x*y-x^3* y^3-x^5*y^5,els(2)[1],1+x);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 13 "undebug(cnv);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 7 "els(3); " }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}}{MARK "12 0 0" 93 }{VIEWOPTS 1 1 0 1 1 1803 }