Divisibility Problem (not allowed to use independence)

[steady whale]

Original problem: what is the probability that nC7 is divisible by 12?
What I've done so far: rewrite nC7 as n(n-1)(n-2)(n-3)(n-4)(n-5)(n-6) (we will also have a 7! hanging out in the denominator). I then calculated the probability that this product is divisible by 2^6 and the probability that it is divisible by 3^3.

Ok sorry Techie and aL, but i know I was struggling to understand independence last night. I talked to the professor to get more of an explanation, and he said we are NOT allowed to use independence for this since we haven't learned it yet. Essentially, he said to calculate the union of it being divisible by 3^3 or 2^6 using smaller classes of modular arithmetic. I do not understand how to figure that out, because the only way that I know how would be to consider mod 3^3*2^6, which is a large number. He said that we can do it using smaller classes. Anybody have any idea (or a similar example) on how to do this?

[final palm]

1. Do not ping the Moderators, unless someone is breaking the rules.
2. Do not ping the Helper Moderators, unless there is a conflict between helpers.
3. Do not ping other members randomly for help.
4. Ask your question and show the work you've done so far. If you've posted a screenshot of a question, specify which part you need help with.
5. Wait patiently for a helper to come along.
6. If the Helper has answered your question, remember to thank them with the Mathematics Ranks bot and close the thread with:

+close
Feel free to nominate the person for helper of the week in #helper-nominations
If you're happy with the help you got here, and the server overall, you can contribute financially as well:

[boreal cipher]

I don't know what the fuck "we're not allowed to use independence" even fucking means. You don't "use" independence, events are or are not independent, and that changes the calculations whether you want it to or not.

[steady whale]

Once we get the two probabilities, we are not allowed to multiply them together

[boreal cipher]

Why the fuck not?

[steady whale]

Because that uses the fact that they are independent

as a justification for why we can do it

And yes I specifically asked if we could just multiply them together and he said no

[boreal cipher]

I think your professor is as confused as you are.

[steady whale]

he managed to do it without multiplying them

[boreal cipher]

How?

[steady whale]

Using the inclusion/exclusion principle

[boreal cipher]

No he didn't.

[steady whale]

he said we can calculate the union that the product is divisible by 2^6 and 3^3 using modular arithmetic

[steady whale]

that's what he told me

[boreal cipher]

"Using modular arithmetic" how?

[steady whale]

essentially I said ok, so we'd have to consider mod 2^6*3^3? and he said that we could consider a smaller number, like mod 8 or mod 16, as long as it works. he said to play around with it and i'd figure it out. obviously he has too much faith in me

[boreal cipher]

What the hell is mod 8 or 16 going to tell you about divisibility by 3?

[steady whale]

beats me. i know from backwards deduction that 24 is the magic number. i just don't know why

[boreal cipher]

How do you know that?

[steady whale]

Because they're independent, i multiplied the two probabilities together to get what I want to find. Then I used the inclusion-exclusion principle to figure out what the union would have to be to use that principle, and it has to be 23/24

[boreal cipher]

Because they're independent
Then why are we still talking about it?

[steady whale]

Again, because we are not allowed to use that assumption to multiply the two numbers

You seem so set on using that when my professor said we cannot. We MUST use the inclusion exclusion principle.

[boreal cipher]

Then you can't assume the conclusion you reached by doing so.

[ashen talon]

Quick question because I didn't follow your previous posts so I don't understand what's going on: where is the randomness in the statement "nC7 is divisible by 12" ? Is n a random variable?

[boreal cipher]

Yes.

[ashen talon]

how is it distributed?

[boreal cipher]

n is a random natural number.

[steady whale]

he said, yes, they're independent, but you can't use that assumption bc we haven't learned it. so i told myself that we know they're independent, so the easy way would be to multiply them. so i calculated the correct answer using that we know they're independent, but since i want to find it using a different method, i tried to figure out how to make it work

it's like when you're learning about derivatives and have to use the limit definition - you can use the tricks to figure out what it should be, but you have to get to that number using the limit definition

[boreal cipher]

That's stupid, you have learned how to calculate joint probabilities of independent events, that's literally all you've learned.

That's pretty much literally the first thing any probability course teaches you.

[ashen talon]

I still don't follow, but perhaps instead of using independence to conclude P(A and B) = P(A)P(B), you could use P(A and B) = P(A) + P(B) - P(A or B)

then maybe you'll magically find that this is in fact equal to P(A)P(B)

[boreal cipher]

And where does P(A or B) come from?

[steady whale]

thanks! that's what I'm trying to figure out how to get P(A or B)!

[ashen talon]

again, I didn't follow what was done before, I did ask but no one answered

I was just trying to propose an alternative to using P(A and B) = P(A)P(B)

[ashen talon]

What are your events A and B in your case?

[steady whale]

thank you! yes, considering the union is the strategy we are supposed to use, I am just having a hard time figuring out exactly how

[ashen talon]

Also, again, how is n distributed?

[boreal cipher]

nC7 is divisible by 3 and nC7 is divisible by 4 and it's just a uniform natural number.

[ashen talon]

there is no uniform distribution on N

[steady whale]

Event A: n(n-1)(n-2)(n-3)(n-4)(n-5)(n-6) is divisible by 2^6
Event B: n(n-1)(n-2)(n-3)(n-4)(n-5)(n-6) is divisible by 3^3

Distribution: if we randomly select a natural number

[boreal cipher]

Then the probability is the limit of the ratio of whateverthefuck

[boreal cipher]

I think you are vastly overestimating the amount of formal rigor in this problem. Though I can't blame you, considering we're arbitrarily not allowed to use literally the first thing you learn in probability.

[steady whale]

I get that you're not happy with the problem. That's totally understandable. But, we can either get mad at the problem or try to figure out ways to use what we are allowed to. I'm trying to do the second route

[boreal cipher]

I mean, by the same logic you aren't allowed to use modular arithmetic because you haven't been taught it.

[ashen talon]

then probably outside of my area of expertise, I'll sleep on it (literally, it's late here) and get back here if I do find a somewhat convincing answer

[steady whale]

ty! it's complicated for sure just trying to the best with what im given

[steady whale]

his reasoning is probably that we can only use the probability tools we have been tought. external topics are fair game. idk man. im just doing what im told

[meager nebula]

nC7 right

@steady whale can we use just case work

[steady whale]

yes! sure, sounds good

[meager nebula]

if its divisible by 12 let's start with divisibility by 4

after that we will look at 3

[steady whale]

ok 🙂

and then look at 4 U 3?

[meager nebula]

we don't step into "probability theory" till the end

this is a number theory problem

[steady whale]

gotcha

[meager nebula]

@steady whale let's go over powers of 2 now

[steady whale]

ok!

[meager nebula]

case 1:
n=2m (it's even)

[steady whale]

yes!

[meager nebula]

as we only care about the powers of two we can ignore odd things and write

(2m)(2m-2)(2m-4)(2m-6)/(2x4x2)

[steady whale]

i did calculate divisibility by 4 and i got 13/16 btw

[meager nebula]

the bottom comes from :
2 gives us a 2
4 gives us a 4
6 gives us a 2

[steady whale]

where does the top come from

[meager nebula]

n(n-1)(n-2)...(n-6)

[steady whale]

oh i see

[meager nebula]

as n is even we ignore n-1,n-3,n-5 as they are odd

don't have anything to do with powers of 2

[steady whale]

but there's a chance we only have 2m(2m-2)(2m-4) and not a 4th term

[meager nebula]

why

[steady whale]

if n is odd, we only have 3 even terms in the numerator

[meager nebula]

correct but i assume n to be even here

[steady whale]

and then we'll handle the case when n is odd later?

[meager nebula]

yes we will

[steady whale]

ok

[meager nebula]

you even got the method right

so simplify our "even" product

[steady whale]

yes, if n is even it is guaranteed that it is divisibe by 4

[meager nebula]

2^4 m(m-1)(m-2)(m-3)/2^4

now moving onto odd n

write n=2m+1 and you can easily deduce that we need 8 to divide m(m-1)(m-2)

[steady whale]

i did it slightly differently but go ahead

[meager nebula]

can you figure out when 8 divides it?

well atleast one of these will be even clearly so we get a 2

but that's not enough

well we could get two 2s at the both ends

still not enough

[steady whale]

right so we have to have a multiple of 4 in there

[meager nebula]

how could we fit more powers of two in that small 3-wide space?

we can get a 4 and a 2

[meager nebula]

yes

[steady whale]

yep

[meager nebula]

but there's a catch

it has to be at the ends, if it's in the middle (i.e. 4|m-1) then it doesn't work

you can see why

[boreal cipher]

That actually is exactly enough.

[steady whale]

i actually don't know why that is

[meager nebula]

we have a 2 below that I didn't write

[meager nebula]

of m-1 is a multiple of 4 (then it's even) what can you say about m and m-2

[boreal cipher]

No, we want a factor of 8 in m(m - 1)(m - 2), right?

[meager nebula]

yeah

[boreal cipher]

And if m and m - 2 are both even, then we have it.

[steady whale]

they're odd

[boreal cipher]

Because they're consecutive multiples of 2, meaning one is a multiple of 4.

[meager nebula]

ok that does work i didn't see it

[meager nebula]

so we only get a multiple of 4 there

[steady whale]

that's true

[meager nebula]

that's not enough so if the middle is ever even then it has to supply the powers of 2 by itself so it has to be a multiple of 8

[steady whale]

👍

[meager nebula]

now as techie pointed out, if one of the ends are even then that also works

[boreal cipher]

Er, wait, why do we want a multiple of 8, rather than a multiple of 4?

[meager nebula]

because for odd n we had (2m+1-1)(2m+1-3)(2m+1-5) uptop

[boreal cipher]

Oh, I see. We're focused on the numerator in the case of odd n.

[meager nebula]

that was the even part

[meager nebula]

yeah

[boreal cipher]

Right. There's been a lot of confusion in this problem over whether we're focused on the numerator or the quotient.

[steady whale]

i've always been looking at the numerator

[meager nebula]

recompiling our findings :
the thing is divisible by 4 if and only if n is

• even
• of form 4k+1 or 16k+3

i might have missed a case wait

it's okay nvm

so if the thing is divisible by 12 we have to have n of this form already

no let's look at divisibility by 3

[steady whale]

ok

[meager nebula]

the denominator gives 3^2
the numerator needs to have atleast 3^3 here. As there are 6 consecutive numbers atop, there are atleast two consecutive factor of 3 there

is this correct

[steady whale]

yes!

[meager nebula]

if there are 2 consecutive factors of 3 can we say (following a similar argument as techie used for powers of two) that there is a multiple of 9 there as well?

[steady whale]

with probability 2/3 right?

[meager nebula]

we can't do that this time as it could be "3 and 6"

[meager nebula]

we are not going to into probability yet

[steady whale]

ok

[meager nebula]

If any one of n, n-1,...,n-6 is of form 9k i.e. n=9k,9k+1,...,9k+6 then it works because we get a multiple of 9 and there will be atleast another multiple of 3 anyways. Let's look at 9k+7,9k+8 now. If n=9k+7 then uptop we get
(9k+7)(9k+6)(9k+5)(9k+4)(9k+3)(9k+2)=3^2 [(9k+7)(3k+2)(9k+5)(3k+1)(9k+2)]
can the expression inside the [ brackets ] have a factor of 3?

@steady whale

[steady whale]

id like to say no

[meager nebula]

why

[steady whale]

bc for each factor, you have a multuiple of 3 added to a non multiple of 3

[meager nebula]

Now if n=9k+8 then uptop we have by a similar logic,
(9k+8-2)(9k+8-5)=(9k+6)(9k+3) and again it doesn't work

so the only thing that work are n=9k,9k+1,...,9k+6

[steady whale]

how do we know that all of them from + 0 to + 6 work

[meager nebula]

because you'll hit some 9k

and there ought to be another multiple of 3

for example let's take 9k+4

you get a multiple of 9 at (9k+4-4)

and (9k+4-1) is also a multiply of 3

so you get 3^3 atop as wanted

[steady whale]

oooohhhhhh

ok

[meager nebula]

now we want to take the intersection of the sets :
{1,2,3,4,5,6}U{8,10,12,14,...}U{9,13,17,21,...}
and,
{1,2,3,4,5,6}U{9,10,11,12,13,14,15,18,19,...}

the first bit is because nC7 is 0 for n<7 I assume

[steady whale]

ok i need a few minutes to think about it

[steady whale]

yeah i believe its 0 for n from 0 to 48

[meager nebula]

i missed the 16k+3s crap

[steady whale]

oh wait that was a different problem

[meager nebula]

no it's only 0 for n from 1 to 6

[steady whale]

8c7 is 8 lol

[meager nebula]

for 2,
n=2k,4k+1,16k+3
and for 3,
n=9k,9k+1,...,9k+6

let's go one by one

[steady whale]

wait, did we ever consider the option that n is odd for the 3? then we're guaranteed to have a 9 in there

[meager nebula]

Take n=9k+7

we didn't make even/odd cases for 3 we made modulo 9 cases

[steady whale]

i thought that was only if there were 2 multiples of 3 in there

[meager nebula]

come again?

[steady whale]

we only considered the option that there are exactly 2 consecutive factors of 3, right?

[meager nebula]

it's not an option

you have a 6-wide slider, there will always be exactly two factors of 3 in this

[steady whale]

we can either have 3 consecutive factors of 3 or 2 consecutive factors of 3

[steady whale]

we have a 7 wide i thought?

[meager nebula]

wait what's

i forgot

[meager nebula]

yes we do

[steady whale]

n(n-1)...(n-6)

[meager nebula]

still the same

it's 7 wide

but can't we have 3k,3k+3,3k+6 this is exactly 7 wide

[steady whale]

ya

[meager nebula]

do we really need this

we already went over all possibilities modulo 9 right

[steady whale]

that's what's been confusing me the last few days

[meager nebula]

if n=9k,9k+1,...,9k+6 that readily works

9k+7,9k+8 don't work

these are all the possibilities

[steady whale]

that does work, but im not sure that's all of our options bc they don't necessarily need to be in the form of 9k + m

[meager nebula]

it does

[steady whale]

even if there's 3?

[meager nebula]

what do you mean exactly

[steady whale]

oh i guess that's true

[meager nebula]

A number must have a remainder when divided by 9 right?

[steady whale]

yeah that is true

[meager nebula]

if it has a remainder r then it's of the form 9k+r

[steady whale]

ok so how come we had to break it into cases for mod 4 but not for mod 9

[meager nebula]

it always has a remainder btw

[meager nebula]

because this method isn't generaliseable

you can look over the work again

I'm not saying this is the only method

but here we just did what was convenient

[steady whale]

yeah. i guess that's what im having a hard time with. to me it feels like a random guess if we have to break it into cases or not

[meager nebula]

now find the intersection of these

[meager nebula]

I explained my thought process clearly didn't I?

[steady whale]

yes

[meager nebula]

can't really learn that I think it comes with practice

[steady whale]

here's what im referring to. we cosidered the case when n was even and when n was odd. i don't see how we don't have to do that for 3

[meager nebula]

we don't have to because it just worked by assuming cases modulo 9

if it didn't work then I'd have done something else

[steady whale]

uh oh i feel a circle of confusion coming on 😭

[meager nebula]

Okay here's the deal

[steady whale]

i am very much aware of that. i am trying to determine for myself when i can use that without having to ask for help each time 🙂

[meager nebula]

there might have been a way to do the work for powers of 2 similarly with some carefully chosen modulo

[whole elbow]

this again

[meager nebula]

but it just worked without it

[steady whale]

only bc your method wasnt permissable lol

[meager nebula]

so i rolled with it

[steady whale]

oh gotcha ok

[meager nebula]

was it wrong?

[steady whale]

aLs was not permissable (but it was correct)

[meager nebula]

what is this the 1800s?

[steady whale]

hahahaha

[meager nebula]

you do whatever you want to noone decided what's permissible

[steady whale]

my professor told me

that i could not use that method

[meager nebula]

anyways now find the intersection

[whole elbow]

did he elaborate on the use of 3^3 or 2^6?

[steady whale]

yes! he said we could find the union using smaller classes

[meager nebula]

ask your professor to give you a problem that actually requires you to use probability theory rather than force you to make a probability argument at the end and be fine with it

[steady whale]

so im finding the intersection of this?

[meager nebula]

begs the question whether discrete probability is combinatorics or not

i won't get into that

[steady whale]

lol he wanted us to use inclusion/exclusion principle

[meager nebula]

i missed the 16k+3 there

[meager nebula]

find the intersection of :

{2k,4k+1,16k+3 | k=0,1,2,...} and {9k,9k+1,...,9k+6 | k=0,1,2,...}

or in this case find the probability that some number is in both sets

[steady whale]

Oh boy. Do I compare element by element and determine which ks work for each of them?

[meager nebula]

could. should? no

[steady whale]

so this must be what he was talking about for finding smaller classes

[meager nebula]

wdym

[steady whale]

got to find another modulo that encapsulates both of them

[whole elbow]

huh, crt?

[meager nebula]

he allows crt

?

[steady whale]

he pretty much said we can find the union by finding a modulus like 8 or 16

what is crt

[meager nebula]

Chinese remainder theorem

[whole elbow]

nevermind

[steady whale]

never heard of that

[whole elbow]

you will

[meager nebula]

it's propaganda

[meager nebula]

do you have the answer for this problem?

[steady whale]

I know what it should be, I don't know how to get there

[meager nebula]

happens

[steady whale]

i haven't taken number theory before 😦

[meager nebula]

Try going case by case I'll check back on 90 minutes

[steady whale]

would I do 9 * 16 for my modulus and go from there?

[meager nebula]

you can try it

[steady whale]

like compare two of the formulas and find a k that works for both of them?

[meager nebula]

in the first set we have :

0 modulo 2 or,
1 modulo 4 or,
3 modulo 16

how do you combine em?

[steady whale]

id assume we could look at mod 16 and see how many numbers fit each of them

[meager nebula]

hint : look at {0,1,2,...,15}

[meager nebula]

yes 16 works

[steady whale]

so we know it needs to be 3 mod 16 - so for mod 4, we can only have -1 if im looking correctly

2 isnt possible

[meager nebula]

Is it {0,1,2,3,4,5,6,8,9,10,12,13,14}?

[steady whale]

there is no intersection if I understand correctly

[meager nebula]

intersection in the sets for 2? we care about their union

[steady whale]

oooooooh union

ok

[meager nebula]

which I think is this modulo 16

recheck it ofc

[steady whale]

i dont see how 1 works

[meager nebula]

from 4k+1 for k=0

[steady whale]

i forgot about zero smh

ty

[meager nebula]

k=0 or k=16 maybe

4k has to be of form 16m for us to get a 1 out of this

let's try 17

4*4+1

[steady whale]

ok after further thought i agree

[meager nebula]

we get : 16,14,12 there we needn't look further

you could even go through all of these again and verify manually

[steady whale]

wdym we get 16, 14, 12

[meager nebula]

17(17-1)(17-2)...

we get these uptop

[steady whale]

oooooh so now we're focusing back on top gotcha

[meager nebula]

takes care of the powers of 2

does it work with 3

we don't know yet because this is the union of cases for 2 not 3

[steady whale]

so should i find the intersection of the 3s first

UNion

sorry

[meager nebula]

combine these again

here's how to do it

to find the smallest modulo via which we can convey the information already present is the smallest one where we can fit a whole number multiples of these existing modulos

i.e. try to get the smallest number that can be broken up into 12 bits and 9 bits both

[steady whale]

remind me where the 12 comes from?

also i know im not getting this very fast but im super grateful that you're sticking with me

[meager nebula]

then work modulo that and see when the two collide

[meager nebula]

because for 2 we combined things into modulo 12

oh sorry

[steady whale]

gotcha gotcha gotcha

[meager nebula]

@steady whale it was 16

not 12

I've been saying 12

[steady whale]

ok yeah that's what i thought

so we want modulo 144?

that checks out with what the answer is

[meager nebula]

yes 9*16=144

[steady whale]

ok. but we can use some inherent information that every 16 for 2s it has a repeating pattern, and every 9 for 3s it has a repeating pattern?

[meager nebula]

yeah its supposed to have a repeating pattern

that's how modulos work

by the way is the answer

[steady whale]

ok that sounds fantastic! I think I have an idea of where to go now. I'll leave this thread open for a bit in case i run into issues, but i will try to take it from here. you're amazing tysm and you will get my one gau that I have 🙂

[meager nebula]

91/144?

[steady whale]

YES

whoaaaaaaa

[meager nebula]

notice how 91 = 7*13

can you see anything probability-like here

[steady whale]

7 * 13...

waitttttt

i seee it

[meager nebula]

(7/9)(13/16)

yeah

[steady whale]

yessssss

that's so cool

im intrigued

[meager nebula]

it's not a coincidence

[steady whale]

yeah, it's because of the independence 🙂 (which we cant use :()

[meager nebula]

that sucks

[steady whale]

right

[meager nebula]

good luck writing our 144 numbers

[steady whale]

i have faith in myself

[meager nebula]

(you'll notice a pattern you won't have to go past 30 at worse)

[steady whale]

i can do mundane

[steady whale]

ooooohhhhh sounds good tysmmmmmm

[meager nebula]

now back to the 90 minutes i used

my chemistry isn't looking good

[steady whale]

nooooo im so sorry

if it makes you feel bettter i have a few assignments due in an hour

physics isnt looking great for me rn

[meager nebula]

i did it out of my own will and it helped me recall a bit of number theory so don't say that

[steady whale]

im strongly considering taking number theory after this

but it would have to wait until next year

[meager nebula]

or you could also read a book on the side

[steady whale]

i could but that would be challenging for me

im already pressed on time

[meager nebula]

did you progress on the combinatorics book yet?

[meager nebula]

try cutting out some sleep

normal for college students

[steady whale]

i've been getting 2/3 hours a night

[steady whale]

no im so behind ive been having to turn in unfinished hw

[meager nebula]

🙏

I'm not religious but bless you

[steady whale]

tyty. i have mental conditions that makes it so i take longer to do ordinary things so i just have to deal with it

also how do i give you my gau

[meager nebula]

just do +close and read through the text it has the information

we get gau from the government

[steady whale]

If it’s ok I’ll leave it up for a bit until I’m able to finish the problem. Should be tomorrow at some point

[steady whale]

I just got my first ever gau today!

[steady whale]

sorry to bug you again, but i'm wondering how you deduced that. i tried writing it as (2m+1 (2m)(2m-1)(2m-2)... and then multiplying all 7 factors, but that just gave me a big polynomial lol

oh i just saw why so sorry for the ping

[steady whale]

ok, so in this case I get that we need something of the form 8k + 2, but that wasn't what we determined we needed. Did I do something wrong?

[meager nebula]

we need m of the form (at the middle) 4k to get 8k in the middle

[steady whale]

this is what i ended up working out - does it look right?

yeah i think im doing something wrong

that 1 in image 2 should be a 2

[meager nebula]

is this the for correction? assuming that sthick is the one

[steady whale]

yes

haha yes

[meager nebula]

we saw that just making k even put everything else in place so do that

why didn't you write the proof yesterday

[steady whale]

bc i had assignments due at 12am and we were talking at 11pm

[steady whale]

yeah that's what i wast trying to do, but rn i only have so far that n can be of the form 2k or 16k + 3, so I was trying to figure out how we got the 4k+1 in there

[meager nebula]

if i remember it was when we were accounting for odd n, with powers of 2 in mind

[steady whale]

oh yes, that is what it is. so we have n odd, and the outer two of the 3 terms are even, so we have to get one that's a multiple of 4 and one that's a miltiple of 2. Still not quite sure how the 4k+1 got in there

[meager nebula]

try scrolling up my vision is limited for atleast 15 minutes rn

[steady whale]

oh i did scroll up and read everything back. it looks like you figured out what the forms had to be and i just accepted it to get the big picture. no worries if you need some time. sorry that your vision is limited 😦

[steady whale]

ngl i did the unthinkable and chat gptd where the 4k+1 came from and chat gpt had no clue 😦

i guess i'll try with 8k + 1 instead and see if that works out

oh i figured it out

thx for your patience lol

[steady whale]

+close

[brittle rock]

Please thank your Helpers before closing!

Please thank the helpers who assisted you by clicking the buttons below. You can thank each helper only once. Once you're done, click "Close Post" to close this thread.

[brittle rock]

Thank you for your feedback! coffey has been awarded 1 . They now have 39 . They have 3 daily left for today.

[brittle rock]

Thank you for your feedback! aL has been awarded 1 . They now have 851 . They have 3 daily left for today.