Yes
#discrete-math
burnt fractal
any math gradautes can help me put a really hard word problem into an equation?
vale cairn
What's the problem?
junior sky
I am a little confused with this example. We are told some are done wrong but the syntax is right. Was this done right? i thought the set should be in coloration to {K + 'J of k'}
its in relation to where the red arrows are
remote sentinel
any math gradautes can help me put a really hard word problem into an equation?
possibly, depending on whether or not it can actually be put into an equation (like cos often ambiguous interpretations can arise from the order you choose to apply the operatons; the rules of bidmas cannot be applied to semantic language, because it's not math. just a syntactical representation of it, which doesn't necessarily have to adhere to its rules.
tulip sundial
Couldn't figure this one out, Also you need to find a variable of x that makes P true. I am so lost, thanks anyways
faint narwhal
Can you tell me what subset means?
tulip sundial
it means that every element of set A is also an element of set B, i think
faint narwhal
Right, so can you try to show that for this question?
tulip sundial
How would i form the answer, since this isnt much like propositional or predicate proofs
or would it be similar
pale epoch
consult your notes on definitions
its probably the complete graph on 8 vertices, path graph on 5 vertices and cycle graph on 11 vertices
fresh venture
its probably the complete graph on 8 vertices, path graph on 5 vertices and cycl...
Ok
But I checked already
There are too many possible figures ig
opal belfry
what would the result be if infinity * 0 be? because 0 times whatever number is 0 and infinity times whatever number is infinity
fresh venture
It's indeterminant actually
Neither 0 nor infinity nor even <not defined>
Total 7 such expressions exists
stoic lotus
does someone know what the class of an element is
and what the quotient set is xD
Like, I understand the concept of class and of quotient set
but I dont understand why the class of X is {x,1-x} and not also {x,x} and like, why is it expressed that way
I understand how it can be expressed afterwards as {[1], [2],...} but I dont get the first step
ó means "or"
pale epoch
$x + (1-x) = 1$, so $x^2 - (1-x)^2 = x - (1 - x)$ and therefore $x,R,(1-x)$
vital dewBOT
Lochverstärker
fresh venture
Anyone knows the clique number and independence number of c11 graph?
weary tiger
uhh it should be pretty obvious if you understand the definitions
so ask about those if you don't understand them
fresh venture
I know the definitions but idk how c11 looks like
weary tiger
how do you define c_n
fresh venture
Cycle
weary tiger
like do you know how c3, c4 look like
fresh venture
Yeah kinda
weary tiger
wdym kinda
fresh venture
So what 11 clique number for c11?
weary tiger
what is clique number of c4?
fresh venture
Hmm... 4 vertices ...
weary tiger
what is clique number?
weary tiger
Yeah Im asking about a definition
fresh venture
It's a subset of vertices
weary tiger
that's what I was saying at the very beginnning, you seem like you don't know the definitons
fresh venture
Which are not adjacent
weary tiger
no
its the cardinality of maximal subset of set of vertices such that all edges are connected
fresh venture
So C4 has 4 clique right?
fresh venture
4 edges
fresh venture
that would mean that all the vertices are connected with each other
Ohh so 2
fresh venture
what would it be for, lets say c3?
0
weary tiger
why
fresh venture
C11 is a normal 11 side polygon type right?
weary tiger
yes
fresh venture
So if we need to join the edges with maximal number of vertices....
weary tiger
what, no
you said at beginning you get the definitions, you don't but ok let's look at examples
fresh venture
I got it but Idk how to apply
weary tiger
no you dont
clique number is the biggest subset of vertices, such that in this subset every vertex is connected with every other one
fresh venture
That's why I started with questions to know how to apply
weary tiger
but you couldnt give me the definition and jsut saying random stuff
fresh venture
clique number is the biggest subset of vertices, such that in this subset every ...
So for example c11 there are 11 vertices
If we connect them all there would be around 10+9+8...1
55
weary tiger
...
weary tiger
clique number is the biggest subset of vertices, such that in this subset every ...
So like, for a square if you take 2 adjacennt vertices, they are all connected. But if you take any 3, the 'opposite ones' are not connected by any edge (we dont ahve the diagonal edges)
fresh venture
So like, for a square if you take 2 adjacennt vertices, they are all connected. ...
Ok
weary tiger
therefore the clique number is 2, because this is the biggest number of vertices you can pick from the graph, such that they are all connected to each other
fresh venture
That's why it's 2?
weary tiger
for c3 (a triangle) it would be 3, because entire graph is connected (every vertex is connected to every other one)
figure it out for c11
fresh venture
Then it's 2 for all C5, C6 c7..... Right?
weary tiger
yes
fresh venture
Okk
weary tiger
onnly for c3 its 3, its a special case
fresh venture
Ok
U said C3 has 1
Nah u said minimum possible is 1
I got it wrong
Uk about independence number @weary tiger ?
weary tiger
?
weary tiger
yeah what about it
fresh venture
Like for clique u said how many were needed to join 2 adjacent vertices
What in case of independence number?
Does that mean for the C4 we find how many vertices are not connected to each other?
So answer becomes 2
weary tiger
yes
fresh venture
Ok
weary tiger
what would be the answer for c3 and c6?
fresh venture
Imagine hexagon
Then connect all the points to each other and disconnect previously connected ones
fresh venture
Ok
weary tiger
how many can you pick such that none of them are connected
it cannt be 7, there arenn't even that many vertices
fresh venture
ONLY AB BC CD DE EF FA RIGHT
Yep
weary tiger
so like if you pick the vertices A and C, they dont have annything in common
fresh venture
ONLY AB BC CD DE EF FA RIGHT
These are connected
fresh venture
Ohh okayy
Ig then there are 3 non connected ines
So for C6 ig independence no. Is 3?
weary tiger
yep
weary tiger
ye
weary tiger
you can try to come up with a general formula for C_n
so like a function that if you plug n it gives you the independence number for C_n
weary tiger
so lets say for C_6, that would give you 2.5 😛
but close
there is a 'floor' function that helps to do it
but if you dont know it you just consider even/odd case ye
fresh venture
Yeah
Clique is just 2 for all
And 3 for c3
Would clique still be 2 in case of Pn? @weary tiger
weary tiger
whats pn
fresh venture
Clique will still be 2 here ig
No difference
And independence is... Only 2 edges are not joined so it will be 1
weary tiger
no
rose cipher
Is Inclusion/Exclusion actually a good way to calculate number of primes less than n? Or is it just used as a way to help learn Inclusion/Exclusion?
rose cipher
uhhh wait I think they talked about that in another class but I forgot what that is, I was refering to how you can use the inclusion/exclusion alternate form like N(p1' p2' p3' p4') or whatever to calculate primes less than n
faint narwhal
oh, to calculate the number of primes
Yeah, this works. I'm not really sure what you mean by "good"
rose cipher
how efficient is it compared to other methods, out of curiosity?
faint narwhal
Uh well
You use inclusion/exclusion to get a formula
and you can rearrange that formula into something really nice
this essentially
And there are many ways other than inclusion/exclusion to get this formula of course
This formula is reasonably fast, but the problem is that you need to know the prime factorization of n
pale epoch
this is the number of coprime numbers (to n), not the number of primes less than n 🤔
faint narwhal
And the idea that there's no faster way to compute this euler phi function without knowing the prime factorization of n is kind of what RSA relies on
raw musk
Hi anyone here know lambda calculus?
weary tiger
Hey can anyone help with a combination problem?
last timber
iron marsh
Probably best to use nor to remove ambiguity.
So you can't be late nor can you smoke
But yes, you have the right idea.
past burrow
is it not "It is not the case you can be late or it is not the case you can smoke."
cuz that was my other idea
lofty cloudBOT
last timber
@fresh grove if asks for subset of A \cross B such that it could not be graph of any function
fresh grove
<@!702907583857688577> if asks for subset of A \cross B such that it could not b...
oh yeah but how do we do it isn't it any (x,y) y can be expressed in terms of x somehow
cerulean wind
oh yeah but how do we do it isn't it any (x,y) y can be expressed in terms of x ...
you know that a function must have a unique output for each input. try to break this condition.
alternatively, any function from A to B must be defined on all of A. you could also try to this condition as well
fresh grove
you know that a function must have a unique output for each input. try to break ...
okay lemme keep this in mind and try again thanks!
vital dewBOT
black_fires
sharp ledge
stray reef
jsut by sheer coincidence i explained this exact problem just now in #help-6. #help-6 message
dusky island
Let's say there are 6 numbered balls and they are randomly distributed to 4 containers which are identical. How many possible ways of distributing the balls are there when the order of the containers does not matter and the order of the balls does not matter.
I've tried to approach this with a few ways but it seems a bit more complicated than I first thought. Any hints?
vale cairn
If i'm interpreting it correctly, perhaps try a 'stars and bars' argument if you know what those are?
dusky island
I guess I can calculate every possibility by going through every option, (6), (5-1), (4-1-1), (3-1-1-1),(3-2-1) and so on, but I might be making things a bit too difficult
yeah the arrange and split method
vale cairn
Not heard of that precise term before, what's that?
dusky island
we don't use the stars and bars term in my native language, it's something like arrange and split or something. But I'll try it, thanks
vale cairn
oh sure, cool
dusky island
5 possible splitting points and 4 splitters. I think My best guess would be 4^6*ncr(5,1)*ncr(5,2)*ncr(5,3)*ncr(5,4). 4^6 for possible orders, ncr5,1 for one meaningful split, ncr2 for 2 meaningful splits
ah hmm so 3 possible splitters not 4.
cold saddle
For the discrete series given as, X variable values - 32 with frequemcy 2, 37 with frequency 5, 46 with frequency 3 and 48 with frequency 9, median is ___
Select one:
a. 48
b. 32
c. 46
d. 37
vale cairn
5 possible splitting points and 4 splitters. I think My best guess would be 4^6*...
Ah, that isn't stars and bars.
Maybe I can give you a hint of how that'd work if you'd like
stray reef
Let's say there are 6 numbered balls and they are randomly distributed to 4 cont...
are the boxes allowed to be empty?
if yes then this is the sixth Bell number minus 1 minus 6C2 to account for illegal partitions (ones that split into six or five sets respectively - more than we have boxes)
,w 6th Bell number
vital dewBOT
plush dock
Hey, sorry for the silly question. I'm struggling to understand how they arrived at the marked expression..
vale cairn
Factor out 1/(1-x)^5 from the preceding expression
vale cairn
Np
dusky island
@stray reef visualizations of bell numbers suggest that this is indeed a bell number problem, thanks!
tawny trout
hi small question to conffirm in thinking this right. so 2 is not an element of A={{2},{{2}}}?
if it was an element, would it be A={2{2},{{2}}}?
pale epoch
hi small question to conffirm in thinking this right. so 2 is not an element of ...
yes
tawny trout
thank you :)
pale epoch
if it was an element, would it be A={2{2},{{2}}}?
missing a comma?
tawny trout
yeah i think so
pale epoch
2 is an element of {2, {2},{{2}}}, not of {2{2},{{2}}}
tawny trout
thank you for clarifying that for me. Makes way more sense :)
pale epoch
👍
weary tiger
if u have thirty students and u have 3 groups, group A B and C and u have 12 in A 10 in B and 8 in C
to find the probability of two students being in the same group
would u just do something like
(12/30)(11/29) + (10/30)(9/29) + (8/30)(7/29)
or would u do that and then divide by like 30 Choose 2
or would it be like
[(12C2) + (10C2) + (8C2)]/(30C2)
tawny trout
so how do you determine if something is a function? I dont understand functions and how to determine if theyre functions
pale epoch
how did your class define functions?
tawny trout
Let A and B are non empty sets A function f from A to B, denoted as if : A->B, is an assignment of each element of A to an exactly one element of B
thats how my prof defined it
theres a question that goes "the function that assigns to each positive integer the largest integer not exceeding the square root of the integer.
We are supposed to find domain and range
I know the domain is {1,2,3,...} but is the range supposed to be square roots of that?
would the range be like {a,b,c,...} because for elements 1 2 and 3, it would be 1 for range, then when it's 4,5,6,7,8, it'd be 2? So we have to put the range as {a,b,c,...}?
elder berry
Domain is which numbers can you put in the function (which are the natural numbers) and the range are all the possible outputs. As you said 1 can come up multiple times, but we don't care how many times it does, we care that it indeed does appear (that it is a possible output), so that means every natural integer can also be the output of that function or {1, 2, 3, ...}
slate burrow
How does this diophantine equation have a solution?
There isn't any number that divides them both
2 divides 22 and 6 but not 19
elder berry
2 divides 22 and 6 but not 19
2 may divide x then, which would mean it's possible for there to exist a solution
faint narwhal
No
Something like 19x + 22y = 19 obviously has a solution for example
even though 2 doesn't divide 19
slate burrow
I mean in general, if you can't divide c then there is no solution no?
faint narwhal
I have no idea what you mean by that
Maybe you're saying that
if you want to solve ax + by = c, it must be true that gcd(a,b) divides c for there to be a solution
slate burrow
Trying to solve this equation, and i was wondering should i how should i write the last night?
tawny trout
Domain is which numbers can you put in the function (which are the natural numbe...
tyvm
slate burrow
nvm :D
brisk fox
in a lattice the join of two elements is defined as sup{a, b}. Why is it not just max{a, b}? Is it because it's possible that they aren't comparable, since it's on a poset?
faint narwhal
Yes thats right
brisk fox
ok thanks, I've been wondering about this for years
proud totem
needing some help on this problem
digital quail
worthy mist
needing some help on this problem
do you have any idea how to approach the proof in the first place?
proud totem
ngl not really. These proofs for this class are really stumping me
I did a few universal generalization problems but stuck on this
worthy mist
alright so as the task says you'll have to use set equality for this, so when exactly are two sets equal?
proud totem
if the elements contained are the same
worthy mist
Exactly, so if we apply that whats the actual thing we have to prove here?
proud totem
that the sides are equal to each other?
worthy mist
no, we have to prove that for an arbitrary x the x is in the lefthand side, if and only if it is in the right hand side
since that would mean that the sets are equal right?
proud totem
yes
worthy mist
right, and how do we prove a if and only if?
proud totem
contra positive? if a then B is the same as if not A then not B?
worthy mist
no no, a if and only if is not A -> B but A <-> B
(also called iff for short)
so how would be prove A <-> B
proud totem
i dont know
worthy mist
the usual way to do this is by considering two cases:
- A -> B
- B -> A
since if they imply each other they are true if and only if the other one is true
proud totem
ok
worthy mist
so the way we prove
(x ∈ A ∩ B ∪ A ∩ Bᶜ ∪ Aᶜ ∩ B) ↔ x ∈ A ∪ B
is by first showing
(x ∈ A ∩ B ∪ A ∩ Bᶜ ∪ Aᶜ ∩ B) → x ∈ A ∪ B
and then also showing:
x ∈ A ∪ B → (x ∈ A ∩ B ∪ A ∩ Bᶜ ∪ Aᶜ ∩ B)
(the ᶜ is just another notation for ¬ since ¬ is usually used for propositions not sets)
so do you have any idea how we could prove (x ∈ A ∩ B ∪ A ∩ Bᶜ ∪ Aᶜ ∩ B) → x ∈ A ∪ B?
or rather, how we would start a proof for this
proud totem
do we factor out something? I just blank out when looking at the rules and trying to apply it to a problem. Im having a hard time grasping this right now. Do you have any good resources for learning proofs like these?
worthy mist
so first things first no the first step here is quite simple, we assume (x ∈ A ∩ B ∪ A ∩ Bᶜ ∪ Aᶜ ∩ B) and from that have to show x ∈ A ∪ B (and this would work via a series of case distinctions on our assumption)
Regarding the ressources, I mostly got into proofs by learning a so called interactive theorem prover on my own but that's definitely not a way I would recommend, it's rather difficult and takes a lot of time to learn, especially if you aren't even familiar with pen and paper proofs so Im afraid no.
However I'd say your issue with this is that you are lacking very fundamental understanding of how mathematical logic works and if you are doing proofs like this you shouldve learned this before so I'd suggest looking into that again
mint bane
if i prove n=0 and n=1 as base cases for induction, i can assume P(n) and P(n-1) right
burnt fractal
any math grads here that can help me
last timber
delicate flower
With recurrence relations I'm not sure how to find the extra f(n)? I'm writing for a divide and conquer algorithm that takes in a list of numbers:
if start == end
return start
else
left = Algorithm([start...midpoint])
right = Algorithm([midpoint...end])
return theList[left]
end if```
I think the relation is T(n)=2*T(n/2) + f(n) but I don't know how to figure out whether f(n) is 1 or n and how to figure out whether the base case should be T(0)=1 or T(1)=1
Sorry if this isn't the right section to post in, please let me knowok so the 2*T(n/2) is correct kinda
the f(n) is the "extra work" that is being down
so in this case it's the return statement
so what is the computational complexity of that?
then the n in T(n) is the variable that stands for the length of the list
so what list length is the base case?
delicate flower
so what is the computational complexity of that?
It must be constant, does that mean it's 1? Does the comparison start/end count as work also?
delicate flower
so what list length is the base case?
Would this be 1? So then T(1) = the "extra work" you mentioned?
pale epoch
It must be constant, does that mean it's 1? Does the comparison start/end count ...
it depends on your computational model what exactly counts as work
but either way, the work is constant which is really all that matters in this case
the base case is 1, yes
and here there is also a comparison and a return statement
which again is constant work
delicate flower
In that case would 2*T(n/2) + 1, T(1) = 1 be right?
pale epoch
asymptotically, yes
delicate flower
I was looking at this powerpoint and it made me think maybe it should be 2*T(n/2) + n
I also had this example in my workbook but the base case was C(0) = 0 which I don't understand, since wouldn't it have the same amount of extra work so shouldn't it be C(0) = 1?
if n == 0:
return 1
else
return Algorithm(n-1) + n*z```i agree with you
it should be C(0) = 1
its impossible to do no work at all
this does a comparison and a return
but it depends on computational model
(although i think it is standard to only count arithemetic operations and comparisons, in which case this would still be constant work)
delicate flower
Oh I see
Thank you!
My last question is, would I be right to say this is O(nlogn)?
I think I understand now
pale epoch
whats this?
delicate flower
With recurrence relations I'm not sure how to find the extra f(n)? I'm writing f...
For the worst case running time of this algorithm
delicate flower
Of course, you've helped me alot
pale epoch
actually
i think there is a better worst case?
if you take n a power of 2, then it does T(2^k) = 2*T(2^(k-1)) + 1 = ... = 2^kT(1) + k = 2^log_2(n) + log_2(n) = O(n)
delicate flower
I thought O(n) was only possible for algorithms with one recursive call
I did T(n) = 2^kT(n/2^k) + k
pale epoch
yes, but n/2^k reaches 1 after roughly log(n) many steps
so then k = log(n)
2^(log(n)) = n
and n + log(n) = O(n)
(roughly)
delicate flower
Ooh
You're right, I think I understand it properly now!
Thank you very much for your help 😄
weary tiger
How is this symbol called_
pale epoch
$\vartheta$
vital dewBOT
Lochverstärker
pale epoch
it's a "curly theta"
stray reef
an ugly theta*
slate burrow
So i am trying to solve this equation 19x+22y=6
I'm trying to solve for the gcd(19,22) and i am not sure weather to stop at when the rest is 1 or 0?
So i have this
19x+22y=6 (x=22, y=19, x=yq+r, i changed the values so it is easier to calculate)
22 = 19 * 1 + 3
19= 3 * 6 + 1 (stop here or proceed to when the r is 0?)
so 3= 1 * 3 + 0
stray reef
you stop when the remainder is 0, then the previous remainder is your gcd
slate burrow
Right so then i do like this
22 = 19 * 1 + 3 -> 3 = 22*(1) + 19(-1)
19= 3 * 6 + 1 -> 1 = 19 (1) + 3 (-6)
so 3= 1 * 3 + 0 -> 0= 3 (1) + 1(-3)
Or is this wrong?
because when i do it according to this i get this 19(-22)+22(19) which results in 0
i'm doing something wrong and i can't seem to figure it out
vale cairn
22 = 1*19 + 3
19 = 6*3 + 1
3 = 3*1 + 0, so 1 is the gcd - as Ann said, take the remainder before 0
in this case you can just use the fact 19 is prime though ig
vale cairn
What did you get?
slate burrow
What is the purpose of the gcd? It just tells us about the greatest the common divisor
i got 19(7)+22(-6)=1
mulitply by 6
vale cairn
Yes, the greatest common divisor tells you the greatest common divisor lol
slate burrow
you get 19(7*6)+22(-6 * 6) = 6
right which is 1
so that means only 1 divides 22 and 19
vale cairn
But one point is you can always divide by it to get that linear diophantine equation to have coprime coefficients, which is useful for classification
The algorithm also allows you to find a solution to 19x +22y = 1
slate burrow
aha
vale cairn
so that means only 1 divides 22 and 19
Yes
vale cairn
Well then you could just divide both sides of the eq by 2 and you'd have coprime coefficients again
but smaller numbers i guess
slate burrow
aha nice
i think i got the hang of it
i was so stressed because i kept getting 0s and 1s
i thought that it was supposed to give me the answer right away, didn't know you have to multiply a little bit here and there
So now i can just find as many as solutions as i want right?
19(7*6n)+22(-6 * 6n)
or no i believe there is one more step, i got ahead of myself
slate burrow
right
vale cairn
The point is any two solutions to that equation have a difference satisfying 19x + 22y = 0
So find the general solution to that and add on your particular solution
slate burrow
I understand a little bit, but not to a extend where i can explain
I want to be done with my assignment and then read abit more into it
Discreet math isn't as hard as i thought, it actually more fun than i expected 
raven inlet
lethal frost
<@&286206848099549185>
coral raven
||it's 52.04 + 0.0690169016901...
so that's 5204/100 + 1/10 * (6901/9999) = 5204/100 + 6901/99990 = (5204*9999)/999900 + 69010/999900 = 52103806/999900 = 26051903/499950||
for where the 9999 came from, see here: https://en.wikipedia.org/wiki/Repeating_decimal#Converting_repeating_decimals_to_fractions
young breach
||it's 52.04 + 0.0690169016901...
so that's 5204/100 + 1/10 * (6901/9999) = 5204...
Have you tested the solution?
young breach
I get 5246377/99990
Excuse my ugly handwriting haha
And I'm European so commas are decimals and the dot is multiplication
north dust
I am boggled at how to do double sums for combinatorics
coral raven
wait it's not 52.04 it's just 52.4
i'm dumb
||it's 52.4 + 0.0690169016901...
so that's 524/10 + 1/10 * (6901/9999) = 524/10 + 6901/99990 = (524*9999)/99990 + 6901/99990 = 5246377/99990||
young breach
Haha almost mate. It's 520 now
coral raven
ok yeah i didn't remember to edit the very last number
silk hull
Can someone pls explain this to me lolol
I don’t get how they got it
<@&286206848099549185>
silk hull
Can anyone help?
last timber
@silk hull still stuck?
silk hull
Yup @last timber
last timber
what exactly troubles you
silk hull
I don’t get how to work it out @silk hull like how they’re got the answer
minor pumice
Let A={1,2,3,4,5,6} and let
R={[1,1],[1,2],[2,1],[2,2],[3,3],[4,4],[4,5],[5,4],[5,5],[6,6]}
be an equivalence relation on A.
What partition of A does R induce?
I don't even know what I am being asked
stray reef
you have an equivalence relation on A. you are asked to list the equivalence classes generated by it.
minor pumice
you have an equivalence relation on A. you are asked to list the equivalence cla...
?
I don't understand fancy math talk can you say it like you are explaining to a 5 year old
red nest
Can someone pls explain this to me lolol
Let x be the students studying only art, y the students only studying music and z be the students studying both. The number of students not studying anything has to be 6 because there are 25 total and 19 studying something. Also the number studying at most 1 thing is x+y+6 which is 16. So x+y=10. x+y+z is the number studying atleast one thing which is 19. So x+y+z=19 so 10+z=19 hence we get that z=9
peak grail
can someone briefly explain the logical reasoning behind this?
<@&286206848099549185>
sonic prism
@peak grail
subtle charm
Let A={1,2,3,4,5,6} and let
R={[1,1],[1,2],[2,1],[2,2],[3,3],[4,4],[4,5],[5,4],[...
Based on what Ann mentioned, I think it is asking for all the equivalence classes.
[1] = {1, 2}
[2] = {1, 2}
[3] = {3}
[4] = {4,5}
[5] = {4,5}
[6] = {6}.
And you can see that [1] = [2], [4] = [5]. I think my answers is right? Not really sure since I am still learning. Perhaps @snow sleet can help to check if my understanding is right?
Then the answer will be something like: Partition = {{1,2}, {3}, {4,5}, {6}} ?
snow sleet
Based on what Ann mentioned, I think it is asking for all the equivalence classe...
Looks good
acoustic sphinx
I recently came across an exercise with pairs but I have no clue how to even approach the assignment. Any clues would do wonders! :)
subtle charm
Looks good
Awesome!
peak grail
Would the if-then part be,
If Islamabad United will not win tomorrow's game, then they will not win the pennant
OR
If Islamabad United wins the pennant, then they win tomorrow's match?
I am confused 😢
gritty crescent
I am confused 😢
Let's try an easier statement: I can vote only if I am over 18.
Can you reformulate this in the if-then form?
outer hinge
Why is p -> q logically equivalent to ~p or q ?
I did a truth table and I don’t see it
elder berry
I did a truth table and I don’t see it
When you compare p -> q and ~p v q with the truth table, they should give the same truth/false value when you put the same true/false values for p and q, so you need to compare the last columns of the table
outer hinge
This is what I got
So I need to use p and q ?
How do I know I’m supposed to compare them to that ?
gritty crescent
Your entry for p -> q when p is false and q is true should be true, not false
outer hinge
Your entry for p -> q when p is false and q is true should be true, not false
Why ? Is p being true implies isn true then then why would p being false imply q is true ?
gritty crescent
See, this is one of the common problems understanding the implication-this is not necessarily a cause effect relationship. The thing is, as soon as p fails, there is no obligation for q to be either true or false, so the implication still holds as a whole.
Intuitively, you can think of the implication as an agreement: if you do A, I promise you B. However, if you fail to do A, then the agreement still holds whether I give you B or not.
The only circumstance in which the agreement really breaks down is when you do A, but I fail to give you B.
peak grail
Let's try an easier statement: I can vote only if I am over 18.
If I am over 18, then I can vote?
gritty crescent
Correct!
So "A only if B" gives the feeling that A in some sense is predicated upon B happening
Hence it translates to "if B, then A"
peak grail
ohh, so it will be,
If Islamabad United wins tomorrow's game, then they will win the pennant?
gritty crescent
Yep!
peak grail
noice, ty 😄
gritty crescent
No worries, goodluck 
peak grail
If I have an if-else statement, would the contrapositive be true?
robust mango
@peak grail If you have some if-else/then statement which is true, say p implies q, then it is equivalent to not q implies not p(the contrapositive) and it is true as well.
weary tiger
Proofing that its a function but Y input seems to have no use
Confused does y not matter
last timber
can you represent 5 as difference of some square and 3?
robust mango
@weary tiger Yes, y doesn't matter because just think of it as x^2 * y^0, whatever y you put, just becomes 1.
Now think what beware said, put g(x,y) = 5. Can you find some (x,y) that gives you g(x,y) = 5?
For onto, all the outputs must be able to be traced back to atleast one input. So, for the output g(x,y) = 5, can you find some input (x,y). And remember, x and y should be integers.
weary tiger
For onto, all the outputs must be able to be traced back to atleast one input. S...
ok makes sense
weary tiger
For onto, all the outputs must be able to be traced back to atleast one input. S...
but when you want to put it in a proof do you want to make x and y integers? I am not sure because dont you want to prove at large that an integer is onto because an NOT onto function can have a input and different out put so your not really proofing it
robust mango
@weary tiger What we did was just prove that the statement is false using a counter example. If we have a function which really is onto, then you start from the output and then prove that it can be traced back to some input which satisfies the given condition
weary tiger
oh so it's not onto
robust mango
Yes, do u know why?
weary tiger
no
robust mango
Let g(x,y) = 0. Then we have x^2 - 3 = 0 which gives us x = +- sqrt(3)
The output "0" is an integer, and for the function to be onto, "0" can be traced back to some input(pair of integers).
But when we put g(x,y) = 0, it gives us x = +-sqrt(3), which means x is not an integer.
weary tiger
ok thats makes sense
how would i go about writing a proof
I started with
Proof:
Take any b = E Z and
robust mango
Let g(x,y) = 0. Then work out the algebra, and then state x is not an integer.
Thats it
gritty crescent
@weary tiger Start by considering an element c in X\cap Y. Can you show f(c) lies in both f(X) and f(Y)?
Also, I hope this is not a graded assignment/exam?
weary tiger
no im just reviewing
wow im lost
function f ( X and Y) are subsets of f(X) AND F(Y)
is there like a video example of this kind of problem
this is the first time looking at something like this
robust mango
This is not the case of onto. For this, you have to show that if some element belongs in f(X and Y), then it must also belong in f(X) and f(Y)
To show that A is a subset of B, you just show that any element belonging in A also belongs in B.
weary tiger
oh yeah i was confused on that too
robust mango
Sorry
Maybe this video will help
It's f inverse here but still just think of it as some function F
weary tiger
Wtf
gritty crescent
Try not to bury yourself in a sea of symbols before figuring out the proof itself.
To avoid ambiguity in naming, suppose b is some element in f(X\cap Y).
Now f(X\cap Y) is the image of X\cap Y, so you can agree there exists some c in X\cap Y such that f(c)=b, right?
weary tiger
trying to work it out in my head
gritty crescent
Try to scribble a bit out on paper
Consider one object at a time for now
Ask yourself: what is X\cap Y? What is f(X\cap Y)? What is an element in f(X\cap Y) like?
gritty crescent
I think it's a typo in all likelihood
It should be f as well
Doesn't make sense to introduce a new function symbol out of nowhere
gritty crescent
A note on good practice: be explicit about what variables denote what, in words. Start with something like "Consider an element b\in X\cap Y. Then, f(b)=c is in f(X\cap Y)..."
gritty crescent
I don’t know what im doing
Take a break if you need it. The idea is to pick an element in f(X\cap Y), and lead up to showing that it is in f(X)\cap f(Y)
The general element in f(X\cap Y) is the image of some element in X\cap Y, and that's your stepping stone. An element in X\cap Y is present in X as well as Y; hence its image is contained in f(X) as well as f(Y). Now tie this up as a proof.
weary tiger
@gritty crescent
frosty dagger
P and not Q is not(not(P) or Q)
mental sapphire
Yes but the r
frosty dagger
Well, the [if X then Y] statement is X -> Y I guess ?
I'm not sure if you could do more than that
mental sapphire
Well, the [if X then Y] statement is X -> Y I guess ?
Yes
I’m not sure either, I am trying to set up a truth table but I have a feeling I committed a mistake
frosty dagger
Do you have a photo you could post so we can look at what you think went wrong ?
frosty dagger
Let me look at it 🙂
mental sapphire
It’s alright I think I got it
mental sapphire
But the truth table is incorrect
The statement is a tautology
It’s all Ts when I solved for it in a truth table
There must be something I’m missing but idk
frosty dagger
Huh, really ?
For P = true, Q = false and R = false ?
@mental sapphire Sorry I was eating
mental sapphire
It’s alright
Here’s the truth table I made
Wait nvm
Dumb me
I made the truth table just for that specific statement
I’ll make a truth table to check the truth tree
gritty crescent
<@!697848465819959388>
alpine agate
Is this the correct channel for enumeration?
weary tiger
hi im having trouble with this question
we're not allowed to use truth tables, and just learned how to use logic laws and such to find a solution
this is what I've done so far and im not even sure if its correct
also sorry for the messy writing lool 😁😁
should i be using the questions text channels to look for help o.o or is here fine
Is 10 days enough to prepare for a discrete math I test?
I’ve been going to lecture
He doesn’t assign that many problems
alpine agate
If anyone can help me with a counting problem that would be appreciated: How many ways are there to select 10 of 50 people IN A CIRCLE so that none of those chosen people are adjacent?
meager prairie
hmm
is it implied order matters
it shouldnt right
picking persons A-B-C-... is the same as C-B-A-...
gritty crescent
Hmmm, I think the path I would take is this: consider the number of ways where two of the 10 people do end up being adjacent, and subtract it from all possible arrangements.
gritty crescent
meager prairie
for example
try 2 from 10, and 3 from 18
which sounds like a lot but i enumerated both in 10~ mins by hand lol
assuming order doesnt matter
but including order wouldnt be too much work
oh, shoulda been 3 from 15 
but same project
gritty crescent
Could be, what I have in mind is to pick 10 people in 50C10 ways, then form pairs in 10C2 ways, now permute the 48 people+1 pair in a circle
meager prairie
thats probably pretty naive approach
actually yea pairwise is a good approach
ways to pick 10 people such that you have at least one pair
gritty crescent
Right
meager prairie
@weary tiger were talkin about ur problem
alpine agate
What I was considering at first is because you can't have the 10 people next to each other you have a person A (that's selected) and B (which includes the other 40 people) and you first have them like ABABABABABABABABABAB in a circle, then you fill in the other people but im not sure if the count would work
meager prairie
If anyone can help me with a counting problem that would be appreciated: How man...
for example consider 3 from 15. we want at least one pair next to each other. start with assuming your first pick is next to your second pick.
then start from the next position and count (but dont count when the third pick touches the other side, to avoid double counting)
you get 15-3 = 12
then count if person 2 and 3 are next to each other
i get another 11
multiply by 15 possible chairs
then probability (i think?) would be 1- [ 15*(12+11) ]/[ 15C3 ]
alpine agate
so you're just considering a smaller example right when you say 3 from 15? im not looking for probability btw, just the number of ways the occurrence with the parameters can happen
meager prairie
oh
then just count
yea a smaller example but similar fraction
I think manan is more on the ball with a super specific way to compute it
i worry about double counting my way
alpine agate
oh and thats why you divide the 15 choose 3 out?
meager prairie
no, i was making a probability
and now im really thinking ive done a horrible amount of double counting
alpine agate
Thing im wondering is does Manan's count account for the possibility that you have two people next to each other and then you have another instance of two people being next to each other on another part of the circle
meager prairie
thats totally fine
for all participants, no two are adjacent
negate to exists some participants such that two are adjacent
having them all right next to each other satisfies that just fine
same with any other case which would break the non-negated condition
aka existence is satisfied by any amount of pairs greater than 0
alpine agate
i think i see what youre saying now
meager prairie
so lmc
idk maybe you have enough of a hint, i am also in a similar class so youd prolly get it as fast as me
alpine agate
I think so, so we start out with the 50C10, then we have to subtract the 10C2 (which are the cases when two people are next to each other), and then we permute the final 48 people?
alpine agate
The problem is 10C2 is i think 45 which is really small, perhaps it makes more sense than im thinking
meager prairie
thats just to ensure at least one pair though
wait but
damn idk im in a similar class like i said
manan is counting diff orders then
which im not sure matters
right?
alpine agate
I think in this case order does matter because the people are distinguishable
meager prairie
idk i always figure these are like
committee problems
youre building a subset of people from a set of folks on some condition
alpine agate
wouldnt that mean that order would matter?
meager prairie
and i mean
50C10 doesnt enumerate the permutations does it
only the possible subsets
alpine agate
right
meager prairie
so what youd really want is like
50C10 total ways
subtract the ways to pick some pair from 50
which i think is 49?
alpine agate
why would it be 49?
meager prairie
(1,2) then (2,3) then ... then (47,48) then (48, 49) then (49, 50)
the nth pair has a highest element n+1
i think
alpine agate
With that it would make sense but couldn't you also have say (1,2) and (9,10) etc because we're not just working with 2p eople
meager prairie
adjacent pairs
maybe i should specify
no, but you just multiply by the ways to order the remaining people
this is another double counting thing though
if order really doesnt matter
since i mean even imagine picking 4 people
one of your pairings is gonna have (1,2) as the first two
then the remaining permutations will have (3) (4)
but then when you enumerate (3,4) initial youll get (1) (2)
so you need to uhh
it needs to decrease right
that stops you from double counting
(1,2) has 48 choose 8
(2,3) has 47 choose 8
is that enough
alpine agate
im not sure
meager prairie
i think so
you should capture every possible case of all 10 being next to each other right
i think this works
alpine agate
I should, but iits always weird w/ circles for me so i have a hard time picturing the count and stuf
meager prairie
you need to find the last case
whats the initial pairing
is it 41,42
then its only 41 out front
alpine agate
When you say 41, 42 those are the 41st and 42nd people in the circle being paired right?
meager prairie
yea, not allowing chairs behind the initial pair to be selected
so 41, 42 as the initial pair
then 8 seats remaining
all 10 people next to each other is the only case
no further chairs can be initial
since theyd begin to overlap
alpine agate
man this problem seems more complicated than i thought
vital dewBOT
jan Niku
alpine agate
i havent used latex in a while unfortunately
meager prairie
$\binom{50}{10} - \sum \limits _{n=8} ^{48} \binom{n}{8}$
vital dewBOT
jan Niku
alpine agate
That does seem right, because you're adding up all the cases where they're next to each other, and of course you want to remove those cases
meager prairie
i dont think its right
alpine agate
I do know that my professor is expecting a more simple answer than that though
meager prairie
the number of ways to choose 10 with at least one adjacent is 4 times smaller than the way to choose with 0 adjacent
in this answer
that doesnt make intuitive sense
alpine agate
so we know we're starting with the 50 choose 10 and we need to subtract something, and that something is basically all the ways we can pair up 10 people?
meager prairie
well
its all the ways you can pick 10 people such that at least 2 of them are adjacent
alpine agate
or any 10 people
meager prairie
my thought from manan was like
pick two seats, then pick from the rest that are higher than that pair
ensuring you have at least 2 adjacent
so you get 48C8 + 47C8 + ....
but thats too low
alpine agate
can i tell you what im thinking, it might not be right for a circle problem but
meager prairie
sure
alpine agate
We start off, knowing that 10 cannot be adjacent, so we start off separating one of the 10 (we'll call it P) and then right after we have a Q (any ppl not those 10), and in a circle the pattern is PQPQPQPQPQPQPQPQPQPQ---then we fill in the remaining Q's
I believe the count for filling in the Q's would be 49C9
39C9*
meager prairie
alpine agate
That was sorta how we would do it in class with rows
meager prairie
should it be 30 left?
alpine agate
I may hve miscounted just a moment
yeah 30 people left
There's 30 people left, but there's an idea where it's like x1+x2+x3+...xn, where x_i>=0, you'd just say (n+r-1 choose r-1) and thats where the 39 choose 9 came from
alpine agate
yeah im not very good at explaining stuff, but if we basically find out how many ways to fill in those gaps
then we complete the circle, and im assuming we could just orientate the people within there?
meager prairie
as long as you can make sure you arent double counting
idk a good guess but maybe if you can figure out how to calculate it somewhere between 1 and 4 billion is a good number?
alpine agate
with rows it isn't a problem but i have noi dea with circles
uh what do you mean by that
meager prairie
total is around 10 bil
so maybe something like 10 to 40 percent of that is a reasonable answer?
just a guess
alpine agate
i was initially thinkng that was way too high but we're working with 50 people so maybe?
meager prairie
if you can calculate it and land around there youre on the track righter than me lol
,w 50 choose 10
vital dewBOT
alpine agate
I dont really care about the actual number we just put it simply and we're done
meager prairie
no, the real number doesnt matter
ballparking is good tho
idk id have to think more i think
damn my formula works for simpler examples 
well wait a second
maybe thinking the initial answer was wrong was bad intuition
maybe the number of no-adjacents should be way higher @alpine agate
that was the only reason i rejected that answer
but 10 is so small compared to 50
like even choosing 2 from 9 the ratio is 3
maybe 4 isnt too wild for 1/5 instead of 2/9
i think its right
alpine agate
which was the initial answer?
meager prairie
meager prairie
i rejected it on bad intuition i think?
since it said the number allowing at least one pair is way less than when no one is next to each other
alpine agate
Yeah my intuition with counting has not fully formed so it's hard for me to think it through
meager prairie
but think in a big empty movie theatre
you and 10 randos can sit apart from each other in so many more ways than like
i mean itd be so exceptional for a randomly chosen seat to be next to so few people
alpine agate
i see that, theres only 10 and theres 40 other possible seats
meager prairie
yea exactly
so i think given this makes like
calculation sense and intuitive sense its reasonable
but im also a stats student so grain of salt
alpine agate
ahh
meager prairie
fwiw it works on examples you can enumerate by hand
i tried 3 from 15 and 2 from 9
alpine agate
And you wrote those out by hand or you just used a similar strategy to what we did here
meager prairie
by hand
well both i guess
try 2 from 10
enumerating all cases of adjacent is easy
alpine agate
theres 11 of them i think
meager prairie
its just 10
meager prairie
so youd expect the answer to be 10C2 - 10
then you just count
starting from chair 1, you have 8
2 gives 7
alpine agate
is there a combination way to get that 10 though?
meager prairie
3 6, 4 5, 5 4, 6 3, 7 2, 8 1
oh maybe theres 9
we already did this lol
(1,2) then ... then (9,10)
nth pair has highest element n+1
then 9 pairs
alpine agate
For 10 people in a circle it should be 10 because let's use alphabet: AB, BC, CD, DE, EF, FG, GH, HI, IJ, JA
alpine agate
For a 3 example where they're adjacent how would we count that?
would it be 6*6...10 times?
meager prairie
you just pick up more
alpine agate
oh but we also need the pair case so maybe that would not be right
meager prairie
from each initial pair
instead of only one
since the remaining guy fills in (its no longer the remaining seats choose 0)
alpine agate
i dont quite follow how you pick up more people, to find the count
With the 2 example it's easily listable, but theres so many more options when it comes to 3
alpine agate
8 pairs as in AB, BC, CD that type of deal?
meager prairie
ohh
sorry i just figured something out
8 pairs in terms of like
picking 2 adjacent seats
sorry i think my answer is slightly off above, were missing a pair
anyways you have 8 initial possible pairs next to each other
alpine agate
right
meager prairie
then in the (12) case (call it 1 initial)
alpine agate
12 case?
meager prairie
you have 6C1
yea, a person is selected from chair 1, and chair 2
ensuring at least 1 pair
alpine agate
ohh 1,2 right
meager prairie
then person 3 can be picked from 3-8
giving 6C1
then 2 initial gives 5
3 initial gives 4
4 gives 3
5 gives 2
6 gives 1
and thats it, yea?
so we expect answer to be 8 choose 3 - 15
alpine agate
So for (1 initial) case where does the 6C1 come from, i thought we had 8 in total?
meager prairie
we do, but 1 and 2 are already selected
we choose 1 more from the remaining 6 seats
alpine agate
oh ok
alpine agate
one more pair or one more additional number?
meager prairie
8C3 - 21
one more person
for a total of 3
2 in the initial pairing
then 1 more for a total of 3 from the 8 possible
so
,w (8 choose 3) - 21
vital dewBOT
alpine agate
maybe, but we can have AB, BC, ... HA, and then we can have ABC, BCA, CBA, so maybe realistic?
I feel like that doesn't make sense for there to only be 13 triplets that are next to each other right?
meager prairie
idk im so tired
alpine agate
this is frustrating stuff man
alpine agate
I tried with even having 5 chairs and selecting 3 and its confusing me lol
alpine agate
it’s fine man I’ll try and grind it out ty for your help tho!
alpine agate
If anyone can help me with a counting problem that would be appreciated: How man...
if anyone else reading wants to think it through with me just ping me :)
dire wren
Need a second opinion on this proof by induction problem. Anyone mind taking a look and letting me know what they come up with?
west meteor
need help for this
minor pumice
hello can someone help
R = {(a, b) ∈ Z × Z : 4 | (a^2 - b^2)}
S = {(2,0),(-2,0),(4,0),(-4,0),(4,2)}
How tf do I show R is an equivalence relation if it is not reflexive?
I can't tell where I am making a mistake
any number minus itself will equal 0
4 does not divide 0
vital dewBOT
jswatj
weary tiger
except for 0 i think
weary tiger
4 | 0 is $\frac{0}{4}$ no?
vital dewBOT
jswatj
minor pumice
im so confused
weary tiger
confused about what?
minor pumice
so a | 0 is always true?
minor pumice
ok
weary tiger
yes
minor pumice
thx
weary tiger
in fact any (x,x) is true because 4|0
minor pumice
ye
minor pumice
in fact any (x,x) is true because 4|0
hey one more question
I have to describe distinct equivalence classes
I am not sure how to write it
but wouldn't it be every multiple of 4 and 0
in one class
tf would a second equivalence class be
weary tiger
can you send the question?
minor pumice
same relation as above
R = {(a, b) ∈ Z × Z : 4 | (a^2 - b^2)}
every element could be related to every other element and satisfy the conditon
{...,-4,-2,0,2,4,...}
weary tiger
what distinct equivalence class do they want you to describe
or like a general class [x]
minor pumice
Describe the distinct equivalence classes of R and prove that they are the
equivalence classes.
stray reef
4 | 0 is $\frac{0}{4}$ no?
4|0 is not a number, it's a statement.
plush dock
Hey, I'm struggling with this a bit.
Let G be a simple graph, |V|=6. The degree of each one of the vertices of G is 4
- G is a necessarily planar graph.
- G is necessarily not a planar graph.
- Answers 1 or 2 are incorrect
I was thinking the answer is 2 because G has K_5 as a subgraph, but I'm unsure
What am I misunderstanding?
pale epoch
why would it have K_5 as a subgraph
neon fulcrum
This example in my textboook doesn't make sense to me. I think it should be q -> p
Am I crazy?
plush dock
Because it has at least 5 vertices with 4 edges each, but I probably misunderstand how subgraphs work.
pale epoch
that does not mean they are all interconnected
e.g. connect 1 to 2, 3, 4 and 5 and connect 2, 3, 4 and 5 to 6
(then add enough connections so its 4-regular but it wont have K_5 as subgraph)
pale epoch
i will share my cookie with you only if you share your soda with me
i.e. the only way that i share my cookie with you, is if you share your soda with me
so if i shared my cookie with you, we can dedude that you have shared your soda with me
q -> p is different, because you might share your soda with me for other reasons (i.e. while not getting any of my cookie)
neon fulcrum
is the "only" special here?
pale epoch
yes
neon fulcrum
ok
pale epoch
"only if" has a different meaning than "if"
jaunty mountain
so lets say I have a problem like this: ¬(p∨(¬p∧q))≡¬p∧¬q
do i solve it by looking at one part of the question and comparing that to any of the logical equivalences and then changing that part of the question to the logical equivalence that matches?
faint narwhal
What have you tried?
floral lily
did i understand this correctly?
floral lily
Is it because am empty set actually can be a posibility of a? i didnt thiink so simply because i didnt think changing a set to an empty set would make it true
ashen tapir
Hello, i'm new for this server
i want a help with this exercise
Z = {w ∈ ℤ : w ≥ - 5 y w < 7 y (w)² is par}
floral lily
i just started so im figuring it out still, i just didnt think an empty set is a probability of a set that isnt empty
brazen blaze
mmmm
floral lily
?
brazen blaze
mmmmmmmmm
floral lily
um ok?
brazen blaze
mmmmm mmmm mmm m m
brazen blaze
mmmm
obsidian tendon
please dont do things like this in this channel
faint narwhal
What have you tried?
weary tiger
Im looking at a similar problem on youtube
weary tiger
Prove that if a and b are integers and a divides b, then a
is odd or b is even.
what kind of proof method would i use
oh
ok
so direct prro
proof
lol
wait
3 / 3 = 1
both are odd
i dont get what the question is asking
faint narwhal
a is odd in that case
weary tiger
It is given that
b = m ⋅ a for some integer m. If a is not odd, then a = 2k
for some integer k, whence b = 2km. This means by definition that b is even.
why is b considered even
@faint narwhal
b = 2km
faint narwhal
Do you know what the definition of even is
faint narwhal
What does equal amount mean
weary tiger
An even number is an integer of the form n=2k
faint narwhal
So do you see why 2km is even