im kind alost on how these are different
#discrete-math
valid wave
coral raven
you're comparing the power set of the intersection of a and b
to the intersection of the power sets of a and b
pale epoch
start with a few examples
pale epoch
no
one side is the powerset of (the intersection of A and B)
the other side is the powerset of A intersected with the powerset of B
pale epoch
you want to prove that they are the same if they are
and if not, you want to give a counterexample
valid wave
Hi sorry for noob questions
For E: how isn’t 3 a subset of it
Also
I get that 1 e A wouldn mean an element
But would {1} E A
Mean a subset containing 1?
or rather an element that is = {1}
Could someone explain that
weary tiger
Any ideas how to prove it combinatorially?
I was thinking about something like considering in which cycle n+1 element is supposed to go, but I don't get why is there a 2^k
coral raven
2C1 * 2^1 + 2C2 * 2^2 = 2*2 + 1*4 = 8 != 6?
weary tiger
its not choose
weary tiger
Its Stirlings number of the first kind.
coral raven
oh gods
clever sage
mystic moss
Any ideas how to prove it combinatorially?
i found this very cool actually
so the idea is that you have to think of it as picking a set of "chosen cycles"
from each possible permutation
and using that to create the new cycle that the (n+1)th element will be in in the ordering of n+1 objects
and you do this by ordering 2, 3, 4, ... m using the m-permutation obtained by the chosen cycles
m is just the sum of the sizes of the chosen cycles (i.e. one less than the size of the cycle that the n+1th element will live in)
and after ordering the last m-1 elements, just stick the first element in the front
mystic moss
and you do this by ordering 2, 3, 4, ... m using the m-permutation obtained by t...
oh and it doesn't need to start at exactly 2. by 2 i just mean the second element in the chosen cycle list
urban saddle
I want to know how many numbers of 4 digits exists, I see it as variation with repetition, so as we have 9 differents digits, the solution would be 9^4 = 6561
but that is wrong...what am I missing?
urban saddle
oh,true
proud birch
Translate the following sentence into mathematical notation: ”Every integer is less than half as big as another natural number.” Negate the sentence and translate it back into English.
does the mathmatical translation of this (without negation) mean Vx c Z, x < n/2, n c N
or is it like Vx c Z, x/2 < n, n c N
proud birch
okay thank you, the wording really throws me off
so all quantifiers should be placed prior to the statement
fair cedar
Yeah, bigger problem was that you left n unquantified
proud birch
oh shitt
fair cedar
But yeah usually quantifiers at the beginning
quick folio
can someone draw this for me
grim kraken
This is a set partition. So you have 3 sets of things which are equivalent: 0 is just equivalent to itself, 1 and 2 are equivalent, and 3 and 4 are equivalent. There are no relations joining things in separate sets.
You can think of this like 0 | 1~2 | 3~4 (where the bars separate nonequivalent groups)
So to prove this is an equivalence relation, you want to check that it has all the properties it needs to have: that it's reflexive (x ~ x for each x in S), symmetric (x ~ y implies y ~ x for each x, y in S) and transitive (x ~ y and y ~ z together imply x ~ z for each x, y, z in S)
Prove these 3 parts separately. Usually it's easiest to go in order. Remember that x ~ y means x, y are both in A_i for some i.
urban saddle
I'm trying to find all numbers of 4 digits such as n1 < n2 < n3 < n4, eg 1234 or 3579 but I'm not seeing the solution
by logic I can see the following restrictions:
1<= n1 <= 6,
2<=n2<=7
3<=n3<=8
4<=n4<=9
but beyond doing the permutations for each slot I dont know how I can make sure it follows the original restriction
proud birch
how would you define thus?
proud birch
Thank you for trying at least lol
quick folio
ty ryc
i was thinking like
nC1 +nC2+...+nC_{n-1}
thats 2^n-2
where am i missing 2x extra cases
weary tiger
$2^n - 2 = 2 \cdot (2^{n-1} -1)$
vital dewBOT
Godel
weary tiger
You are counting two times because when nC1 you already are counting nCn-1 kinda.
quick folio
can u explain that
weary tiger
When you are choosing 1 element set you already chose n-1 element set.
quick folio
OH
OK
Ok OK
so when u do n-1
u have a case which is equal to when u did nC1
{1,2,3} -> {1,2} {3}
u could have {3} {1,2}
azure tree
can someone help me with this question
apparently the rows are from 1-15 in hexadecimal
but i want to know how i can compute that without the use of google
dense sapphire
What're the traversals (pre, in, post) for this tree?
I want to say preorder is: 11,1,2,6,3,4,7,9,5,8,10
Inorder is: 6,2,1,11,9,7,4,10,8,5
Postorder is: 6,3,2,9,7,4,10,8,5
keen girder
I only agree with your preorder
My postorder is: 6 9 7 10 8 5 4 3 2 1 11 and my inorder is: 6 2 3 7 9 4 5 10 8 1 11
however, i could be wrong.
dense sapphire
I am more likely to be wrong than you
keen girder
we can discuss on how you came up with your attempt then we can correct it.
dense sapphire
so i know the steps, but my tree confuses me due to its asymmetry
keen girder
yes the tree is certainly confusing. However, the algorithm for the traversal doesn't change. Start with describing how you got your inorder.
dense sapphire
I knew that inorder is left root right
keen girder
yes.
dense sapphire
what i was confused where to go from was node 3
i wanted to go 6,3,2
i also wanted to try 6,2,3,1,11
keen girder
I see you wrote, 6, 2, 1. However, this does not make sense. 1 is the parent root of 2. Then, in order to visit 1, we would have visited ALL of children of 1. Which is why we would get 1 in the second last.
dense sapphire
yes i've actually struggled to find discussions of tree traversals in parent/child terms
idk why
keen girder
I think if you are confused about traversal like these, I suggest on a new paper, draw a complete tree and mark the non-existing nodes as "empty". Then apply our tree traversal logic again.
dense sapphire
yeah I was leaning that direction
keen girder
@dense sapphire ignore the error at the bottom, but i represented null nodes by colouring in black.
dense sapphire
yeah that looks what i've drawn
keen girder
So now, we perform the inorder algorithm.
dense sapphire
ok, here goes: (6,2,null,3,null,7,9,4,null,5,10,8,null,1,null,11,null)
oops typo
so i get your answer
keen girder
lol i was typing every step but since you get it i wont post it.
anyway, now apply the post order algorithm on the tree.
dense sapphire
no i admit i can't find good explanations of traversals despite how trivial they are
like this strategy of balancing with null nodes is intuitive, yet nothing mentions this
keen girder
I agree. However, with practice, this will become easy to imagine in no time.
dense sapphire
no doubt, ok here goes: 6,7,9,10,8,5,4,3,2,1,11
and no i'm not copying your answer I'm using the same form as an example I'm looking at
from cmu
keen girder
I don't think we have the same answer.
First, tell me, what are the steps for post order?
dense sapphire
ah you're right i have my 7 and 9 mixed up
keen girder
yes
dense sapphire
i broke the rule of children before parent
wish more of these traversals were phrased that way
Tell me, have you ever seen a traveling salesman problem that looked like this before
keen girder
That looks confusing to me haha.
dense sapphire
How do you find upper and lower bounds for a Chinese postman problem
placid coyote
What're the traversals (pre, in, post) for this tree?
Considering this, remember that:
Pre - Visit, left, right.
In - Left, Visit, Right.
Post - Left, Right, Visit.
timid atlas
hello is anyone here good at discrete math
mint bane
h e l p
potent chasm
Hey. I have the following question:
How do i prove this: x⋅(y+z)=x⋅y+x⋅z ?
mint bane
de morgan's law...?
potent chasm
@mint bane I had another question, where i needed to prove de morgan's law, i got this:
Just don't quite know how to intertwine them, if that makes sense😅
And i though i where to use the Distributive Law, maybe🤷♂️ (boolean algebra)
weary tiger
Hint: this is the same as distributing 25 balls into 6 urns, but you can put at most 9 balls into first,second and third urn.
And just count all the possibilities in different cases, although there's probably some faster way I can't think of right now.
Maybe also let x3+x4+x5 = n \in {0, ... 25} and find solutions to 25 - n in x1 x2 x3 in {0,...,9}, just a thought though.
edgy totem
jolly ridge
Does anybody know 8 queen problem here? I solved it and just wanted to know if it's correct
frigid abyss
anyone know an easy way to determine if a graph contains/does not contain a hamiltonian cycle
stray reef
anyone know an easy way to determine if a graph contains/does not contain a hami...
if someone knew of an easy way they would solve P vs NP i think
but you can try to construct one
and see where your construction fails
frigid abyss
my textbook says this. but idk what they are doing exactly
stray reef
...
whats this talk about removing edges?
what was the exact statement of your original problem
frigid abyss
Show that none of the graphs contains a Hamiltonian cycle.
stray reef
okay so
what i think they meant by edge elimination is that the edges incident to a, c, j and l have to be in the cycle nmw
by virtue of these being the degree 2 vertices in your graph
1 in, 1 out. you don't have any options.
so your cycle is forced to contain ab, ad, bc and bd
and well
oops!
those link up
you can't extend the cycle any further to cover e, f, g or h
frigid abyss
so are they deleting vertices which have more than a degree of 2
but in that case 1 edge for each g and f should also be removed
stray reef
not deleting
just marking off the edges as forced
g and f have degree 3 so the same logic won't work with them
frigid abyss
looks like they are explaining it by eliminating edges tho
weary tiger
What book is that? the style seems familiar
frigid abyss
Discrete mathematics by Richard Johnsonbaugh
neon frost
No idea where to ask this question and sorry to interrupt but is this sentence grammatically correct?
"As all elements of P(A) are distinct, so too will the binary strings they are defined by be."
Or is there a better way to write this because it does not roll off the tongue imo
naive gulch
No idea where to ask this question and sorry to interrupt but is this sentence g...
Maybe since instead just for flow?
Since all elements of P(A) are distinct, the binary strings that define the elements will also be distinct.
Its repetitive but gets the point across easier?
For this question, little lost. Sample space S is {1,2...50}?
Not sure how to proceed
gilded merlin
anyone here??
naive gulch
Against discord rules
The discord can't help you if you're doing a test in the moment
naive gulch
I know its tough and snitchy but imo esp if you're at a university level if they find out, they're directing that towards the admins here
loud sonnet
You can just cheat
naive gulch
that'll put em into the line of fire so the rules make sense 🤷
loud sonnet
And notice how if F is a rigid motion
Then F is differentiable
And the derivative has absolute value 1
Which means that if F' is equal to 1
Then F is of the form x+b for some real number b
And if F' equals -1
It is of the form -x+2a
For some constant a
So it is either a translation or a reflection indeed
But that's sort of cheating
Lmao
unreal stump
You can show rigid motions are linear(also unitary) transforms if T(0)=0
naive gulch
bro ain't slick 😢
gilded merlin
please help me out in this question 🙏🏼
lament quiver
please help me out in this question 🙏🏼
this isn't really satisfying but I found an answer through trial and error
look around multiples of 1, 8, etc....
naive mural
23 isn’t
quick folio
for this qtn
why cant we just do 5C3 * (25C2 - 3)
so 5C3 ways to choose the janitors
25C2 - 3
stars and bars on the janitors
oh i think cause multiple janitors can work on multiple toilet compartments
if the qtn said the compartments have no repetitions
will i be right?
weary tiger
I am writing a true/false test with 12 questions. Eight of the answers are True. How many different answer keys are there?
Would the answer just be 12P8?
Btw I’m very new to this math.
weary tiger
Ok thanks. Do I have to multiple that by 12 C 4 or is 12 C 8 the final answer ?
quick folio
12C8 is the final thing
languid blaze
I was wondering about this question How many 10-character strings of decimal digits ([0-9]) contain a 3 and a 9?
I think I can get a rough idea of how to find the total number of 10-character strings of decimal digits
I just have no idea how to format that when looking for two specific numbers
last timber
@languid blaze you just are given two digits already
so it reduces to finding 8-digit combinations
if i understand wording of problem correctly
last timber
well ugh wait not exactly to 8 combinations
but look
39_ _ _ _ _ _ _ _
for this eight combinations
languid blaze
ok thank you
vital dewBOT
Meliodas
vital dewBOT
Meliodas
quick folio
is ur answer then
quick folio
LOL
the earlier one is exclusion inclusion
i read that as an OR
which would complicate things
lol
quick folio
LOL
do u have more qtns?
@languid blaze
chuck
yeahhh
i got exam coming up so good practice
languid blaze
uhhhhhhhhhh
There is a donut shop with 4 types of donuts. {A, B, C, D} What is the probability that a random sale of 12 donuts contains at least 6 donuts of type A? Assume all sales are equally likely.
I'm pretty sure this is just choose(15,2)-choose(9,6)
If you want I can give you a set of problems to practice from
errant bear
where r u getting that from
languid blaze
getting what?
I have an exam in a week so I've been practicing some previous final questions
errant bear
your answer
languid blaze
ok so basically
the total number of ways to choose 12 donuts from 4 is C(12+4-1,12)
we use combination with repetition formula
and subtract all the options that have at least 6 donuts of type A
which is just C(6+4-1,6)
oops did I say choose(15,2)
i meant choose(15,12)
errant bear
the total number of ways to choose 12 donuts from 4 is C(12+4-1,12)
what
how
@languid blaze
languid blaze
That's just the formula for finding combinations with repetition
Since we can repeat the donut types for when we choose
quick folio
wait for that qtn i think answer is just 9C3
cause its stars and bars so u are saying that let 6 in A indefinitely
so you are arranging 6 donuts to A B C D
since its at least 6 in A, A can have more than 6
etc
since donuts are unordered, repetitions allowed
errant bear
this has to be wrong??
weary tiger
@languid blaze it's a binomial distribution
Just consider X~B(12,0.25) where X is the number of type A donuts
and you want to find P(X>=6)
jolly ridge
I have discrete mathematics problem, about 8 queen problem.
I wrote 3 solution codes, with algorithm to solve it.
But the solution they're asking me is in a different format. Not code or algorithm kind of thing.
Can someone please help me to convert my code/algorithm in this type of answer.
Or make me understand what is this.
jolly ridge
how did u find the locations of influence <@!712442986654597140>
I didn't solve it, this solution was given with the question itself. As an example.
I solved remaining 3 solutions. But in C code format. I just don't know how to convert it in this type of mathematics language
quick folio
send ur code over
jolly ridge
Okay, I'm sending the first one first
#include <stdio.h>
#include <stdlib.h>
int count = 0;
void solve(int n, int col, int *hist)
{
if (col == n) {
printf("\nNo. %d\n-----\n", ++count);
for (int i = 0; i < n; i++, putchar('\n'))
for (int j = 0; j < n; j++)
putchar(j == hist[i] ? 'Q' : ((i + j) & 1) ? ' ' : '.');
return;
}
define attack(i, j) (hist[j] == i || abs(hist[j] - i) == col - j)
for (int i = 0, j = 0; i < n; i++) {
for (j = 0; j < col && !attack(i, j); j++);
if (j < col) continue;
hist[col] = i;
solve(n, col + 1, hist);
}
}
int main(int n, char **argv)
{
if (n <= 1 || (n = atoi(argv[1])) <= 0) n = 8;
int hist[n];
solve(n, 0, hist);
}
How did it happen, I mean it's not readable
How do I send it properly
quick folio
#include <stdio.h>
#include <stdlib.h>
int count = 0;
void solve(int n, int col, int *hist)
{
if (col == n) {
printf("\nNo. %d\n-----\n", ++count);
for (int i = 0; i < n; i++, putchar('\n'))
for (int j = 0; j < n; j++)
putchar(j == hist[i] ? 'Q' : ((i + j) & 1) ? ' ' : '.');
return;
}
# define attack(i, j) (hist[j] == i abs(hist[j] - i) == col - j)
for (int i = 0, j = 0; i < n; i++) {
for (j = 0; j < col && !attack(i, j); j++);
if (j < col) continue;
hist[col] = i;
solve(n, col + 1, hist);
}
}
int main(int n, char **argv)
{
if (n <= 1 (n = atoi(argv[1])) <= 0) n = 8;
int hist[n];
solve(n, 0, hist);
}```Which part am I wrong?
raven python
Is there any efficient way to compute the number of elements in a Minkowski sum of two sets? I'm trying to find the best way to deal with that in terms of space complexity. The Minkowski sum of sets A and B is a set A+B = {a + b : a \in A && b \in B}
tired hawk
Is there any efficient way to compute the number of elements in a Minkowski sum ...
Define X = {a-a' | a , a' € A, a ≠ a'} and Y = {b-b' | b , b' € B, b ≠ b'}. Then, |A+B| = |A||B| - |X intersection Y|
Idk if it helps
raven python
😮
raven python
Idk if it helps
It does! Thank you 😍
tired hawk
:)
tired hawk
Define X = {a-a' | a , a' € A, a ≠ a'} and Y = {b-b' | b , b' € B, b ≠ b'}. Then...
Wait it's a bit wrong
raven python
I'm just wondering about one thing. Should the subtractions in X and Y be positive?
tired hawk
You need to make X and Y into multisets
tired hawk
I'm just wondering about one thing. Should the subtractions in X and Y be positi...
Yeah that too, we don't consider a'-a if a-a' has already been considered
So X = {a-a' > 0 | a , a' € A} and likewise for Y should work, with both being multisets
raven python
I'm not sure if this already works. If A = {1, 2, 3} and B = {5, 6, 7}, A+B = {6, 7, 8, 9, 10}, but X = Y = {1, 1, 2}. You gave me an idea how to think about it, though, so I'll give it a thought once more a bit later. 😄 Thank you for the help
tired hawk
I'm not sure if this already works. If A = {1, 2, 3} and B = {5, 6, 7}, A+B = {6...
Interesting... I'll think about where it went wrong. Thanks for pointing it out!
Okay I realised the mistake but it's a bit hard to state exactly... Anyway since you understood what I was trying to do you'll understand the mistake as well! I'll see if I can think of something better.
keen girder
assuming n starts from 2, floor(2n/3)
coral raven
$\frac{2}{3}n + \frac{2\sqrt{3}}{9}sin(\frac{2\pi}{3}n)$
vital dewBOT
Kaisheng21
solemn quail
**Kaisheng21**
whoa this looks scary hhh
keen girder
lol
solemn quail
assuming n starts from 2, floor(2n/3)
thanks alot !!!!
could u explain how did u figure it out ? if dont mind !
coral raven
so the 2/3 comes from the fact that overall, for every increase in n by 3, the total count increases by 2
coral raven
WAIT NO
IT'S WRONG NOOOOOO
$\frac{2}{3}(n+1) + \frac{2\sqrt{3}}{9}sin(\frac{2\pi}{3}(n-1))$
vital dewBOT
Kaisheng21
coral raven
ok fixed
tawdry edge
Can someone help me understand transitive proofs?
I did reflexive and symmetric
I just don
don't get how to finish a transitive proof
supple cargo
$x^2-y^2 = 2(y-x) \iff x^2-y^2-2(y-x) = x(x-2)-y(y-2) = 0$
$\Rightarrow y(y-2)-z(z-2) = 0$ as yrz
$\Rightarrow x(x-2)+y(y-2) = y(x-2)-z(z-2) = 0$
$\Rightarrow x(x-2) - z(z-2) = 0 \iff xrz$
lets hope this processes correctly
or at all lol
supple cargo
anyway I think you can still get the gist from the latex
supple cargo
ok so you rearrange x^2-y^2= 2(y-x) into x(x-2)-y(y-2) = 0
then y^2-z^2 = 2(z-y) into a similar expression
then equate them, getting x(x-2)-y(y-2) = -(y(y-2)-z(z-2)), and cancel the y(y-2)s giving you x(x-2) = z(z-2) => x(x-2)-z(z-2) = 0 => xrz
coral raven
well you really want to equate the negative of the second one
tawdry edge
lol
couldn't you just use the premise of the transitive
and add the two together
they equal to the corollary
austere marten
,
keen girder
4+4!
weary tiger
thanks
keen girder
np
keen girder
it seems i got mentioned here, did you perhaps had another question?
weary tiger
it seems i got mentioned here, did you perhaps had another question?
yeah, i got infinite walks from a to c and 4 paths from a to c, is that right?
keen girder
well since in a walk you can have multiple repeated vertices and edges, so yes, there must be infinite ways to reach a->c. Now a path is simply a walk with no repeated vertices so again, yes, there is only 4 possible paths.
weary tiger
Thanks.
keen girder
np
weary tiger
How do you conclude that the statement or mathematical induction are invalid?
tawdry edge
Can someone actually explain the difference between combination and permutation for me?
like, I understand the formula difference
via the factorial definition, but I am struggling to understand when to use which in the face of like a word problem
coral raven
combinations are when you don't care about order, permutations are when you do
there are 6! = 720 permutations of '123456', but only one combination
keen girder
If you are struggling to understand when to use it, then I think you just need to practice more and more by going through examples first.
tawdry edge
Unfortunately, I'm lacking in finding examples
but I hear the word "order" used a lot
when talking about combinations
or permutations
so in a permutation, since it is 6! and represented like 6 * 5 * 4 * 3 * 2 * 1
we are losing an option upon every selection?
Like if I wanted to find out how many ways to select a 10 person committee out of 100 people, would permutation be the right choice?
keen girder
well does the order matter here?
tawdry edge
I'm going to say no, in the sense that the committee can be arranged without the need for a specific order
however, we have to make sure that if someone is selected to the committee, they are no longer within the pool for options
which I think the combination formula and factorial cover...
tawdry edge
How do I prove if m^2 | n^3 where m, n > 0 are integers, then m | n?
keen girder
first of all what does it mean to divide?
and do you think this proposition is true?
proven garnet
How do I prove if m^2 | n^3 where m, n > 0 are integers, then m | n?
Take $n =2^6 + 2^4, m=2^6$. Then $m^2|n^3$ but $m$ does not divide $n$.
vital dewBOT
andreO
candid chasm
how do i negate (forsome x p(x))
im not sure if the negation applies on the p(x) bit too
the answer i came up with is forall x p(x) im not really sure tho
pale epoch
well
if p(x) is true for all x, it's certainly true for some x
so that can't be it, right?
candid chasm
if p(x) is true for all x, it's certainly true for some x
yah isnt that correct?
pale epoch
didn't you want to negate it
keen girder
$\neg \qty(\exists x \in S, P(x))$
vital dewBOT
zslya
candid chasm
how do i negate (forsome x p(x))
yah im supposed to negate this but im not too sure if there is such a thing of negating p(x)
pale epoch
if the negation of your statement implies the original statement, that's an issue
pale epoch
you can negate the p(x) fine
the "opposite" of "there is some x with property p" is "there is no x with property p"
or "all x do not have the property p"
candid chasm
so it would be forall x ~p(x)
pale epoch
indeed
candid chasm
ohh i understand now thanks alot really appereciate it
pale epoch
you're welcome
candid chasm
appreciate*
tawdry edge
I am confused by this...
I need to use the injective and surjective definitions to prove bijectivity
but I don't see how I can do this algebraically with abstract constants like A and B
gritty crescent
@tawdry edge Treat them like you'd treat any constant, like 5.
gritty crescent
For injectivity, you want to show that $$g(x_1)=g(x_2)\implies x_1=x_2.$$For surjectivity, resort to the usual technique of setting $y=g(x)$, and then expressing $x$ as some function in $y$
vital dewBOT
Manan.
gritty crescent
thanks, I did A,B = 1
Good job!
tawdry edge
i'm just stuck no a equivalence proof rn
gritty crescent
Equivalence relation?
tawdry edge
It just sucks that there is no universal like method for solving these problems
yes
Like, I'm understanding the reflexive, symmetric, and transitive properties of relations
but like
gritty crescent
It just sucks that there is no universal like method for solving these problems
That's somewhat the point of non-algorithmic maths, you have to think in order to solve.
tawdry edge
It seems like the proof is different when like proving
7 | (2m + 5n)
then like
some expression
Can't think of a counter example rn
gritty crescent
Like, I'm understanding the reflexive, symmetric, and transitive properties of r...
Reflexive means every element relates to itself. Figure out if your relation makes any exception to this.
Symmetric means your relation kinda doesn't discriminate (is symmetric) between the pair (a,b) and (b,a); existence of one should imply the other.
Transitive means your relation allows for some extrapolation: if you know (a,b) and (b,c), then (a,c) should follow. The techniques of proof dabble around this intuition and the definitions.
gritty crescent
7 | (2m + 5n)
What is your domain for m and n?
This breaks down for something as simple as m=1 and n=2
tawdry edge
well, the domain is on Z
but m = 1 and n=2 couldn't be in the relation becasue 7 | 12 is not true
because the expression is
mrn iFF (if and only if) 7 | (2m + 5n)
gritty crescent
Ah, okay.
So let's check if this is reflexive.
For this, you want to check if (m,m) is in the relation for all integers m.
gritty crescent
Yep, 7|7m so we're done.
Okay, let's suppose (m,n) is in the relation, that is, 7|(2m+5n); we now want to check if for every such pair, (n,m) is in the relation too.
tawdry edge
I added up my expressions
like
I did 14k = 7m + 7n
using the division definition
7 | (2m + 5n) then 7k = (2m + 5n)
k being some inteer
is this valid proof?>
gritty crescent
This doesn't say anything about (n,m) being in the relation. You want to be able to say something about the statement 7|(2n+5m) when (m,n) is in your relation.
gritty crescent
Let's see a few values of (m,n) for which the statement works. m=n=1 works
And so does every value for which they are equal
We need to see if there is some non-trivial value of (m,n) for which 2m+5n is divisible by 7
Do you have any tools at your disposal to talk about it?
Okay, I finally have a non-trivial example
m=22 and n=1 gives 2(22)+5(1)=49, which is indeed divisible by 7
Now observe that 2(1)+5(22)=112, which is again a multiple of 7. Seems to reinforce the belief that this is symmetric, but this is still not a proof.
Okay so I figured it out with someone's help
vital dewBOT
Manan.
gritty crescent
And hence your relation is symmetric
Maybe use a similar argument for transitivity
tawdry edge
can't figure it out
unreal stump
Let (m,n) and (n,o) then 7|2m+5n and 7|2n+5o implies 7|2(2m+5n)-5(2n+5o) implies 7|4m-4o Implies 7|4m+10o implies 7|2m+5o
@tawdry edge
tawdry edge
I always figure it out moments before someone posts lol
sage dust
Does anyone understand 2nd order iterative methods?
In particular b) and d). I've already done 1a) and understand it fully, but proving convergence is kinda difficult and i dont understand it well
lavish patrol
I always figure it out moments before someone posts lol
big brain moments
weary tiger
Can I get help with this problem?
supple cargo
the inductive step is wrong I think
wait nvm just re-read it
I think it's all fine
robust mango
isnt the inductive step wrong
weary tiger
why would it be wrong?
robust mango
we assumed 2^k > 2k, how do they get 2 * 2^k > 2 + 2k
when it should be 2 * 2^k > 2(2k)
supple cargo
good spot
weary tiger
why wouldn't it be 2 * 2^k > 2(k+1)
supple cargo
$22^k > 22k=4k>k+1$ for $k>3$
vital dewBOT
Wew Lads Tbh
lucid ingot
they havent mentioned 2k + 2k >= 2 + 2k
knotty badge
Now is anyone trying to do something beyond clutch as fuck
Here me out now. I have an exam tomorrow at 8 on respondus browser which is disguisting. However comma , I have 2 computers. whose tryna let me send them questions and help a man out
knotty badge
thanks chief
another question .. any help : Devise a divide-and-conquer algorithm to findanmodm, wherea, m,andnare positive integers.
sly turtle
Is this as simple as it seems?
f: A-> B is not one to one
f: A-> B is not onto
last flicker
"useful" is a pretty broad word but i'd guess your professor is looking for something a little different than that lmao
a more "useful" way to negate a) would probably be to negate it from this definition, by fucking around with the quantifier
sand cipher
need help
is R={(-3,15),(-3,16),(-3,17),(-3,-18),(-3,-21),(5,15),(5,16),(5,17),(5,-18),(5,-21),(7,15),(7,16),(7,17),(7,-18),(7,-21)}
and for
a). it's a no because 1x value and 2y or more value is not a function (since x there exist A and y there exist B
pale epoch
what makes you think R looks like this
for a) just give a specific counterexample if you think the answer is no
pale epoch
what makes you think R looks like this
you just wrote down the cartesian product of A and B
did you even read how the relation is defined
sand cipher
did you even read how the relation is defined
is this R? R={(-3,15),(-3,-18),(-3,-21),(5,15),(7,-21)}
pale epoch
looks better
sand cipher
R is not a function because it is not right-unique. for example (-3, 15) and (-3, -18) are both in R
weary tiger
why is that called right-unique?
to me left-unique would make more sense as a name cuz theres (at most) a unique tuple for any left element
sly turtle
Not sure where to start I guess I don't even understand the part I need to prove. So A/R is the quotient space of A over R, this means that it is the family of all equivalence classes in A, and f(A) is the image of A under F. And I understand ~ as meaning there is a bijective function from A/R to f(A) ? I think I understand the components of the question but I don't know how to find out what that function is
stray reef
its easier to find than you think
you dont rly need to look far
||f itself will do just fine||
fiery hare
Is the set { 2·q | q is rational } equal to the set of rationals or a strict subset?
(Sorry if it is not the appropriate channel. I asked this in #help-0 yesterday but no one wanted to discuss this, so I guess it wasn't appropriate either. Sorry. This is more related to Real Analysis)
This is my rationale behind it. But I don't know if it's cyclic, convincing or not.
fiery hare
Ah I guess this is a particular instance of closure under multiplication (and division). Which the internet says it is true so I will take it.
obtuse minnow
Um, do you know how to show two sets are equal?
Set A and B have the same elements if everything in A is in B and everything in B is in A.
Q` takes all things in Q and divides by 2.
Let q' be anything in Q' and q be anything in Q. We need to show q' is in Q and q is in Q'.
weary tiger
IDK if it's one of those subjects where it's hard at start or my teacher is not teaching discrete maths well .
this is my first semester learning about discrete maths and I feel really confused .
Do you guys recommend any self-taught books for discrete maths ?
obtuse minnow
Generally, get an "easier" book and do all the problems (at least read through them if you have the chance). Also, though, a question: is there a particular topic you have questions about? Proof by contradiction? Maybe it's modular arithmetic?
weary tiger
Today is literally my second session , and my teacher just dumped on us bunch of formulas .
I'm familiar with most of them because our logical circuit teacher has taught us well , but there are also some elementary definitions which I don't understand with 1 short sentence , that's why I'm looking for a book to first learn and then answer some problems .
obtuse minnow
oh you mean each, for all, exists, etc.?
weary tiger
propositional logic
obtuse minnow
There's a lot of levels of logic. I'm guessing you guys aren't just doing syllogisms?
I am unable to point you to help if you don't tell me what the next test is on?
very basic stuff varies widely. 🙂
weary tiger
Let me rephrase my question , imagine I haven't learned anything about the subject and I have no teacher .
What book can help me self - teach this subject ?
fiery hare
There is How To Prove It that helped me learn how to structure the ideas for proving.
Fairly lightweight introductory yet satisfying book imo
obtuse minnow
Er, I'd recommend Amazon.com if you don't get any other solid recommendations. I swear I don't work for them. Just check out the ratings and reviews. (I must bow out of this conversation -- it's been years since I learned that and we used notes from our professor(s))
fiery hare
Set A and B have the same elements if everything in A is in B and everything in ...
Yeah, that's what I tried to do there, but the part with q = 1/2 · 2q assumes that 2q is in Q and so will be q'. But I think I should have been explicit why that part is true: because of closure under multiplication and (kind of) the definition of rationals.
obtuse minnow
so yeah variables should be named to not cause confusion. I messed up on that. Let's rewrite a bit here.
I want to show everything in Q' is in Q. I dunno how deep your professor wants this, I'm hoping he/she doesn't want more detail than this:
Let q' be in Q'. By the definition of in being Q', q' is 2(t) for some rational t. By being rational, t is n/d for some integers n and d where d is not zero. So q' is (2n)/d. 2n is an integer and so is d and also d is nonzero, so by this fact (2n)/d, otherwise known as q', is also a rational and that means q' is in Q.
We then have to show everything in Q is in Q'.
fiery hare
I want to show everything in Q' is in Q. I dunno how deep your professor wants ...
Ah that's much nicer explicitly leveraging the definition of rationals, yeah. (Also there is no professor, just for myself) Thanks!
weary tiger
Can someone please clarify why the number of non-negative integer solutions to the equation x1+x2+...+xn = r is given by the unordered selection of r elements from a set of size n ie (n+r-1)C(r)?
shouldn't it be (r-1)
@weary tiger
But if you're familiar with stars and bars imagine you have n+r-1 'slots'
oh mb i misread
I'm mainly referring to the explanation in the notes but I've heard about the "bosons" in combinatorics
yeh so its correct but the more useful form to have it in is (n+r-1)C(n-1)
imagine we have n+r-1 slots
and we choose (n-1) places to put a bar
then the slots are now seperated into n parts
of which sum to r
fiery hare
I assume replacement. Now imagine you start with 0 and are only allowed to add. You can add r 1s and get r, i.e. 1·r. You can add one 2 and r-2 1s and one 0, i.e. 2 + 1·(r-2) + 0. You can add one r and r-1 0s, i.e. r + 0·(r-1). Hope you see where this is going.
weary tiger
each choice where you place bar corresponds to a unique solution and there are (n+r-1)C(n-1) ways to choose the bars
fiery hare
Hmm, nvm, you can't have replacement or 0 🤔
weary tiger
Hmm, nvm, you can't have replacement or 0 🤔
The formula refers to an "unordered selection with repetition"
you can have 0 + repetition
fiery hare
Ah then what I said makes sense
weary tiger
just look at this though specifically 'Theorem Two'
getting used to this idea will be v helpful for combinactorics
Alright will do thanks!
The idea of bosons wasn't introduced in my discrete maths course
Strangely
ngl idk what ur talking about
when u say bosons lol
"indistinguisable objects" lmao
ah
Anyway
Why is it true that we can represent a collection of non-negative integers by choosing from the set {1,..,n}? Is it because we can construct an obvious bijection?
the idea being that
for each time you pick i you add 1 to x_i
weary tiger
for each time you pick i you add 1 to x_i
x_i?
x_i being the i'th element of the n tuple? idk
it's defined on the page
but as it says the idea is you are picking r elements from a set of size n where ordering doesn't matter
Ok I sort of get the idea
You pick x1, x2...,xn elements by choosing from the set {1,...n} with repetition
quick folio
@weary tiger what book is that
weary tiger
<@456226577798135808> what book is that
The lecture notes at my uni
quick folio
could you share 🙂
ill share mine too
or is it off limits
i completely understand otherwise!
weary tiger
Nah I think it should be fine
What chapter are you interested in?
It's the Counting part I was sharing
quick folio
what do u have
weary tiger
x_2 be how many 2s you pick and so on
Gotcha
quick folio
lilike on what parts
weary tiger
what do u have
Counting, Recurrence relations, Graph Theory, Coding Theory
@weary tiger regardless though you should look at the thing i linked
theorem two is exactly what you want
quick folio
Can you share on counting and graph theory 🙂
I have
Set theory Counting, recurrence, graph, Proofs
weary tiger
Sure
valid wave
hi
when doing induction proofs
that k+1 on the Right Hand Side
for the 3n^2+3n-1
would the k+1 add up to make it
3k^2+3k+1
or like some weird 3(k+1)^2+3(k+1)-1
coral raven
if you're going from k to k+1, it would go to the second one, yes
you would have to do some rearranging
coral raven
similarly for the other terms
valid wave
but i guess my questions stems from
whats the difference with the
(k+1) + 1
and the last 3(k+1)^2+3(k+1)-1
cause now k+1 is being squared and all that
candid chasm
i dont get the point of questions like this, are we trying to get which variable has the most impact on the answer or is it just that we want to find an exactly equal statement which would be: p v (~p v q)
robust mango
p implies q is equivalent to ~p v q
so ~p implies (~p v q) is equivalent to p or (~p v q)
now just simplify that
if the word simplify applies here
candid chasm
yah i got to that point but idk if p v (~p v q) is equivilant to just p
cuz i think both only depend on p since q doesnt matter either way
supple cargo
p v ~p is true
I just wrote out a massive truth table and I got that ~p -> (~p v q) is always true
candid chasm
ohhh so since its always true its just true i get the point now thanks alot guys really apperciate it
appreciate*
weary tiger
We are looking to seat 7 people around a circular table and this can be done in 6! ways (by fixing the position of the first person and ordering the remaining 6). For when 2 particulars wish to be seated together, we can treat them as one person and order the 7-1 = 6 persons in 5! ways. Ordering the 2 people among them we get 2x5! orderings. Now when 3 particulars wish to be seated together, we adopt the same technique and consider them as 1 person. Shouldn't this be the same as the previous case ie. we get 3!x5! orderings? The solution says we have to order 5 people instead of 6 and I can't figure out why this is the case
kind geode
hey i have a simple question but im not sure if im right, if you roll a fair purple and orange dice, what is the probability that the sum of the dice being 6, given that the orange one will always roll even -> this would just be P(e1|e2) which would end up being 2/5? rgt as P(sum 6 | even) would be 2/36 and p(sum 6) would be 5/36
distant bobcat
Is it true that if $P \neq NP$ then $NP \neq coNP$?
vital dewBOT
Fredrikpiano
mystic moss
Is it true that if $P \neq NP$ then $NP \neq coNP$?
why would you expect this to be true?
distant bobcat
@mystic moss well isnt the converse true if P = NP then NP= coNP? Or maybe I'm confused...
supple cargo
#proofs-and-logic moment
distant bobcat
It would mean that the complement would not decide a language in polynomial time for $P \neq NP$ right?
vital dewBOT
Fredrikpiano
abstract otter
hi, can someone help me starty this problem?
I'm playing around with the identity sum of (nk) = 2^n
but Im not sure if that's the right direction
mystic moss
It would mean that the complement would not decide a language in polynomial time...
hm?
oak lichen
anyone know how to prove this with pigeonhole principle?
well, think about the n-1 case as a starting point (often useful when doing pigeonhole imo). Then think about how that nth value both fills the whole and can't exist twice
fallen vigil
well, think about the n-1 case as a starting point (often useful when doing pige...
idk it doesn't really seem to make a difference whether it's n or n-1, like 3+1, 3+2, 3+3, 3+4, 3+5, 3+6, 3+7, 3+8, 3+9 if n = 10
if the set started at 3
oak lichen
well, it does matter quite a bit actually
suppose you took n - 1 values from n = 10, then I could pick 11-19 (9 values), and you'll note that none of them are divisible by 10
as for your example, it's true that you'll have a divisible number at 3+7, but that's just cause you decided to start at 4, if that makes sense
distant bobcat
@mystic moss nevermind, I realized I could just prove the contrapositive case.
oak lichen
well, so it matters where you start the run of integer numbers. If you start at n+1, you'll always hit a number divisible by n at exactly 2n. If you start elsewhere, though, you might hit a number divisible by n "earlier". For example, if you have n = 10 and start at 24, you'll hit a divisible number at 30 (24 + 6), which is before n - 1.
In summary, the n - 1 only matters when you start at m * n + 1 for some positive integer m, if that makes sense
fallen vigil
oooh, so basically the foundation of the proof is that numbers divisible by n occur every n rather than n-1
quick folio
we can create partitions of
[0] ... [n-1] from n consecutive integers, because of residue classes of n
if you have n terms, all those terms are bijective to those partitions listed above
so there is exactly one in n consecutive terms
abstract otter
so my idea for this is that
base case: the string starts with 1, the remaining n-1 string start with either 0,1 or 2
which is a_n-1 strings
case2:
the string contains only 1s
which is 1 possibility
and case3:
for each k between 0 and n-2, there are n-k-1 possibilities of "sequences" of 1s which is followed by either a 0 or a 2
which is is 2*a_k possibilities
am i on the right track?
this is very similar to this:
i'm also getting the same answer even though the question is different
balmy hornet
is this statement an equivalence relation? "The state of Illinois is within United States of America. Chicago is within the state of Illinois. Andersonville is within Chicago."
urban saddle
how can I prove this?: if a/b then a/b*x
I'd put it like this: that if b = a * k1, then b*x = a * k2 (btw a,b are in Z)
but I'm not sure what to do now, am I looking if k1 = k2?
urban saddle
how can I prove this?: if a/b then a/b*x
I'm not sure it this checks out either tho
pale epoch
does / mean divides?
urban saddle
yes
urban saddle
b = a * k1, k exists in Z
pale epoch
and a/bx then is?
urban saddle
b*x = a * k2
pale epoch
precisely
so now you want to find such a k2 given that a k1 exists
so b*x = (a * k1) * x
this follows from a/b, right?
urban saddle
yep
pale epoch
and now, can you find a k2
urban saddle
so solving for k2 right? i get k2 = k1 * x
urban saddle
alright, thank you!
weary tiger
Can someone help me with this prob I’m struggling with it
quick folio
did srk just ask a matrix qtn in discrete
naive marten
if i had something like aRb where a <= b, would we be able to call that symmetric?
im thinking that's definitely reflexive right? since a = b is possible
but with reflexivity i feel confused
unless im confused abt both then woo hoo
gritty crescent
im thinking that's definitely reflexive right? since a = b is possible
More like, it is only symmetric when a=b and fails whenever a<b. Hence it is not symmetric(failure in even one case suffices to determine this).
naive marten
would you call it reflexive then?
gritty crescent
Tell me, what do you think?
gritty crescent
Correct.
naive marten
which means it is no longer reflexive
now let's say we threw another term in... uhhhh
2a then
a<=b<=2a
gritty crescent
which means it is no longer reflexive
How did this follow?
gritty crescent
Recall your definition of a reflexive relation.
gritty crescent
reflexitivity has to be true for all
Correct.
naive marten
aRa for all a
gritty crescent
Exactly
naive marten
now adding a 2a term
naive marten
at the end shouldnt change anything for those two
gritty crescent
Why are you working with 2a?
gritty crescent
Are you checking transitivity?
naive marten
if this was the equation
yes
well now i am
but i wanna know if my assumption that it doesnt affect symmetry is true
gritty crescent
Let's summarise what you have so far.
naive marten
i figure it doesn't
gritty crescent
- R is reflexive, since aRa is true for all a in your domain.
gritty crescent
- R is not symmetric, since it fails whenever a<b.
Now on to transitivity
Suppose aRb and bRc
aRb tells you a<=b
bRc tells b<=c
naive marten
and bRc would tell us b <= c
gritty crescent
Correct!
gritty crescent
Yep!
gritty crescent
(although avoid using 2a, since it may or may not be an element of your domain. Just say c is some element in your domain)
naive marten
if there's 1 case where a <= b and b <= a
gritty crescent
Yep
naive marten
which would be a = b
then it is not antisymmetric either
so this case would be
reflexive and transitive
gritty crescent
Sounds right.
naive marten
awesome
gritty crescent
Hmmm, I'm a bit irked by not being antisymmetric here though. Your argument seems on point as well.
Okay wait
This is antisymmetric
Observe that aRb and bRa here implied a=b
gritty crescent
Which is the very definition of anti-symmetry
gritty crescent
naive marten
could you help me w clarifying a couple things about well ordered as well?
gritty crescent
Sure, go ahead.
naive marten
alr one sec
so what i'm gathering is something along the lines of
for every possible subset of a set
there is a least element?
assuming not {}
so i guess {1,2,3,4,5} would be well ordered
gritty crescent
there is a least element?
This may not be true in general
Set theory becomes more intricate when your sets become larger.
gritty crescent
Otherwise a simple example of not having a least element is the open interval (0,1), which is a subset of real numbers.
The infimum here is 0, but is not contained in the subset itself
gritty crescent
No, it is not well ordered iirc.
naive marten
in class i was told that {integers} was not well order
which confuses me
because i feel as if that'd be the same situation as here
gritty crescent
Tell me the smallest element in the subset of negative integers
naive marten
-inf
naive marten
mmmmmmmmmmmm
so then would it not be -999999999999999999999 infinite times?
that's not the same case as .00000000000000000000000000001 infinite times?
gritty crescent
I'm just here to call you out if you say something dumb, no pressure
Fuck you 
gritty crescent
Well
Not every subset of R does
(-∞,0) for example
Has no lower bound within R
naive marten
so the easiest way of looking at this is
gritty crescent
"∞" is symbolic here, it is not an object within reals
gritty crescent
The thing to remember is that stuff gets wonky with infinite sets, so one must be careful extrapolating ideas from finite case to the infinite case.
quaint star
so then would it not be -999999999999999999999 infinite times?
Do you understand the issue with this? There is no number like this. You cannot have infinitely many digits before the decimal point, only after.
quaint star
mathematical construct
quaint star
But everything in math is a mathematical construct
So that doesn't mean it doesn't exist
quaint star
It just isn't a construct that applies here
naive marten
i think
yea
okay last thing now uwu
if i needed to write the equivalence classes of somethinig like
a+b = c+d
a,b related c,d (assuming we're given a domain that's like {-5 to 2} x {5 to 9} or whatever)
what would the notation look like
quaint star
How do you normally write equivalence classes?
naive marten
we draw arrow diagrams
and then we blob them
boom
obviously this isnt the right way
but we touched on proper notation for like 2 seconds and moved on
quaint star
I'm shook
naive marten
based on a fast google it should look smt like
[a] = {}
but like where i'm lost is like
quaint star
There are many ways to write equivalence classes. Normally the equivalence class of x is written [x]
naive marten
what does [a] represent
quaint star
It's the equivalence class of a
naive marten
so is a the relation?
taking a quick look here this guy has
[1] [2] [3] and so on
quaint star
Yes
naive marten
so if it's reflexive
we can assume the equivalence classs of 1 is at least
{1}
not the right terminology
but
yk
at the smallest its {1}
quaint star
You don't talk about equivalence classes unless you have an equivalence relation. All equivalence relations are reflexive. So, [x] always contains x, yeah
quaint star
Please include brackets for pairs
naive marten
{0 to 2} x {0 to 2}
mb
a + b = c + b
(a, b) R (c, d)
was going a lil fast and got lazy
anyw
our class would probably be smt like
[(0,2)] = {(0,2) and literally anything else that = 2}
so (2, 0) included too?
i've no idea if this is an equivalence relationm
i sure hope it is
naive marten
[(0,2)] = {(x,y): x+y = 2 }
had i listed everything 1 by 1
it would still be right
right
quaint star
What's your domain?
quaint star
[0,2] x [0,2] or {0,1,2} x {0,1,2}?
quaint star
Yes, then you can list them all
naive marten
okie
yayayay ty
@gritty crescent thank u to u too
although u seem to fear luna
but thats ok
gritty crescent
No worries; goodluck!
gritty crescent
although u seem to fear luna
naive marten
how do you guys study this subject?
quaint star
I told him to continue, but then he ran away 
naive marten
idk where else to get resources for this
gritty crescent
