In how many ways can 8 different numbers can be chosen from the first 49 positive integers such that the product of these numbers is divisible by 8?
Only even numbers can contribute factors of 2 into the final product. The even numbers between 1 and 49 are listed with the number of 2's contributed as factors:
2 1
4 2
6 1
8 3
10 1
12 2
14 1
16 4
18 1
20 2
22 1
24 3
26 1
28 2
30 1
32 5
34 1
36 2
38 1
40 3
42 1
44 2
46 1
48 4
Of the 8 chosen numbers, some can be odd and some can be even.
For example, in the table below, for 1 odd and 7 even, there are 25 choices of odd number and 346104 choices of the 7 even numbers. All 346104 choices of even number work, as any 3 would work by themselves. Combining the choices of the even number and the odd numbers, there are 8652600 ways altogether that include 1 odd and 7 even numbers.
Only when we get down to, say, 6 odd numbers and 2 even numbers, do the "ways that work" differ than the overall choices for even number, where only 210 of the 276 possible combinations of 2 even numbers work to produce a multiple of 8.
number of choices choices even choices total
odd even for odd for even that ways that
numbers numbers numbers numbers work work
0 8 1 735471 735471 735471
1 7 25 346104 346104 8652600
2 6 300 134596 134596 40378800
3 5 2300 42504 42504 97759200
4 4 12650 10626 10626 134418900
5 3 53130 2024 2024 107535120
6 2 177100 276 210 37191000
7 1 480700 24 6 2884200
8 0 1081575 1 0 0
The sum of all the total ways of getting a multiple of 8 is 429,555,291.
Compare that with the C(49,8) = 450978066 ways of choosing the 8 numbers altogether and the probability that the product will be a multiple of 8 is 0.952497079979938, or about 95.25%.
For verification:
ct=0;
for trial=1:1000000
n=randperm(49,8);
p=prod(n);
if mod(p,8)==0
ct=ct+1;
end
end
ct/trial
finds
0.952516 as that probability via simulation.
The two tables were produced by:
clearvars
ct=0; cList=[]; nList=[];
for n=1:49
f=factor(n);
s=sum(f==2);
if s>0
disp([n s])
ct=ct+1;
cList(end+1)=n;
nList(end+1)=s;
end
end
ct
ct=0;
idx=combinator(length(nList),8,'c');
for i=1:length(idx)
row=nList(idx(i,:));
if sum(row)>=3
ct=ct+1;
end
end
ways=0; totnon=49-length(nList);
for non=0:8
w=nchoosek(totnon,non);
w2=0;
idx=combinator(length(nList),8-non,'c');
for i=1:length(idx)
row=nList(idx(i,:));
if sum(row)>=3
w2=w2+1;
end
end
fprintf('%2d %2d %10d %10d %10d %10d\n',non,8-non,w,nchoosek(24,8-non),w2,w*w2)
ways=ways+w*w2;
end
num2sepstr(ways)
|
|
Posted by Charlie
on 2024-07-20 10:25:31 |
solution
