Thu 6 Aug 2009
Matthew Swanson and Robbi Behr ‘97 are collaborating with caped superhero Cory Doctorow (the blogger behind the beloved Boing Boing) on his new book, Makers, which is about two guys living in the not-too-distant future who invent things out of junk, start a movement, eat lots of IHOP, and end up having all sorts of dicey legal adventures with minions of the Disney corporation.
The book will be released in 81 parts on Tor.com (the whole thing will be released in October, but you can start reading it here – the first 14 parts have already been published – table of contents here). Behr and Swanson are creating an illustration for each section. What’s unique about this is that the 81 illustrations are designed to be recombined endlessly* to create new composite illustrations. You can read more about what that means and how it works here.
The first 9 illustrations have been used to create a flash game where you can rearrange the images on a 3×3 grid to come up with new illustrations. As the book grows, this game will eventually expand to a 9×9 grid. Even with only 9 tiles, the results so far are fairly magical.
You can also save the images you create, and if you’re particularly proud of your creation you can send it to Matthew (who can be reached at Matthew at idiotsbox dot com), who will feature it on his blog.
Click on the image below to start playing:
*Question for math majors: yes, I know it’s not technically endless. How many new illustrations can actually be produced with the 81 squares? Remember that they don’t always have to be combined in grids when they’re printed – you could cut them out and combine them in various sorts of linear arrangements.
Print • Email| « Blu Dot Special | #4, According to Forbes » |
35 Responses to “Play with tiles”
Leave a Reply
Trackbacks & Pingbacks:
-
Pingback from Support Your Fellow Ephs : EphBlog
December 8th, 2009 at 9:21 pm
[...] prints, and other hilarious gifts are perfect for any member of the family. Previous coverage here, here, and here (among others). They have a hilarious blog, including cute pics of their daughter [...]
You can follow this conversation by subscribing to the comment feed for this post
If a comment you submitted does not show up, please email us at eph at ephblog dot com. Please note that commenters are required to use a valid email address when submitting comments.
Matthew Swanson says:
Thanks for the post, Ronit. Robbi and I having a blast with this. To further complicate things for the math majors, keep in mind that the tiles can be rotated and still line up with one another. Also, it occurs to me that the tiles can be used to make three-dimensional objects (six could be used to make a cube, for example). Perhaps we should allow the plane geometry specialists (even the great Ed Burger himself) to take a crack at an estimate for the number of possible 3D permutations?
JeffZ says:
Great stuff: the Class of ‘97 continues to kick ass.
'13 says:
81!*4^81
Robbi Behr says:
‘13:
Unfortunately (or, maybe, fortunately) I was an Art/English major – is that a formula in your comment, or just a very complex emoticon (I think that’s what I look like when I try to do the math)?
I’m VERY curious to figure it out. Oh, would that I had taken The Spirit of Math with Ed Burger!
sigh.
Matthew Swanson says:
I actually did take the Spirit of Math with Ed Burger, and yet I am no closer to grasping the wisdom of ‘13.
Please enlighten us.
dm '10 says:
’13’s answer is correct for the case in which everything is kept in a 9×9 square (or any other single arrangement). If you’re not used to standard math notation, maybe the formula would be clearer as
(81 factorial) times (4 to the 81st power)
81 factorial is the number of possible orderings of tiles, since there are 81 tiles, 81 squares, and each tile can only be used once, so there are 81 options for the first square, 80 for the second, and so on: 81*80*79*78*77*…*2*1 = 81 factorial, which is written 81!
Given a particular ordering of tiles, there are 4 possible rotations of the first tile, 4 possible rotations of the second tile, and so on, so the total number of possible rotations of all tiles is 4*4*4*4*…(81 times)..*4*4 = 4 to the 81st power, written 4^81.
This is all (essentially) middle school math – nothing too arcane here. If you plug this into Wolfram Alpha you can get the decimal expansion, which is 33890036684543440769057774862779477997325787000968328173127424517002031965929221017975069852474193892633991640448359911591329973070266928563916552273920000000000000000000.
The total number of possible arrangements is actually much larger, if (as you suggest) we’re allowed to take the squares out of the 9×9 grid and arrange them differently. There are 2^80 ways to arrange the squares in rows of different sizes (assume you place the first square, and then for each subsequent square you have to decide whether to place it on the same row or on the next row – there are two options, and you must make the decision for each of the remaining 80 squares, so 2^80), so the total number of arrangements is at least (81!)*(4^81)*(2^80). But then you have to consider the ways in which squares can be aligned within rows – if the first row has 80 squares and the second row has one square, that one square could be aligned with any of the 80 squares – which makes things start to become complicated.
An upper bound would be the number of ways to place 81 items within a full 81×81 grid (since there’s obviously no way to get bigger than that), which is just (81^2 choose 81) times the number given by ‘13, or 5322104461771248733888756294268672420502329732509626654780191251062519166280634799983000941106981640028467858987354262040152289164230784617329617105119850384343913568810681807667071984653857663841229182876626252704875638131067800269050285152115808606609722447639804571602908412754875086008448347309803419359848120875254453369923376565452800000000000000000000. But this includes all kinds of configurations in which no blocks are touching each other, so it’s probably too big. A reasonable restriction would be to say that the blocks need to be connected: starting at any one block, you should be able to reach any other block without having to go over a blank space. I’ll leave it to someone else to work out how many possibilities that allows.
JeffZ says:
My response to Ronit’s query:
[image added by Ronit]
JeffZ says:
re: comment six, I am trying to figure out if Williams undergrads have gotten smarter, or if I am just getting dumber …
rory says:
jeffz–i’ve come to accept that it’s both me getting dumber and them getting smarter and pray that i graduate grad school and get tenure before they start replacing me with this new smarter generation
:)
JeffZ says:
Thanks Ronit. How do you do that in a comment?
Ronit says:
@JeffZ: <img src=”image url” />
Just for kicks, I’ve also enabled LaTeX on EphBlog, so if anyone wants to show their work or embed an equation, they can do so by surrounding their LaTeX notation with [latex] and [/latex]
Testing to see if LaTeX works…
[latex]e^{\i \pi} + 1 = 0[/latex]
should display as…
Robbi Behr says:
I’m afraid I’m not even as clever as Calvin.
But WOW is the math fascinating. That exclamation point is a powerful thing!
The very first project like this we did was a book titled 10,000 Stories, which is an exquisite corpse-type deal, with 10 pages divided into 4 sections. So, simply, 10×10x10×10 (the math was figured out by someone else – I started counting and got up to 17 before I gave up and figured smarter people needed to intercede). I’m glad we didn’t decide to follow suit and name this one 33890036684543440769057774862779477997325787000968328173127424517002031965929221017975069852474193892633991640448359911591329973070266928563916552273920000000000000000000 Stories!
dm '10 says:
Although the basic combinatorics of the situation (as given by ‘13) are pretty simple, there are a actually a lot of interesting ways to approach the problem of configuring 81 tiles to form a connected shape. If you start with a single tile in the plane, you can place the next tile on any of the four edges of the first tile. Then you have six options for where to place a third tile (since placing the second tile used up one of the original four spaces, but added three new exposed edges). If you could keep going like this, you would have eight options for placing the fourth tile, ten for the fifth, and so on, so the total number of shapes formable with 81 tiles would be:
(and you could just multiply this by ’13’s number to get the total number of possible tile arrangements).
Of course you can’t actually do this, since some of the possible paths lead to situations in which you’re “filling in holes” – placing a tile so that it shares multiple edges with existing tiles, thus cutting off more than one possible playing spot. The number above is too big because it assumes that adding a new tile always adds a net of two new exterior edges. It’s also too big because it fails to account for symmetry – e.g. you can produce a vertical line by starting at the bottom and growing upwards, or starting at the top and growing down (or starting in the middle and growing out), but it’s the same shape either way and so you’d probably only want to count it once.
Basically, the number of possible connected shapes is somewhere between
and
, since the row-based approach in comment #6 gives us the first number but fails to account for all the ways tiles can be arranged within each row, and the incremental-growth approach above gives the second number but overcounts because it includes impossible configurations as well as multiple ways of generating the same configuration. I don’t have any intuition for which side of the bound the true answer is likely to be closer to, but then again, I don’t really know anything about this stuff.
I know there must be a bunch of Ephblog readers who are better at math than I am – anyone else want to take a crack at this? I’m sure there’s a clever solution; I’m just having a hard time seeing what it would be.
dm '10 says:
It looks like Wordpress is a confused by two bits of LaTeX in the same sentence. That should read “the number of possible connected shapes is somewhere between 2^80
and 2^{80}(81!)”.
[Thanks for noting that. Since the size of the resulting LaTeX images are indeterminate, the HTML/CSS has a hard time displaying it inline with other text. I've kluged it so that each bit of LaTeX will be displayed on a new line from now on. - Ronit]
Larry George says:
I like this post.
A lot.
Maybe not 2^{80}(81!) but a heckuva lot.
Ken Thomas '93 says:
Hmmm.
Spse…
Option 1 might be described as straight line of 81 tiles. How many variations does this option have? 81!?
Option 2 might be described as a straight line of 80 tiles, with one tile attached to the line … 80!? + …
Option 3 might be…
?
Ken Thomas '93 says:
#16 will obviously not work.
How about: solve for 1 tile. Solve for 2 tiles. Solve for 3 tiles {…} 81 tiles.
?
Qiao' 13 says:
Quote dm ‘10 Comment 6::
“There are 2^80 ways to arrange the squares in rows of different sizes (assume you place the first square, and then for each subsequent square you have to decide whether to place it on the same row or on the next row – there are two options, and you must make the decision for each of the remaining 80 squares, so 2^80), so the total number of arrangements is at least (81!)*(4^81)*(2^80).”
I was just wondering that when you place the third tile,couldn’t there be 3 options(1st,2nd or 3rd row supposing the 2nd tile is on 2nd row)instead of 2 options? But the strange thing is,I got the same answer as yours eventually by another method.
My method ignores the condition of 9*9 grid because when we consider the possibilities of different linear arrangements we don’t have to care about the grid condition.
I rephrase the tile problem simply as such
1.81 tiles in total
2.each tile can rotate
3.allow different linear arrangements
4.all rows aligned to the left(I’m still trying to figure out the case when we allow different configuration within the same row)
How many different permutations are there?
First,we consider the 81 tiles aligned in a line.We have 81!*4 permutations.(allowing positional changes and rotations)
Second,to allow different linear arrangements,we consider placing partition walls in between tiles,so we can place n partition walls (0<=n<=80) in the 80 spacings in the initial row of 81 tiles.Here placing a partition wall in a spacing between two tiles is like punching the ENTER KEY in between two words.Therefore,this operation generates 80C0+80C1+80C2+…+80C80=2^80 new permutations
so total number of permutations is 81!*4*2^80
dm '10 says:
Qiao ‘13: I guess I didn’t write it very clearly, but I think you and I are actually thinking of things pretty much the same way. My unstated assumption in the paragraph you quoted was that we started out with the tiles in some particular ordering (“81 tiles aligned in a line” as you put it) and then placed them onto the grid, in order from top left to bottom right, in the same sort of way you would type English text (including something analogous to pressing ENTER between lines). So the third tile could not go on the first row, given that the second tile is on the second row, because if you wanted it to go there you should have switched up the order and placed it before the second tile. Basically this is just a less clear way of expressing the same idea as your partition walls. Your original line of 81 tiles has 80 borders between tiles, and at each one of them you have the option of placing a partition or not (2 options), so there are 2^80 ways to place the partitions. This is equivalent to 80C0+80C1+80C2+…+80C80 (the number of ways to place zero partitions, plus the number of ways to place one partition, plus the number of ways to place two partitions, etc.) but thinking of it as eighty independent binary decisions gets you to 2^80 automatically without requiring you to do an eighty-term sum.
Ken Thomas '93 says:
… consider the case when there are only four tiles. How many permutations are possible?
Matthew Swanson says:
Is anyone willing to tackle the question of what happens when you introduce the third dimension? Not that there aren’t enough 2-D permutations to keep us all busy for a while, but…
Diana says:
3D is much, much harder because you have to consider rotations of the cube (you consider two cubes to be the same if you can rotate one into the other). I, for one, am not willing to tackle it.
Diana says:
I forgot that the tiles are all distinct and have an orientation. That makes it a lot easier. The problem is much harder if the tiles are solid colors, for example.
If you are going to make a cube, it has 6 faces. So you have to choose the six tiles that you are going to use. Since you have 81 to choose from, that is
choices. This assumes that you are choosing the tile for Face 1 first, then the tile for Face 2 next, and so on.
But now there are various rotations for which you must control. We have to divide by the number of symmetries of the cube, which is 6*4 = 24. So our answer is
.
Note: At first, I was thinking that it didn’t matter what order you chose the tiles in, so you should do 81-choose-6
But I think that would make it a lot more difficult to divide by the symmetries, since you would have already done some correcting for the symmetry. Thoughts?
EDIT: Latex is clearly not displaying my formulas properly.
[Fixed slashies - Ronit]
Qiao' 13 says:
dm’10:
I think you are right coz I’d have double-counted if I count 3 options for the third tile.Actually I don’t have to calculate the summation coz by some formula the summation=2^80.
btw,are u a math major?
lgeorge says:
EphBlog’s math tiling challenge is linked and featured on the Math Department site: http://math.williams.edu/ephblog-tiling-challenge-for-math-majors/
(Contrary to the title, no need to be a “math major” to play.)
JeffZ says:
Thanks a lot for posting that comment Larry, now I owe DK a sandwich.
Nick says:
My girlfriend pointed me to this problem. When the 9×9 square restriction is removed, it becomes an instance of the polyomino counting problem:
http://en.wikipedia.org/wiki/Polyomino
http://mathworld.wolfram.com/Polyomino.html
Specifically, it’s the fixed polyomino counting problem, because we consider a rotation of a given arrangement to be a new arrangement. This problem is more or less unsolved. The only known way to figure it out is essentially to just enumerate them all and count. While there are fancy computer algorithms to speed this up a bit, the problem gets out of hand rather quickly and to my knowledge no one has ever managed to get up to 81.
This list shows some smaller results:
http://www.research.att.com/~njas/sequences/table?a=1168&fmt=4
The left column is the number of tiles, and the right is the number of arrangements.
Note that the polyomino counting problem does not take into account the question of rotating the individual tiles, or the fact that individual tiles are different from one another. It only counts the shapes into which they may be arrange. So, the number of arrangements of n tiles is n!*P(n)*4^n, where P(n) is the number of fixed polyominoes of that size.
A quick jump over to Wolfram Alpha reveals this to be 26980519328800085374834342152755878331730212833210662912000000, or about 2.7×10^61 for 28, the highest values given in the above list. For comparison, the observable universe is estimated to contain 10^80 atoms. It seems quite reasonable to say, then, that the number of free-form tile arrangements when using all 81 exceeds by many orders of magnitude the number of atoms in the universe.
Ronit says:
@Nick: Thanks for that, I think you’ve blown all of our minds.
Ken Thomas '93 says:
Nick,
Damnit! You gave it away!!
I had neglected this thread a bit, but my next hint would have been something like:
“Draw all the solutions for n=5 and n=8. What do they tell us about topology?”
I… actually, I’ll hold further comment, in case we can get some more discussion.
Ronit says:
The 4×4 version of the game is now a reality:
http://www.thebarnstorming.com/archives/2009/08/makers_tile_gam_2.html
dm '10 says:
Nick: thanks for putting a name to the problem. It’s good to hear that the reason we were having trouble is that it’s actually an open problem, rather than just a simple trick we were missing.
In comparison to atoms in the known universe, you can ignore the polyomino considerations completely (assume a 9×9 square) and you still have 4^81*(81!) configurations, which is roughly 10^170. So even if every atom in the universe had its own individual sub-universe with its own 10^80 atoms, the number of configurations within a 9×9 square would still be larger than the total number of atoms in that universe-of-universes. If you do multiply by the P(81) term (whatever that might be) to account for the number of 81-tile polyominos, you’d probably be able to add a few more levels of universes-within-universes to that example.
And these numbers are still relatively small by mathematical standards, especially once you start playing around with Ackermann or busy beaver functions.
Matthew Swanson says:
“Busy beaver functions?” The layman readership demands explanation.
Nick says:
The busy beaver function is a bit technical, but I’ll give it a go.
So, in order to understand the busy beaver function, we need to understand Turing Machines, which are hypothetical computing devices proposed by Alan Turing. The machine consists of a few parts: a read/write head, a memory bank with some rules, a memory bank maintaining the current ’state’ of the machine and an infinte ticker tape on which we can write symbols. For simplicity, we’ll use 0 and 1 as our alphabet of symbols. This means that every spot on the ticker tape can be either a 0 or a 1, or can be blank. We’ll say that everything starts out as a blank, but you can also use the starting contents of the tape as input to the machine. The neat thing about these is that they are capable of any computation of which any computing device is capable. They might take a bit longer, but if the super-computer down in Los Alamos can solve it, so can a humble Turing Machine.
The Turing machine process goes like this:
Read the symbol currently under the head.
Consult the rule table, and find the entry corresponding to the current state, and the current symbol.
That rule will say to write a new symbol, move either left or right, and enter a new state. One of the potential new states is the HALT state, which means its done computing, and the answer is whatever’s left on the tape.
So, here’s an example rule
If I’m in state 0, and read a BLANK, write a 1, move RIGHT, and enter state 0.
This machine will simply fill the entire tape with an endless string of 1’s. It effectively counts in unary. With a little more effort, we could make it count in binary.
An interesting question to ask about Turing Machines is whether they eventually enter the HALT state. The one above never does. The general form of the question is, if I give you an arbitrary Turing Machine (meaning any set of rules), will it halt eventually? Suppose that, hoping to solve this, you came up with a way to translate the settings of a Turing Machine into 0’s and 1’s. You could then feed these translations into another Turing Machine. That Turing Machine’s set of rules would be such that it would read the other Machine, do a bunch of figuring, and then leave a 0 or a 1 on the tape, telling you whether the first Machine would have halted.
Is such a Turing Machine possible? As it turns out, no. It’s clearly possible to make one that always correctly identifies the ones that do halt. Just simulate the execution of the machine, and halt with the YES output when it halts. But what if the answer is no? That strategy would then mean that your second machine never halts either. This is called the Halting Problem, and Turing proved that its undecidable. The proof is a bit tricky, so I’ll leave it as an exercise for the reader.
So, this brings us at last to the busy beaver function. Suppose I take the set of all possible Turing Machines with N states (meaning that they can enter states 1…N and HALT). If I run them all, and take only the ones that eventually halt, what is the maximum number of steps that will be taken before a halt? (Some define it as the maximum number of 1’s, but I like this version better).
For example, with only 1 state (call it STATE 0), it’s not too hard. Compare these two rules:
If I read a BLANK, and I’m in STATE 0, write a 1, move RIGHT and enter STATE 0.
and
If I read a BLANK, and I’m in STATE 0, write a 1, move RIGHT and HALT.
The first rule goes on forever, and the second rule halts after 1 step. Every other 1 state machine is a variation on these two, except with moving LEFT or writing 0’s. They all either never halt, or halt after 1 move. Therefore BusyBeaver(1) = 1.
The Busy Beaver numbers are the maximum number of moves I can make with an N state Turing Machine before it halts.
Now, suppose I had a handy way to figure out the Busy Beaver numbers. What if I made a Turing Machine to do this:
-Read in the 0’s and 1’s translations of another Turing Machine.
-Count how many states it uses, call this number N.
-Simulate the machine for BusyBeaver(N) steps.
-If it halts, return YES, if it hasn’t halted yet, return NO.
This machine solves the Halting Problem. If BusyBeaver(N) is the maximum number of steps it could take before halting, and it hasn’t halted after that many steps, we can say for certain that it doesn’t halt ever.
But, as we saw earlier, the Halting Problem can’t be solved by Turing Machines. This means that our assumption that we can figure out in general the value of BusyBeaver(N) is false. This means BusyBeaver(N) is uncomputable. If we could compute it, we could solve the Halting Problem.
What if instead of BusyBeaver(N), we tried to compute a function called ReallyReallyBig(N). We pick a function that’s so astronomically huge, that it’s bigger than BusyBeaver(N) for all N, and compute that instead. Well, this is no good either. Substitute ReallyReallyBig for BusyBeaver, and run for that many steps instead. That would solve it too.
The result is that BusyBeaver(N) is bigger than any computable function. As we saw, the number of arrangements of the tiles is computable. That means that BusyBeaver(N) is so huge that it dwarfs even that.
For more on really big numbers, including what is probably a better explanation of BusyBeaver:
http://www.scottaaronson.com/writings/bignumbers.html
sophmom says:
Wow.