[ 3 / biz / cgl / ck / diy / fa / ic / jp / lit / sci / vr / vt ] [ index / top / reports ] [ become a patron ] [ status ]
2023-11: Warosu is now out of extended maintenance.

/sci/ - Science & Math

View post   
File: 20 KB, 200x201, 5610496_orig[1].png [View same] [iqdb] [saucenao] [google]
5688208 No.5688208 [Reply] [Original]

3x3 cube made out of 27 blocks
if you were to separate it into three geometric shapes of 9 block each
how many unique ways could you separate it?

>> No.5688213

27 right? i did no math it's just a guess but it seems easy.

>> No.5688215

Well, lets count them off.
1. three flat squares

>> No.5688218

Do the shapes have to be contiguous?

>> No.5688219

>>5688218
Yes

>> No.5688230

>>5688219
Does that mean connected by faces, or can they be connected by an edge?

>> No.5688235

unique as in no congruences?

>> No.5688237

>>5688218
but can we rearrange individual cubes?

>> No.5688243

>>5688235
Unique as in permutating, I guess.
>>5688237
I guess? How do you mean?

>> No.5688246

>>5688237
i think it should still fit together as the 3x3 cube

>> No.5688252

>>5688215
a flat square on top of two snug stairsets

>> No.5688256

>>5688243
>Unique as in permutating, I guess.

He means, for example, are the three ways you can slice it to get three flat squares counted as 3 different ways, or just 1 because they're all rotations of one another?

>> No.5688267

>>5688256
that's what i got out of permutating

>> No.5688268

>>5688256
just one

>> No.5688279

>>5688268
Do reflected versions count as identical?
What about pieces that can be put together to form a cube in more than one way?

>> No.5688283

>>5688279
>Do reflected versions count as identical?
yes
>What about pieces that can be put together to form a cube in more than one way?
no
but that sounds interesting if you can find one

>> No.5688288

google "mathematics of the rubiks cube permutation group" or "Rubik's Cube permutation group"

>> No.5688298

with a 2x2 i think there's 3

>> No.5688307

>>5688298
Yeah I think you're right
two flat squares
two triangular
two L shapes

>> No.5688314

>>5688307
So what does that mean for the 3x3?

>> No.5688315

>>5688243
can i take any 9 random cubes?

>> No.5688316

>>5688315
They need to be contiguous

>> No.5688323

81

>> No.5688326

>>5688323
show your work

>> No.5688329
File: 44 KB, 542x325, 2 triangles.jpg [View same] [iqdb] [saucenao] [google]
5688329

these plus another square

>> No.5688332

>>5688326
I can't really I just counted them all up in my head kind of.

>> No.5688342

>>5688332
How many ways have at least one chiral shape?

>> No.5688384

Programming that. I'll let you know what I come up with.

>> No.5688389

i wish i had a toy that could help me with this

>> No.5688402

>>5688389
I tried it in Minecraft but it took too long

>> No.5688459

Counting congruent shapes as different shapes (for now), my algo finds 3504 possibilities. I have to give it a fast check to make sure that what it returns is correct, though.

I considered a shape to be valid if it you can go from any block of the shape to any other block by traveling through contiguous faces (having common edges or vertices is not enough).

I basically count the number of ways one could take the 27 blocks and color them without moving them, as to define a red zone, a green zone and a blue zone, all containing 9 blocks, and all "valid" as detailed above.

>> No.5688467

>>5688208
>Assuming the lack of a 4D stereoscopic view

Infinitely

Took me 2.47 seconds

>> No.5688492

Here are my 3504 shapes: http://pastebin.com/UyhBSVtN

I'll check for duplicates fast. It looks like they are valid in the sense that they are connected shapes which use the 27 different blocks by groups of 9.

>> No.5688493

>>5688459
That's smaller than what I would have expected. BTW are you currently counting the solutions you get by interchanging the red and green zones as distinct?

>> No.5688508

>>5688492
Okay, I have a lot of duplicates. Need to figure out what went wrong.

>>5688493
> BTW are you currently counting the solutions you get by interchanging the red and green zones as distinct?
That's the only congruence I actually try to consider. (red,green,blue) and (red,blue,green) and (blue,red,green) and the other 3 permutations are counted as identical. Basically, I count the number of partitions of the set of blocks that work, and partitions are sets so the order in which I define the 3 shapes doesn't matter. Or well, considering that I still have kinda buggy results, maybe it does, but it's not supposed to.

>> No.5688598

>>5688508
I had a mistake in my code. As >>5688493 had guessed, the number is far larger than 3500.

I made an ugly change to ensure that duplicates aren't counted, and fixed what caused the code to miss possibilities. It's still searching (it's slow, I'm on a slow machine and it's coded in an interpreted language and I made no real effort to have an efficient algo).

At the moment, it found about 500k partitions of 3 shapes. I basically first get a first shape that contains 3,3,3, then find other shapes that work given the first shape. I have at the moment about 2200 different "first shapes" found, and they generate in average about 250 partitions each.

I could run a search for all the "first shapes", count them, and multiply the result by 250, to get a decent approximation of the number of partitions. I'll do that if the algo fails to complete in a reasonable amount of time.

>> No.5688651

>>5688598
OP still here, thank you

>> No.5688674

Not >>5688598 , but I'm getting 40488 first shapes.

>> No.5688733

>>5688674
The "check that you don't find duplicate answers" part of my alg made it eventually require too much memory and it crashed before reaching 40488 first shapes. Let me see if I can confirm that by checking only first shapes.

>> No.5688739

>>5688674
Okay, I find 40488 first shapes too, when I force 333 to be part of the first shape.

As it seems correct, I'll remove the part of my alg that checked for duplicates (it never found any) to avoid out of memory issues, and I'll natively compile it and run it on a faster machine. I'll let you know.

>> No.5688746

>>5688739
Okay, if the speed it roughly constant in the number of first shape, it should take roughly two hours.

>> No.5688811

>>5688746
Finished earlier than expected.

I found 3,835,119 patterns total.

Considering that cubes have 48 symmetries (http://en.wikipedia.org/wiki/Octahedral_symmetry)), that means that there are at least 79,899 non-congruent solutions (probably far more, but we know, assuming my algo is correct, that there are between 79,899 and 3,835,119 non-congruent solutions).

>> No.5689874

>>5688811
I also found 3835119.

>> No.5689897

>>5689874
Cool! Did you give a thought about how to get the number of non-congruent solutions?

>> No.5689909

>>5689897
One way would be to apply all possible transformations and choose the one that's first in lexicographic order. Applying that to the output already generated and removing duplicates should get rid of the congruent solutions.

>> No.5690077

>>5689909
I think that it can work in a reasonable amount of memory and with a reasonable asymptotic complexity (only linearly more time than my current alg), by coming up with a map that transforms a solution into something small (maybe an integer is enough, I'm not sure), and using hash tables, search trees or whatever data structure gives a fast "insert(x)" time and fast "exists?(x)" time.

However, consider how little I work on each of my solution, I think it would multiply the time my program uses per solution by a pretty large factor (anywhere between 10 and 100 wouldn't surprise me), so it may take a long time.

I'll think about it tonight.