Don't have an account? Register now to chat, post, use our tools, and much more.
Online Users
There are 105 users online: 4 members, 70 guests and 31 bots.
Members: HOMER-16, lafferjm, Xeda112358.
Bots: VoilaBot (3), Spinn3r (3), MSN/Bing (2), Magpie Crawler (4), Googlebot (19).
SAX
This is an archived, read-only copy of the United-TI subforum , including posts and topic from May 2003 to April 2012. If you would like to discuss any of the topics in this forum, you can visit Cemetech's Technology & Calculator Open Topic subforum. Some of these topics may also be directly-linked to active Cemetech topics. If you are a Cemetech member with a linked United-TI account, you can link United-TI topics here with your current Cemetech topics.

Math and Science => Technology & Calculator Open Topic
 » Goto page 1, 2  Next
Author Message
magicdanw
pcGuru()

Calc Guru

Joined: 14 Feb 2007
Posts: 1110

 Posted: 03 Jan 2008 01:26:00 pm    Post subject: My friend's cousin (a math professor) posed this problem: How many shapes can be made using the squares of a chessboard? This is like the problems of how many squares can be constructed on a chessboard, but it includes any closed shape regardless of the number of sides. The shape's area consists of the selected squares. The professor said that he didn't know the answer to this puzzle, and was unaware of any elegant (mathematical) solution. Does anyone know of a solution to this problem, short of constructing every possibility on a supercomputer, storing them all, and comparing them for replicated shapes?
DarkerLine
ceci n'est pas une |

Super Elite (Last Title)

Joined: 04 Nov 2003
Posts: 8328

 Posted: 03 Jan 2008 01:27:24 pm    Post subject: Does the shape have to be connected? If not, the answer is 2^64 - for each square, you have the option of including it in the shape or not.
JoostinOnline

Active Member

Joined: 22 Aug 2007
Posts: 559

 Posted: 03 Jan 2008 01:32:20 pm    Post subject: He said they have to be an enclosed shape.
DarkerLine
ceci n'est pas une |

Super Elite (Last Title)

Joined: 04 Nov 2003
Posts: 8328

 Posted: 03 Jan 2008 01:35:58 pm    Post subject: Right. Sorry. That does make the problem a bit harder. Are holes allowed? And are two squares that share a corner connected?Last edited by Guest on 03 Jan 2008 01:37:26 pm; edited 1 time in total
magicdanw
pcGuru()

Calc Guru

Joined: 14 Feb 2007
Posts: 1110

 Posted: 03 Jan 2008 01:58:09 pm    Post subject: I'm not sure about holes; I can ask my friend if he knows tomorrow in school. As for corners, I'm pretty sure they aren't considered connected. Do you know if this is a puzzle that might have been attempted before? A lesser-known but still classic puzzle? Or did my friend's cousin just make it up with no solving method in mind?
DarkerLine
ceci n'est pas une |

Super Elite (Last Title)

Joined: 04 Nov 2003
Posts: 8328

 Posted: 03 Jan 2008 02:58:45 pm    Post subject: It's probably been posed before, though I haven't found anything about it so far. For reference, such connected shapes are called "polyominoes" (as a generalization of "dominoes").
Recursive Acronym

Joined: 11 Dec 2006
Posts: 499

Posted: 03 Jan 2008 05:35:19 pm    Post subject:

 magicdanw wrote: ...and comparing them for replicated shapes?[post="118098"]<{POST_SNAPBACK}>[/post]
Does this mean that rotations and reflections are the same shape, or does this only eliminate translations of the same shape?
 DarkerLine wrote: Does the shape have to be connected? If not, the answer is 2^64 - for each square, you have the option of including it in the shape or not.[post="118099"]<{POST_SNAPBACK}>[/post]
That is incorrect; a 2*2 square is only a single shape, but can be placed in 49 different locations on the board.
DarkerLine
ceci n'est pas une |

Super Elite (Last Title)

Joined: 04 Nov 2003
Posts: 8328

Posted: 03 Jan 2008 05:40:05 pm    Post subject:

Recursive Acronym wrote:
 magicdanw wrote: ...and comparing them for replicated shapes?[post="118098"]<{POST_SNAPBACK}>[/post]
Does this mean that rotations and reflections are the same shape, or does this only eliminate translations of the same shape?
 DarkerLine wrote: Does the shape have to be connected? If not, the answer is 2^64 - for each square, you have the option of including it in the shape or not.[post="118099"]<{POST_SNAPBACK}>[/post]
That is incorrect; a 2*2 square is only a single shape, but can be placed in 49 different locations on the board.
[post="118123"]<{POST_SNAPBACK}>[/post]

Well, those 49 locations are counted 49 times in the "how many squares..." problem that magicdanw compared this to, so I don't see why they would only be counted once in this one.
Recursive Acronym

Joined: 11 Dec 2006
Posts: 499

 Posted: 03 Jan 2008 05:49:56 pm    Post subject: That could be true. magicdanw, could you give us more information?
DarkerLine
ceci n'est pas une |

Super Elite (Last Title)

Joined: 04 Nov 2003
Posts: 8328

 Posted: 03 Jan 2008 06:41:50 pm    Post subject: A side note: I really need a whiteboard. I've probably killed half a tree working on this problem so far.
elfprince13
Retired

Super Elite (Last Title)

Joined: 11 Apr 2005
Posts: 3500

Posted: 03 Jan 2008 07:21:48 pm    Post subject:

 DarkerLine wrote: A side note: I really need a whiteboard. I've probably killed half a tree working on this problem so far. [post="118131"]<{POST_SNAPBACK}>[/post]

or a wacom tablet ;)

and can we have more specifics on the exact rules for this project? are congruent shapes with different colors considered the same? what are the space confinements? or is this rather how many shapes can be made ON a chessboard?
magicdanw
pcGuru()

Calc Guru

Joined: 14 Feb 2007
Posts: 1110

 Posted: 03 Jan 2008 08:29:34 pm    Post subject: I don't understand your concerns about color. Color of shapes is irrelevant. You just need to try making a single shape on the chessboard, and see how many single shapes can be made on the chessboard, not at the same time. I'll try to find out more specifics from my friend tomorrow at school, but he may not know them either.
elfprince13
Retired

Super Elite (Last Title)

Joined: 11 Apr 2005
Posts: 3500

Posted: 03 Jan 2008 09:42:12 pm    Post subject:

 magicdanw wrote: I don't understand your concerns about color.  Color of shapes is irrelevant.  You just need to try making a single shape on the chessboard, and see how many single shapes can be made on the chessboard, not at the same time.  I'll try to find out more specifics from my friend tomorrow at school, but he may not know them either. [post="118141"]<{POST_SNAPBACK}>[/post]

ok, ON the chessboard, not with the individual squares of the chessboard.
magicdanw
pcGuru()

Calc Guru

Joined: 14 Feb 2007
Posts: 1110

 Posted: 03 Jan 2008 09:44:07 pm    Post subject: I think you've got it. Like, if I gave you infinite chessboards, and on each one you could color in adjacent squares to form a solid shape on the board, how many boards could you color until you run out of unique shapes. And I'm assuming that rotations and reflections count as different shapes.
DarkerLine
ceci n'est pas une |

Super Elite (Last Title)

Joined: 04 Nov 2003
Posts: 8328

 Posted: 03 Jan 2008 10:55:50 pm    Post subject: What about translations?
magicdanw
pcGuru()

Calc Guru

Joined: 14 Feb 2007
Posts: 1110

 Posted: 03 Jan 2008 11:13:36 pm    Post subject: You mean the same shape shifted across the board? Also different, because they use different squares. It's not about cutting a unique shape out of the board, but it is about identifying shapes found on the board.
Weregoose
Authentic INTJ

Super Elite (Last Title)

Joined: 25 Nov 2004
Posts: 3976

 Posted: 04 Jan 2008 04:23:16 am    Post subject: What if one repeatedly "splatters" a chessboard with this color, records whether or not there is an island made up of it, continues on until there is a decent enough approximation of the odds of this happening, and then multiplies those odds by the possible number of colorings? Analogously, create a random binary array and see if each "one" is mimicked by any elements located at a distance of ±1 or ±√length(array) indices from it; if not, then it represents an island. Find out the numbers for general board sizes and then pray that Sloane's Encyclopedia has already listed them—it's not mathematically beautiful, but it's a way to find out.Last edited by Guest on 04 Jan 2008 04:29:15 am; edited 1 time in total
simonzack

Joined: 25 Dec 2007
Posts: 71

 Posted: 04 Jan 2008 04:34:42 am    Post subject: This can be simplified to (the 'with holes' situation): with a[8] ( a cloumn), find all b[8] that with each b column joins to an a column, and start working here. I'll try this now...
magicdanw
pcGuru()

Calc Guru

Joined: 14 Feb 2007
Posts: 1110

 Posted: 04 Jan 2008 01:07:15 pm    Post subject: simonzack: I'm afraid I don't understand what you're talking about here...Could you explain? Weregoose: Also, I'm not fully understanding your suggestion. What I got out of it is that you're saying I should randomly select squares on a board, check if it forms a closed shape (I found out that holes can exist in the shape), and compare those to the total number of possible combinations. I don't really see how this would work...
JoostinOnline

Active Member

Joined: 22 Aug 2007
Posts: 559

 Posted: 04 Jan 2008 01:14:22 pm    Post subject: I am sorry if you already said this, but I can't find it. Do the dimensions of the shape matter (i.e. are a 1x1 square and a 2x2 square count as different shapes?)?
 Display posts from previous: All Posts Oldest FirstNewest First
Register to Join the Conversation
Have your own thoughts to add to this or any other topic? Want to ask a question, offer a suggestion, share your own programs and projects, upload a file to the file archives, get help with calculator and computer programming, or simply chat with like-minded coders and tech and calculator enthusiasts via the site-wide AJAX SAX widget? Registration for a free Cemetech account only takes a minute.

»
 » Goto page 1, 2  Next Page 1 of 2 » All times are GMT - 5 Hours

© Copyright 2000-2013 Cemetech & Kerm Martian :: Page Execution Time: 0.026344 seconds.