Problem 181

[sfabriz]

Hello,

about problem181: what the answer would be for BBWW ?

Would it be 9 with the following groups?

BBWW
B,BWW - BB,WW - BBW,W - BW,BW
B,B,WW - B,BW,W - BB,W,W
B,W,W,W

Cheers,
sfabriz

[daniel.is.fischer]

Yep.

[Robert_Gerbicz]

Yes, that's correct.

[sfabriz]

Ah, all right, thank you very much, now I should know what to do.

Cheers,
sfabriz

[Taifu]

Hello,

about problem181: what the answer would be for BBWW ?

Would it be 9 with the following groups?

BBWW
B,BWW - BB,WW - BBW,W - BW,BW
B,B,WW - B,BW,W - BB,W,W
B,W,W,W

Cheers,
sfabriz

sfabriz,
perhaps last one is B,B,W,W ?
Ciao.
Marco.

[sfabriz]

sfabriz,
perhaps last one is B,B,W,W ?
Ciao.
Marco.

Yes, it is indeed. It's just a typo.
Ciao!

[robheus]

Here is how the problem is formulated:

Having three black objects B and one white object W they can be grouped in 7 ways like this:
(BBBW)	(B,BBW)	(B,B,BW)	(B,B,B,W) 	(B,BB,W)	(BBB,W)	(BB,BW)

In how many ways can sixty black objects B and forty white objects W be thus grouped?

As we can see from the example, the colors don't matter at all, and it seems the problem can be simply re-formulated like this:

In how many ways can any number (including zero) of separators be placed in any position between any two objects (objects layed out sequentially in a row) if there are N objects (so, there are N-1 positions between objects).

Which is realy a simple problem, as it is the summation of placing 0 up to N-1 seperators in N-1 possible locations (each location can have at most 1 seperator), and for placing k seperators in N-1 possible positions this is the well-known formula:

(summation of)
n! / ( k! * (n-k)! )

where n=N-1 and k from 0..N-1

In fact you do not need to use combinatorics equations, since it is either one of N-1 places contains a separator yes or no, which is simply the power equation:

2^N-1-1

For 4 objects we have thus 3 places, and the above equation yields 7.

But this turns out to be the wrong answer as for the case of 60 B and 40 W (= 100) objects, I assumed this would be 2⁹⁹-1 which is 633825300114114700748351602687.

So I suppose this re-formulation is somehow wrong, but then I don't understand the problem.

In what way does the color matter???

(and perhaps I think the problem needs clearer formulation if that is the case, since the example looks like the color does not matter, just the number of objects)

[stijn263]

With B = 2 and W = 2 I get 9 ways to group:

BBWW
B,BWW - BB,WW - BBW,W - BW,BW
B,B,WW - B,BW,W - BB,W,W
B,W,W,W

And with B = 4 I get 5 ways to group:

BBBB
B,BBB - BB,BB
B,B,BB
B,B,B,B

[Doraki]

In that example, what about the (BB,B,W) grouping ?

[robheus]

With B = 2 and W = 2 I get 9 ways to group:

BBWW
B,BWW - BB,WW - BBW,W - BW,BW
B,B,WW - B,BW,W - BB,W,W
B,W,W,W

The last one I assume is incorrect and should be

B,B,W,W

since we use 2 B and 2 W, but that is aside of the issue.

And with B = 4 I get 5 ways to group:

BBBB
B,BBB - BB,BB
B,B,BB
B,B,B,B

I get the picture, I guess.

So I guess that:

(B,B,B,W)

and

(B,W,B,B

) (for the original 2 B 2 W problem) designate the same grouping and count only once.

and while for the 4 B variant

(B,B,BB

) is equal to

(B,BB,B)

and equal to

(BB,B,B)

and count as 1

in case of the 2 B 2 W variant

(B,B,WW) is different from (B,BW,W) and count as 2

[robheus]

In that example, what about the (BB,B,W) grouping ?

In the example given, there are 2 B and 2 W so there is no

(BB,B,W)

group.

Edit: If referring to the original problem, the

(BB,B,W)

group is already considered, but in a different ordering:

(B,BB,W)

.
But for this type of problem, the ordering of the elements in the group are not important.

[GenePeer]

Can anyone explain to me the C code Robert_Gerbicz "translated" from posted PARI solution? I don't mean explaining what the code is doing (C is very similar to Java so I was able to implement it) but explaining its relation to the problem.

Thanks.

[hk]

This forum is not a place to discuss solutions.
So if someone wants to answer this question please do so in the problems forum.
It's still open and there is plenty of room there.

@GenePeer: as the problems forum is still open, the place to ask your question is there.

[GenePeer]

Those forums seem to be active only when the problem is released. I was hoping someone who understands it would send me a PM, not discuss it here.

PS: Can there be a notification system like "View your posts" where you can see if there are new replies in forums you posted in? Maybe this could help spark activity in those threads.

[hk]

The correct way would have been:
post your question in the problems forum and ask here if someone is willing to answer it there.
In that way your question (and hopefully answer) would contribute to the problems forum and spark activity there.
PM-ing explanations to each other doesn't contribute to the community.

[GenePeer]

Done.

I just posted a question on the problem's solution-thread. Can someone answer it? Thanks.

[LarryBlake]

I get the correct answers for BBBW and BBWW.

For B(5)W(5), I get 335. Is that correct?

[Marcus_Andrews]

I get the correct answers for BBBW and BBWW.

For B(5)W(5), I get 335. Is that correct?

I'm afraid not -- but you're close!

[snapey1979]

I found the example for this problem a little confusing. In particular, as I read it, you had to keep the original "string" of Black and Whites in the same order. i.e. for BBWW, I thought the groupings were (BBWW), (B,BWW), (BB,WW), (BBW,W), (B,B,WW), (B, BW,W), (BB,B,W) and (B,B,W,W). But, crucially, not (BW,BW)

This forum explanation of groups for BBWW (i.e. (BW, BW) is valid) explained this, but without the forum I think I would have banged my head for a long time (particularly as my solution with the order of the original string preserved gives the right answers for a number of cases).

I wonder if a further example with a grouping that includes such a group might be useful. On the other hand, might just be me as many others have passed this way before...

[Perlkonig]

Uhm, why is the grouping (BB,B,W) not also valid? Is that what I'm supposed to figure out? Thus the phrase "thus grouped"? If so, my suggestion would be to reword the problem to make the "riddle" aspect more explicit.