33tapan.. how u got 10/32 batao naa.....
mere se nahi ho raha lagta hai :(
Two integers are multiplied. What is the probability that their product is a multiple of 8
Then generalize for 2n.
-
UP 0 DOWN 0 2 29
29 Answers
33
21actually nihit n me had da same dbt!! {the obvious one ! [3] }
jabardast SIR!!!
GOT IT now!!
gr8 soltn!!!
62hmm..
for the number to be divisible by 2n it can be any multiple of 2n
which comes once in every 2n numbers..
Hence the probability is 1/2n
The second and more non trivial question is .
Probability that the highest power is exactly n and above is given by 1/2n+1
Can you figure this one now?
3nishant sir...b4 i ask my doubt...thank u 4 a wonderful solution !!
actually i was trying to solve it on very similar lines, but i could not get two lines from ur ans :
Probability that the highest power is n and above is given by 1/2n
Probability that the highest power is exactly n and above is given by 1/2n+1
hehe..its funny actually, i didnt get the 'obvious' ones only !!
62Now I will give an expression taht I got for this question....
My solution is slightly different from Prophet's
We have to take 2 numbers.
First number can have a highest power of 2.
This power can go from 0 to n and beyond.
Probability that the highest power is n and above is given by 1/2n
Probability that the highest power is exactly n and above is given by 1/2n+1
These two are kind of obvious. But then as they say what is obvious to me might not be obvious to you. So if it is not, do ask! ;)
Now the probability that the product of the two numbers is divisible by 2n is given by the summation over r of
probability that the first number is divisible by 2r and not 2r+1 and the 2nd is divisible by 2n-r
Here we will club all p's when p is greater than equal to n.
SO the total probability is givenby
the probability that the first number has highest power r and that the product with the 2nd is divisible by 2n is given by ....
1/2r+1 x 1/2n-r = 1/2n+1
Hence total probability is givenby summation of the above when r goes from 0 to n-1 + the probability for the extra case when the first number is divisible by 2n
r ( 1/2n+1 ) + 1/2n
P= 1/2n x (r/2+1)
We have calculate for n=3.. ie when we find divisiblity for 23 = 8
where we did get 1/8(3/2+1) = 5/16 :)
cheers :)
62Awesome..
It needed the prophet to come to solve this one :)
I guess we could also have looked at the Binary expansion of a number! This was my guess when I looked at this question.. May be we cannot.. But my gut feeling says that we can.
last n digits being zero means that the number is divisible by 2k
so to find if the product of 2 numbers is divisible by 2n we need that the sum of the zeroes of the two numbers intheir binary representation becomes greater than equal to n!
I think this can be completed with proof. It makes thinking easier... atleast to my mind....
21Sir, aapka solution hai to samjhne mein do teen din to lag jaenge.... [12][12][7][7]
par i'll 2 crack it soon (HOPEFULLY) HA HA HA....
still chewing upon ur thot process
341i think it gives us a good framework for nishant sir's second question too. There will be two cases, n being odd or even.
When n is odd:
Every number is of the form 2n, 2n±1, 2n±2,..., 2n+2n-1
This is needed as we have a basis for saying that every number is equally likely to fall into one of these slots.
Our first task is to identify, among these which are at most divisible by 2,4,6,...
Denote the number of members of this set, that are at most divisible by 2k by sk
We have sk = [(2n-k-1)/2]+1
Now, to count the number of favourable cases.
We of course have 2n+1-1 cases for at least one of the numbers being of the form 2n.
Then we have the one case when both numbers are of the form 2n+2n-1
Now, if one of the numbers is divisible at most by 2, the other has to be of the form 2n+2n-1 which gives two cases
If one of the numbers is divisible by 4, the other can be divisible at most by 2n-1 or 2n-2
Which gives the numbers of cases as 2(s2+s2*sn-2)
and so on till 2(n-1)/2 where the number of cases as 2[s(n-1)/2(1+sn-2+....+sn+1/2]
Adding up these gives us the number of favourable cases.
Case 2: when n is even. Pretty much the same pocedure except we have to look out for when we are dealing with numbers that are at most divisible by 2n/2, not to count the case when both numbers are of that form twice.
341oh! i thought it is related to the same qn, so my answer was in that context i.e. when the number is obtained by the product of some two integers.
in that case you are right of course
21and the questn here is : WHat is tthe probability that an integer is divisible by 8 but not 16.?
its not relating nethin related 2 product of 2 integers... [12] [7]
21PROPHET SIR,
can u pl. pt out da flaw in this method : any no. div by 8 will be 8k,
now if k is even the no. is div by 16 as well else not!!
coz by this meth ans cums 2 b 1/2
341that should also easily settle tapan's qn, whats the probability that the integer formed this way, is not a multiple of 16, but is a multiple of 8.
Cases (2) and (3) are immediate contributors giving 4 favourable cases. Case (4) does not qualify
Case 1 needs one of the integers to be odd, so it gives 8 favouravle cases.
So of 20 cases, 12 are favourable. So that the prob is 3/5.
341I read the posts in this thread and the related one for div by 12. I think the sample space is an issue. It is not very clear that the probability in the sample space {1,2,...,12} (this was one of the arguments in the other thread) will hold over the set of all integers.
One of the ways to organize the sample space in this problem would be to state that every integer is of the form 8k, 8k+1, 8k+2,..., 8k+7.
Thus, considered modulo 8, we have 8X8 = 64 possibilites.
The favourable cases:
(1) At least one of the numbers is of the form 8k = 15 cases
(2) One is of the form 8k+2 and the other 8k+4 = 2 cases
(3) One is of the form 8k+6 and the other 8k+4 = 2 cases
(4) Both of the form 8k+4 = 1 cases
giving 20 favourable cases and hence the probability of 20/64.
21DUDE YEH POST PADH LO.... I HAV PUT UP MA ENTIRE SOLUTION THER....
READ THE ENTIRE POST!!!
http://targetiit.com/iit_jee_forum/posts/19_02_09_divisible_by_12_2688.html
DO SIMILARLY 4 16
21i m not sure,
jus thot that any no. div by 8 will be 8k,
now if k is even the no. is div by 16 as well else not!!
21WHat is tthe probability that an integer is divisible by 8 but not 16.? ans = 1/2 ?? [7]
62it is slightly above that level.
You have to think in terms of the hint that I have given.
I dont know how good that hint was.
Another Hint:
WHat is tthe probability that an integer is divisible by 8 but not 16.?
WHat is tthe probability that an integer is divisible by 2n but not 2n+1?
24can this come in JEE this year?????or is it above that level........[7][7]
21hmmmm... yah! actually i ve bn solvin this type of sums wid case-counting method so its tuff 2 generalize frm ther on....
this shall b an interestin approach!!!
62well manipal and tapan .. (Hint)
we take some cases..
first number is a multiple of 2n
first number is a multiple of 2n-1 but not 2n
first number is a multiple of 2n-2 but not 2n-1
and so on...
FInally take the sum for all these probabilties
11tapan i m really confused about these ques
please explainevery step in detail
21for n=1;
P = 3/4
for 22
P = 1/2
n=3 ==>
P = 5/16
kuch banta hai kya???
21[12]
I guess rkrish's method in divsiblity by 12 shall help 2 generalize...