The five girls, named G1, G2,…G5 arranged the round-table sitting so that between each two of them there were at least two out of 12 boys , B1, B2,…B12.
In how many ways is such arrangement possible?
First of all there are 4! = 24 ways of arranging G2,...,G5 relative to G1. This applies to each of the scenarios mentioned below:
There were between 5 and 12 boys included, inclusive. For each number of boys, at least one is between each girl.
For 5 boys:
There are C(12,5) = 792 ways of choosing the 5 boys.
There are 5! = 120 ways of arranging the 5 boys.
792*120*24 = 2280960
For 6 boys:
There are C(12,6) = 924 ways of choosing the 6 boys.
There are 15 ways of choosing the two of these six to sit between the same two girls.
There are again 120 ways of arranging the resulting 5 entities (boy or pair of boys).
924 * 15 * 120 * 24 = 39916800
From here on it gets a bit hairy. The first part, C(12,k), is straightforward, as is the constant 120 ways of arranging 5 entities, and the 24 arrangements of the girls stays 24
But the ways of grouping the k boys into 5 entities is the hairy part. This must be done in such a way as not to count a given grouping more than once. And you don't want to break into an unmanageable number of cases.
The program below forms all such arrangements and counts them. They appear in the third column below:
One note: I wrote this while solving, including writing the programs. The first attempt lacked something (see second thoughts after it), but in the second thoughts, I show only the correction to the program; the major structure of the program remains the same.
Also, there's a question as to whether all the boys need to be included. My major finding includes the possibility that the arrangements might also include those in which not all the boys are included. But since the solution is done by summing the different number of boys, the possibility that all are included is one of the addends.
# of ways of grouping
boys C(12,n) the boys
5 792 1
6 924 15
7 792 140
8 495 1050
9 220 6951
10 66 42525
11 12 246730
12 1 1379400
In each case the ways of placing the groups is 120 and there are 24 ways of placing the girls. All placements are relative to G1.
The resulting products are:
2280960
39916800
319334400
1496880000
4404153600
8083152000
8526988800
3972672000
(for example, the 319334400 = 792 * 140 * 120 * 24)
The total of all these is 26,845,378,560.
But if the assumption was that all 12 boys would participate, the answer would be just the 3,972,672,000 from the last case.
clearvars,clc
global group ct n
group=zeros(5,12);
for n=5:12
ct=0;
addon(1);
disp([n ct])
end
function addon(wh)
global group ct n
foundempty=false;
for psn=1:5
if group(psn,1)==0
foundempty=true;
end
for i=1:size(group,2)
if group(psn,i)==0
group(psn,i)=wh;
break
end
end
if wh==n
if group(5,1)>0
ct=ct+1;
if n==5
disp(group)
disp(' ')
end
end
else
addon(wh+1);
end
group(psn,i)=0;
if foundempty
break
end
end
end
Second thoughts:
When calculating the groupings of boys, the program calculated only 1 for each combination (of course later multiplied by the choice of boys and permutations of girls), such as when considering 8 boys, a grouping might be 1, 3, 1, 2, 1. This would count as only 1, or rather it would count as 5!/(3!*2!) as the permutations of the groupings were counted. However, it didn't count permutations within each group, so B3, B1B2B6, B8, B5B9, B10 was considered no different from B3, B6B2B1, B8, B9B5, B10.
So instead of counting only 1 for each such grouping a new version counts the product of the permutations of each of the five "entities" (groups or individual boys).
prms=1;
for jj=1:5
prms=prms*factorial(length(find(group(jj,:))));
end
ct=ct+prms;
Here are the results from 5 to 12 boys multiplied out by the other factors:
2280960
79833600
1437004800
16765056000
134120448000
724250419200
2414168064000
3793692672000
They add up to 7,084,515,778,560 -- over 7 trillion.
But if the assumption was that all 12 boys would participate, the answer would be just the 3,793,692,672,000 from the last case.
Even in an interpretation that all 12 boys must be included, it's over 3.7 trillion.
Sanity check: that's less than the 20.7 trillion if the 16 other people could sit anywhere around G1.
|
|
Posted by Charlie
on 2023-10-02 15:35:58 |
solution
