[Guest]

The starting position of one player's pieces on a chessboard forms a rectangle of 2 x 8 fields. These 16 pieces could be filed in several different ways that would still form a unique rectangle - with no pieces left, and no pieces missing in the formed rectangle.

The possible combinations in which this can be done are 5:

1 x 16

2 x 8

4 x 4

8 x 2

16 x 1

All 32 pieces can fill unique rectangles in 6 ways. However, with only 24 pieces you can fill unique rectangles in 8 unique ways.

Imagine a near-infinate size chessboard, and equally many pieces. How many pieces would it require for you to be able to fill unique rectangles in 2048 different ways?

Edited April 8, 2009 by uhre

[Guest]

The number of rectangles that could be formed = the number of pairs of factors the number has. And since the order of the numbers matter, this is called a combination, right? As opposed to a permutation?

The OP already demonstrated that 16 pieces can make 5 unique rectangles because 16 has 5 distinct pairs of factors.

Likewise, the OP told us that 32 has 6 combinations.

32:

1x32

2x16

4x8

8x4

16x2

32x1

And that 24 has 8:

1x24

2x12

3x8

4x6

6x4

8x3

12x2

24x1

The answer is... the number that has 2048 distinct pairs of factors.

[Guest]

[spoiler='ummm

']6144

[Guest]

I notice that 3 has 2 posibilites, 6 has 4, 12 and 6, 24 has 8, 48 has 10...etc.

So 3x2^n peices yields 2n possibilites. We want 2048 possibilites so n=1024.

That would mean 3*(2^1024) this is a huge number...excel quit at 2^1023 which is about 9x10^307...so roughly 5.4x10^308?

So I did the same thing starting at 32 peices has 6 possibilities, 16 has 5, 8 has 4 etc.

THIS shows 2^n peices yields n+1 possibilities.

Using this method n=2047 and the total number of peices is 2^2047. I don't think this is the same result that i got in my other method, so I think I am flat out wrong.

Edited April 8, 2009 by wafflechip

[Guest]

I forgot to add this to the OP:

Of course there are several correct answers to the question. And all will be acknowledged as good answers. The best answer, however, is the one requiring the least possible amount of pieces.

[Guest]

The number of rectangles that could be formed = the number of pairs of factors the number has. And since the order of the numbers matter, this is called a combination, right? As opposed to a permutation?

The OP already demonstrated that 16 pieces can make 5 unique rectangles because 16 has 5 distinct pairs of factors.

Likewise, the OP told us that 32 has 6 combinations.

32:

1x32

2x16

4x8

8x4

16x2

32x1

And that 24 has 8:

1x24

2x12

3x8

4x6

6x4

8x3

12x2

24x1

The answer is... the number that has 2048 distinct pairs of factors.

Yes, you are correct so far.

(and these are permutations, since 24x1 is different from 1x24 - as opposed to combinations where the order doesn't matter)

[Guest]

[spoiler='ummm

']6144

This is not the correct answer - and it is not even close. I'd love to hear some reasoning behind the answers as well (when there is any, of course )

[Guest]

So I did the same thing starting at 32 peices has 6 possibilities, 16 has 5, 8 has 4 etc.

THIS shows 2^n peices yields n+1 possibilities.

Using this method n=2047 and the total number of peices is 2^2047. I don't think this is the same result that i got in my other method, so I think I am flat out wrong.

I notice that 3 has 2 posibilites, 6 has 4, 12 and 6, 24 has 8, 48 has 10...etc.

So 3x2^n peices yields 2n possibilites. We want 2048 possibilites so n=1024.

That would mean 3*(2^1024) this is a huge number...excel quit at 2^1023 which is about 9x10^307...so roughly 5.4x10^308?

Well, fortunately I can tell you that both guesses are too large. Anyway, you should add to your reasoning that while 8 pieces has 4 possibilities, 16 has 5, and 32 has 6 - 24 pieces actually has 8 possibilities - so the answer is not quite as simple as that.

[DudleyDude]

According the great Google, the method of finding the number of factors for a number is as such: Reduce the number to it's prime power factors (24 = 2^3 * 3^1). Take the exponents and increase each by one (3->4, 1->2). Multiply the results and that is how many factors are possible (4*2=8; 24 has 8 factors -> 1,2,3,4,6,8,12,24). Using that (plus a spreadsheet), the lowest number I've found is 47,675,628,000 (2^5 * 3^5 * 5^3 * 7^3 * 11^1 * 13^1). This should have (6*6*4*4*2*2) 2304 factors. I have a feeling that this isn't the optimal answer though.

[Guest]

According the great Google, the method of finding the number of factors for a number is as such: Reduce the number to it's prime power factors (24 = 2^3 * 3^1). Take the exponents and increase each by one (3->4, 1->2). Multiply the results and that is how many factors are possible (4*2=8; 24 has 8 factors -> 1,2,3,4,6,8,12,24). Using that (plus a spreadsheet), the lowest number I've found is 47,675,628,000 (2^5 * 3^5 * 5^3 * 7^3 * 11^1 * 13^1). This should have (6*6*4*4*2*2) 2304 factors. I have a feeling that this isn't the optimal answer though.

that I'd have to agree with you. This is not an optimal answer since it is incorrect. The correct answer must have exactly 2048 factors - not 2304.

[Guest]

Yes, you are correct so far.

(and these are permutations, since 24x1 is different from 1x24 - as opposed to combinations where the order doesn't matter)

Oh. I thought it was the other way around. I guess the English language is funny---you know Combination locks? Order matters for them, but combination actually means the order doesn't matter. Just like people park on a driveway, but drive on a parkway.

Will you please answer these two little questions for me? You can either mail me privately, or post on the board. Your choice.

1. What kind of math should I use to solve your riddle?

2. How should I find the lowest number that has 2048 distinct pairs of factors?

Edited April 8, 2009 by HammyHam

[DudleyDude]

that I'd have to agree with you. This is not an optimal answer since it is incorrect. The correct answer must have exactly 2048 factors - not 2304.

I was looking for the smallest number with at least 2048 factors. Not at all what you asked for. One solution would be 21,189,168,000 (2^7 * 3^3 * 5^3 * 7^3 * 11^1 * 13^1). This will have 8*4*4*4*2*2=2048 factors. I think this is also the lowest, but I can't prove it at the moment...

[Guest]

5,587,021,440

(2^7*3^3*5*7*11*13*17*19)

[Guest]

Oh. I thought it was the other way around. I guess the English language is funny---you know Combination locks? Order matters for them, but combination actually means the order doesn't matter. Just like people park on a driveway, but drive on a parkway.

Will you please answer these two little questions for me? You can either mail me privately, or post on the board. Your choice.

1. What kind of math should I use to solve your riddle?

2. How should I find the lowest number that has 2048 distinct pairs of factors?

[Guest]

Let's say K = 2 ^ N is the number of pieces. We can lay them as:

2 ^ 0 [1] x K

2 ^ 1 [2] x K / 2

2 ^ 2 [4] x K / 4

2 ^ 3 [8] x K / 8

….

2 ^ N [K] x 1

So there are N + 1 different ways to lay K pieces.

Now let N + 1 = 2048, you'll get 2048 different forms of laying 2 ^ 2047 pieces

Probably there would be a better solution using fewer pieces, but this one was really easy to find

[CaptainEd]

2*3*5*7*11*13*17*19*23*29*31

There are 11 independent factors. There are 2^11 (=2048) combinations of these factors (that number includes the degenerate 1 by x and x by 1 combinations)

I guess it's conceivable that you could get a smaller number by using repeated factors, as hookemhorns did, but I think his answer doesn't give 2048 possible rectangles.

edit: no, I see that hookemhorns' answer does give exactly 2048 rectangles. And his number is smaller than mine (6469693199)

Edited April 8, 2009 by CaptainEd

[Guest]

Oh. I thought it was the other way around. I guess the English language is funny---you know Combination locks? Order matters for them, but combination actually means the order doesn't matter. Just like people park on a driveway, but drive on a parkway.

Will you please answer these two little questions for me? You can either mail me privately, or post on the board. Your choice.

1. What kind of math should I use to solve your riddle?

2. How should I find the lowest number that has 2048 distinct pairs of factors?

Sorry for the empty post above...

I can't answer your questions without giving the answer away. I can give you some hints though:

This question can be answered without using brute-force programming, spreadsheets, or similar electronic tools (well, a standard calculator would be advisable).

You need to apply some or more of the following:

- mathematical factoring

- prime numbers

- logic

I hope this will help you.

[Guest]

5,587,021,440

(2^7*3^3*5*7*11*13*17*19)

As far as I could figure out, this is indeed the correct answer. Not just a correct answer, but the lowest possible number of pieces. I would like some reasoning behind it though. Or better yet - a technique to apply that would enable me to figure out any reasonable number - say, the number of pieces required for exactly 10.000 combinations - without using more than pen, paper and a standard calculator.

[Guest]

Maybe this will help...

Ok, 2048 is 2^11. Therefore, we know you can use the first 11 primes multiplied together to get the answer (as the Capt. mentioned). So the minimum solution can be found by working from that.

List out the factors, followed by the power that you're raising it to, followed by the next product you'd have to add in order to increase that factor. It's easier if you can see it:

  2|   3|   5|   7|  11|  13|  17|  19|  23|  29|  31

  1|   1|   1|   1|   1|   1|   1|   1|   1|   1|   1

  4|   9|  25|  49| 121| 169| 289| 361| 529| 841| 961

When increasing the exponent for any factor, you have to increase it by the next power of 2, so 1 becomes 3, 3 becomes 7, etc. This is true because 2048 has only 2 as a prime factor. So, on the table above, if we want to increase the exponent on the number 2 (the first column), we will have to go from 1 to 3. This will multiply the current product by 4 (the third row, 2^2). So the trick is this: If there is any number on the first row that is greater than any number on the third row, you can decrease the exponent by the next power of 2 for the larger number and increase it for the smaller. In this example, you can see that the next number for 2 is 4, and it is much less than 31, so we can decrease 31's exponent and increase 2's.

   2|   3|   5|   7|  11|  13|  17|  19|  23|  29|  31

   3|   1|   1|   1|   1|   1|   1|   1|   1|   1|

  16|   9|  25|  49| 121| 169| 289| 361| 529| 841|

You just repeat this process until all of the top numbers are the smallest possible.

  2|   3|   5|   7|  11|  13|  17|  19|  23|  29|  31

  7|   1|   1|   1|   1|   1|   1|   1|   1|	|

256|   9|  25|  49| 121| 169| 289| 361| 529|	|


  2|   3|   5|   7|  11|  13|  17|  19|  23|  29|  31

  7|   3|   1|   1|   1|   1|   1|   1|	|	|

256|  81|  25|  49| 121| 169| 289| 361|	|	|

At this point, the smallest number on the bottom (25) is still larger than than the largest number on the top (19) so you know you're done.

Answer is 2^7 x 3^3 x 5^1 x 7^1 x 11^1 x 13^1 x 17^1 x 19^1 = 5587021440.

P.S. Even as I wrote this, I know it sounds clearer in my head. Sorry if it doesn't make any sense.

edit: fixed a frickin typo. Wow, this post is longer than I expected it to be.

Edited April 8, 2009 by jb_riddler

[Guest]

2*3*5*7*11*13*17*19*23*29*31

There are 11 independent factors. There are 2^11 (=2048) combinations of these factors (that number includes the degenerate 1 by x and x by 1 combinations)

I guess it's conceivable that you could get a smaller number by using repeated factors, as hookemhorns did, but I think his answer doesn't give 2048 possible rectangles.

edit: no, I see that hookemhorns' answer does give exactly 2048 rectangles. And his number is smaller than mine (6469693199)

As I said I'd give credit for any correct answer, this is indeed a correct answer as well. Just not the lowest possible (as you also stated yourself).

[Guest]

Maybe this will help...

Ok, 2048 is 2^11. Therefore, we know you can use the first 11 primes multiplied together to get the answer (as the Capt. mentioned). So the minimum solution can be found by working from that.

List out the factors, followed by the power that you're raising it to, followed by the next product you'd have to add in order to increase that factor. It's easier if you can see it:

  2|   3|   5|   7|  11|  13|  17|  19|  23|  29|  31

  1|   1|   1|   1|   1|   1|   1|   1|   1|   1|   1

  4|   9|  25|  49| 121| 169| 289| 361| 529| 841| 961

When increasing the exponent for any factor, you have to increase it by the next power of 2, so 1 becomes 3, 3 becomes 7, etc. This is true because 2048 has only 2 as a prime factor. So, on the table above, if we want to increase the exponent on the number 2 (the first column), we will have to go from 1 to 3. This will multiply the current product by 4 (the third row, 2^2). So the trick is this: If there is any number on the first row that is greater than any number on the third row, you can decrease the exponent by the next power of 2 for the larger number and increase it for the smaller. In this example, you can see that the next number for 2 is 4, and it is much less than 31, so we can decrease 31's exponent and increase 2's.

   2|   3|   5|   7|  11|  13|  17|  19|  23|  29|  31

   3|   1|   1|   1|   1|   1|   1|   1|   1|   1|

  16|   9|  25|  49| 121| 169| 289| 361| 529| 841|

You just repeat this process until all of the top numbers are the smallest possible.

  2|   3|   5|   7|  11|  13|  17|  19|  23|  29|  31

  7|   1|   1|   1|   1|   1|   1|   1|   1|	|

256|   9|  25|  49| 121| 169| 289| 361| 529|	|


  2|   3|   5|   7|  11|  13|  17|  19|  23|  29|  31

  7|   3|   1|   1|   1|   1|   1|   1|	|	|

256|  81|  25|  49| 121| 169| 289| 361|	|	|

At this point, the smallest number on the bottom (25) is still larger than than the largest number on the top (19) so you know you're done.

Answer is 2^7 x 3^3 x 5^1 x 7^1 x 11^1 x 13^1 x 17^1 x 19^1 = 5587021440.

P.S. Even as I wrote this, I know it sounds clearer in my head. Sorry if it doesn't make any sense.

edit: fixed a frickin typo. Wow, this post is longer than I expected it to be.

Excellent job, jb.

And this makes perfect sense. Especially because it is exactly the way I tested the puzzle as I was constructing it. And by applying this technique it takes about a minut or 2 to calculate the solution for 10.000 combinations - which is a hell of a lot better than the primitive brute-force java program I made to validate it.

Edited April 8, 2009 by uhre

[Guest]

Well the most obvious answer would be just 2*3*5*7*11*13*17*19*23*29*31

because to find the number of factors we only need to add one to each exponents to get 2^11 = 2048.

However we can make substitutions like using 8 (2^3) instead of the 2 so we can get rid of the 31. We can apply similar logic until we get 128*27*5*7*11*13*17*19 = 507911040 where each change would begin to increase the number.

So that is the lowest number.

EDIT: lol when I started writing my solution, there were still only two pages. I guess writing my answer took too long and congrats to jb_riddler for getting it first!

Edited April 8, 2009 by James T

[Guest]

EDIT: lol when I started writing my solution, there were still only two pages. I guess writing my answer took too long and congrats to jb_riddler for getting it first!

Well the most obvious answer would be just 2*3*5*7*11*13*17*19*23*29*31

because to find the number of factors we only need to add one to each exponents to get 2^11 = 2048.

However we can make substitutions like using 8 (2^3) instead of the 2 so we can get rid of the 31. We can apply similar logic until we get 128*27*5*7*11*13*17*19 = 507911040 where each change would begin to increase the number.

So that is the lowest number.

Yeah, I hate it when that happens

Your solution is correct. You did, however, accidentally, leave out 11 when producing the final number - making it 11 times smaller than the correct result.

[Guest]

Your solution is correct. You did, however, accidentally, leave out 11 when producing the final number - making it 11 times smaller than the correct result.

lol that's why you should always show your work then!