i tried drawing it but got stuck there
#discrete-math
wild peak
deft dock
bruh you still helped this clown what a great man
cerulean wind
felt bad lmao
wild peak
how do i do this
proven silo
please help if possible thank you guys\
Find what elements the set S_3 contains and what elements the set S_7 contains
upbeat lance
Greetings, I'm trying to understand the GCD of two polynomials. My problem resides within the "greatest" identity. Let's suppose for example we were given two GCD's for A(x) and B(x). One is correct and one is false. They both divide each other but one polynomial is greater than the other. Only solution is to compare the two no? But wouldn't this identity be hugely dependent on the domain wherein we're looking for the GCD?
quaint star
A(x) divides B(x) and B(x) divides A(x) implies that A(x) = k B(x) for some constant k. So, there are two possible definitions. Either you allow multiple GCDs for A(x) and B(x) or you restrict the GCD to be the monic polynomial (it's leading coefficient is one), and doing this makes it unique
Since A(x) and B(x) cannot both be monic unless k = 1 which means they are equal
@upbeat lance
upbeat lance
A(x) divides B(x) and B(x) divides A(x) implies that A(x) = k B(x) for some cons...
I suppose the multiple GCDs for A(x) and B(x) would vary on the domain of study right?
quaint star
I'm not sure what you mean but I think yes?
If you are looking at polynomials, you will be looking at polynomials where the coefficients come from a specific ring. k comes from that ring.
If you are just talking about real polynomials, and you mean like their domain as functions then no it is independent of that.
obtuse lance
for example, A(x)=(x+1)(x+2)(x+2) and B(x)=(x+2)(x+3) then the GCD would be (x+2) since it's the greatest thing that divides both A(x) and B(x) @upbeat lance has nothing to do with how large they get when you plug in numbers to them
quaint star
To add to the example, if you consider them as polynomials over Q or R, then 2x+4 also divides both. But we choose x+2 to be the gcd because it is monic.
upbeat lance
for example, A(x)=(x+1)(x+2)(x+2) and B(x)=(x+2)(x+3) then the GCD would be (x+2...
Let's say for example: $A(x)=(x-1)^2(x-3)^3$ and $B(x)=(x-1)^3(x-3)^2$ If we plug in numbers how we know which is greater $(x-1)^2$ or $(x-3)^2$. My apologies, I'm a tad bit confused.
vital dewBOT
hwaydjaj69
obtuse lance
@upbeat lance has nothing to do with how large they get when you plug in numbers to them
it's just about the most divisors they share in common
what's the "greatest" power of (x-1) that divides A(x) and B(x) in your example?
it's just (x-1)^2
but we include everything
the greatest common divisor of your A(x) and B(x) is (x-1)^2(x-3)^2
upbeat lance
all clear now, that went over my head.
obtuse lance
lol
if it 'went over your head' that means you don't understand it which means it's not 'clear' 😵
upbeat lance
if it 'went over your head' that means you don't understand it which means it's ...
Well I used to not understand it, after your explanation it's all good now x)
obtuse lance
gotcha, I see
obtuse lance
If you are looking at polynomials, you will be looking at polynomials where the ...
I think when they were saying 'vary on the domain of study' and you sorta took this to mean different areas of math and then switched to realizing they meant domain of functions, they were toast cause of the ring stuff lol
quaint star
weary tiger
can someone help
Two players alternate taking stones from two piles. A valid move is taking any (positive) number of stones from one of the piles or the same (positive) number of stones from both piles. Whoever takes the last stone loses. Who wins with best play if there are initially 7 and 11 stones in the two piles.
i believe that the goal is to make other player finsih off one pile
or leave an equal amount in both
then we win
wait, no
last stone means they can only take one stone
plucky slate
My thinking for this kind of problem would be: Put yourself in the game and see what happens
If there are 2 players and there are 2 piles of stones, 7 and 11 respectivly then we know there are 18 stones.
To win we must NOT take the last stone.
So here's my thinking.
To win you must keep the total number of stones odd until there is only one stone left on your opponents turn.
If that makes sense
crude nymph
Guys using rules of inference how can I show .∀x(d(x)∨ a(x)) the d(x) is true?
Or I was thinking, one of the premises are true so you get to choose which one you want to be true so d(x) is true is that wrong?
weary tiger
My thinking for this kind of problem would be: Put yourself in the game and see ...
ok
do you want to do a sample game?
elder berry
> Two players alternate taking stones from two piles. A valid move is taking an...
Often you need to rephrase the question and look at what's happening from a different perspective
Make a grid, or a coordinate system, and let the first pile be the x-values, and the second the y-values.
At each coordinate point, you can move left (take away stones from pile 1); down (take away stones from pile 2) or diagonally to the bottom-left (removing same amount of stones from both)
Doing so, and considering where faulty cases (cases where you lose) are, will lead you to the answer
weary tiger
um
elder berry
Also if you want we can try a round to see that I (Player 1) can always win in this case
elder berry
I'll go first (since I know the optimal strategy)
weary tiger
ok
elder berry
Start: Pile 1: 7 Pile 2: 11
I take 1 stone from both piles
End: Pile 1: 6 Pile 2: 10
Start: Pile 1: 6 Pile 2: 10
I take 1 from pile one
End: Pile 1: 5 Pile 2: 10
Start: Pile 1: 5 Pile 2: 10
I take 7 stones from pile 2
End: Pile 1: 5 Pile 2: 3
Start: Pile 1: 5 Pile 2: 3
I take 2 stones from pile 1
End: Pile 1: 3 Pile 2: 3
Start: Pile 1: 3 Pile 2: 3
I take 1 stone from each
End: Pile 1: 2 Pile 2: 2
Yeah, so let me show you how to make that table
weary tiger
you are so smart
elder berry
I am going to edit the above text* so I don't spam the chat
I will put L at all positions where if you start from there, you are guaranteed to lose, and W if if you start from there, you can play optimally to win
Basically on your turn, you want to go from W -> L, so that your opponent is in a losing block
weary tiger
right
elder berry
Obviously, if you have 1 stone left, you lose, you must take it right. So we put L there
elder berry
Check the table, we filled in the L's, but now my question to you, how can we reach the (1, 0) or (0, 1) situation with the moves available?
remember when I said we can move left, down, or bottom left?
weary tiger
yes
elder berry
Alright great, that means that every other position that can reach (1, 0) or (0, 1) is a winning one since it forces the player to lose
elder berry
7 W W W
6 W W W W
5 W W W W
4 W W W W
3 W W W W
2 W W W
1 L W W W W W W W W W W W
0 L W W W W W W W W W W
0 1 2 3 4 5 6 7 8 9 10 11
Alright let me explain the series of W's I just wrote
Oh I missed some...
Sec
Everywhere where I placed a W means that I can for sure reach an L by moving down, left, or bottom right
Do you agree with that?
Feel free to ask any questions if something confuses you
I have to get going, so @weary tiger you need to continue this process forward
From the above table, you know that (2, 2) is a losing square, so you put an L there, and that should tell you which other squares are winning ones.
Cheers
weary tiger
Do you agree with that?
yes
so the strategy is just to match the winning coordinates
thanks
wait
so, @elder berry
7 W W W
6 W W W L W
5 W W W L W
4 W W W L W
3 W W W L W
2 W W L W
1 L W W W W W W W W W W W
0 L W W W W W W W W W W
0 1 2 3 4 5 6 7 8 9 10 11
the squares
but could you explain to me what i would have to do to win?
please
tired nacelle
You need to choose and arrange 4 letters from the word NUMERICAL.
Show the steps to find how many ways are available if the four letter
word must begin and end in a consonant?
weary tiger
@elder berry ?
tired nacelle
actually i want to ask about that question
how to tho that
because i new about this subject
*do
weary tiger
@elder berry
elder berry
<@!206074524150530049>
Alright I'm back
weary tiger
good explanation?
We can solve this problem like a graph, with 7 on the y axis, and 11 on the x. THe losing coordinates would be (0,1) and (1,0). And, if we were to move on this graph, we could only move left, bottom, and bottom right.
Based on that, we can mark our coordinates.
7 W W W
6 W W W W
5 W W W W
4 W W W W
3 W W W W
2 W W W
1 L W W W W W W W W W W W
0 L W W W W W W W W W W
0 1 2 3 4 5 6 7 8 9 10 11
From W, we can always get to an L, based on our movements, and that is the goal on how to win. The optimal strategy is to make the piles match on of those coordinates.
It's fine, we need to complete the graph first
We now start with (2, 2), do we have a winning strategy if we are on that coordinate?
(recall that, if you land on a L, you win)
(We want on all moves to go from W -> L so that the opponent loses)
Can we go from (2, 2) to L in this case?
@weary tiger yes or no?
weary tiger
We now start with `(2, 2)`, do we have a winning strategy if we are on that coor...
we losew
weary tiger
Can we go from `(2, 2)` to `L` in this case?
yes
elder berry
yes
How? Can we go from (2,2) to L in one move?
(I should've said one move, but with that information is it still possible?)
weary tiger
we take away one from noth piles
elder berry
That leads us to (1, 1) which is a W
No matter what you try, there is no possible movement (given only going down, left etc) to reach an L in one move
So whoever is on (2, 2) will lose
Fill in (2, 2) with a L
Now, which coordinates directly lead us to (2, 2).
We know that if you go from (some coordinate) to (2, 2), you will win
What are those coordinates that in one move, lead you from where you were to (2, 2)
(name at least 2 for now just so I know you've understood it)
@weary tiger Could we go from (6, 2) to (2, 2) in one move? (yes or no)
weary tiger
ok
weary tiger
<@456226577798135808> Could we go from `(6, 2)` to `(2, 2)` in one move? (yes or...
yes
elder berry
Great, so (6, 2) is going to be a W since it is a point that directly goes to (2, 2) = L
So, from the point (2, 2), every point directly above is immediately a W, every point to the right of it is W, and every point directly diagonally to the top-right is a W
Try to fill the graph on your own now, if you get stuck ask me
weary tiger
so what does the graph look like now
elder berry
Did you try to fill it in?
elder berry
Here is the full solution, it's difficult to go step by step through text, so try and understand the write-up and also write the table in your notebook since it is rather difficult to see what is happening through text (the diagonals and what not)
Pile 1 stones
|
7 W W W W L W W W W W W W
6 W W W W W W W W W W L W
5 W W W L W W W W W W W W
4 W W W W W W W L W W W W
3 W W W W W L W W W W W W
2 W W L W W W W W W W W W
1 L W W W W W W W W W W W
0 • L W W W W W W W W W W
0 1 2 3 4 5 6 7 8 9 10 11 - Pile 2 stones
From the game rules, you start at (11, 7). First person to (0, 0) loses.
You can move: to the left, down, bottom-left.
•Going from W -> L means you are on a winning position, and you end your turn in a losing position - meaning the other player starts from a losing position (which implies they lose)
•Going from L -> W means you start from a losing position, and give the other player a winning position
•L -> L is impossible since if a winning strategy exists (which in our case it does), we made an error during the table construction
•W -> W means that a player had a winning strategy, but didn't play well enough and gave the possibility of the other player to win
A winning strategy is possible and player 1 wins all the time.
On their first move they should move to (10, 6) or (4, 7)*
After that they should always move from W->L to win. Q.E.D.
Ask me any question, no matter how dumb you think it may be, and I'll try to explain
weary tiger
ok
crude nymph
How do I prove with logical equivalencies that ∀x(P(x) v Q(x)) is equivalent to p(x).
cerulean wind
it’s not ?
if P(x) is false and Q(x) is true for all x, then P(x) and Q(x) is always true, but P(x) is false
weary tiger
```
Pile 1 stones
|
7 W W W W L W W W W W W W
6 W W W W W W W...
your solution is nice
weary tiger
help plz
gritty crescent
@topaz jacinth Looks good, although use the "=" symbol carefully
Like you start with x=(2k+1) and then =x^2 which is incorrect
Start with something like "Let x be an odd number. By definition, x=2k+1 for some integer k. Thus, x^2=(2k+1)^2..."
The argument is fine 
topaz jacinth
ok tysm 🙇♀️
arctic totem
@topaz jacinth this will be on a more personal opinion level, but also elaborating with deep explanation helps a ton! Something like:
We want to show that if x is odd, then x^2 is odd
Recall that the definition of an odd integer is x = 2k + 1, where k is an integer.
Then x^2 = (2k+1)^2.
=> 4k^2 + 4k + 1
=> 2(2k^2 + 2k) + 1
By definition, 2k^2 + 2k is an integer since k is an integer.
Let b = 2k^2 + 2k for some integer b
=> 2b + 1
Therefore, x^2 is odd.
Hopefully that made sense. I had a teacher explain to me that it helps a ton to mix logic and math with English to really get what you're trying to prove explicitly stated.
topaz jacinth
If I were to prove this by contradiction: if x^2 is odd, then x is odd. (p -> q)
I will assume that x is not odd/ x is even
And then I will prove that x is even, however, it will be that x has no way of being even if x^2 is odd
Since I assumed that x^ 2 is even, but at the same have proven that it is odd = since they contradict each other, then it will be that to assume to !q is false. And since (!q) is absurd, then q (x is odd) has no choice but to be true.
-- i don't know if i'm getting the general idea of contradiction right. am i on the right track >?
proven silo
No. You will then assume x^2 is odd and suppose for contradiction x is even. Then show this leads to a contradiction.
hidden crystal
div? how do i do this <@&286206848099549185>
proven silo
Check your definition of div
hidden crystal
figured it out
valid loom
You need to select 3 random balls from a box that contains 7 red balls and 5 blue balls. Report the steps to show the probability of you selecting all red balls.
guys I need help
should I use probability or combination to answer this question
weary tiger
let's say we have a function f:A --> B so A is a domain and B is the codomain right? why can't we just say that B is the range of a function? what's the point of a codomain?
stray reef
'range' is ambiguous in that it may refer to the codomain or to the image
weary tiger
I don't get why the concept of a codomain is useful
Like f:A --> B maps elements of A to B right? why would you use B if every element of A just gets mapped to a subset of B? why can't you just use the subset of B in the function definition "f:A --> B"?
hidden crystal
help
weary tiger
32/5 = 6.4 how would the ceiling and floor be negative?
hidden crystal
Ohhh it was a typo thanks
coral raven
Like f:A --> B maps elements of A to B right? why would you use B if every eleme...
functions are formally defined using domain and codomain
also, sometimes you might not know the image of f beforehand, but you still want to be able to say 'oh we don't need to worry about complex numbers, the output is going to be real'
quaint star
let's say we have a function f:A --> B so A is a domain and B is the codomain ri...
Sometimes it's not obvious what the range is, you just know that the range is a subset of the codomain
weary tiger
that makes sense
quaint star
Damn, sniped by Kaisheng
coral raven
np
quaint star
👍
pallid thicket
Hi everyone
I've been looking for a good material to learn and practice discrete math for computer science. I'm currently using the 6.042j math for computer science spring 2015 from mit but they don't upload the answwers to the exercises so I think this might not work as a good material.
Is there any good one?
quaint star
Not having solutions is not the end of the world imo. Most textbooks do not have solutions either.
If you are unsure about your solutions or are stuck on how to do a problem, you can ask for help here
pallid thicket
OK. Thanks
weary tiger
@arctic totemcorrect
dusk kindle
is <=>
and <-> the same thing? Is it just preference for how its written or is it two signs. My prof knows a good bit ab CS so I think he’s just using that cause of C++
pale epoch
there is a difference but its very subtle, most people just ignore it
actually let me rephrase: depending on author there might be a difference, but it does not matter to most people, so in your case they are probably equivalent
zinc karma
weary tiger
For this question T is a tree with 100 leaves. Prove that we can add 50 new edges to T, so that in the new graph G there will be no bridges Is the answer to connect all the leafs together?
ornate cliff
Saw this online. How is { } transitive and symmetric?
dense geyser
Saw this online. How is { } transitive and symmetric?
it's vacuously true, in a sense. There's no pair of elements that break symmetry, and so it's symmetric
same with transitivity
dense geyser
what are you trying to prove?
steep locust
I try to solve this recurrence .
weary tiger
Are there non isomorphic graphs that have 6 vertices and 3 leaves?
onyx zephyr
Anyone know any good resources for learning induction from scratch?
weary tiger
How to prove it by Velleman or Book of proof. Both of those books are available online.
onyx zephyr
Diff between the books and which one do you recommend? @weary tiger
crude nymph
just a question is (There is a cat that naps a lot)
Is that ^ or ->
cerulean wind
neither imo
gritty crescent
I'm a bit confused about regular languages (in the context of finite automata). A language is regular if it is recognised by some finite automata. Can I not make every language regular with an automata that has only one state? (All symbols in the alphabet lead to a loop)
Point being the machine that doesn't keep a track of the string at all can accept any language
sacred spindle
If your TM accepts a string not in the language, then it doesn’t recognize that language
gritty crescent
Ah, okay
Thanks!
I'm trying to prove that the class of regular languages is closed under union.
Consider any two languages L1 and L2. We change the alphabet of L2 by replacing each symbol a by a', so as to completely distinguish it from the underlying alphabet of L1. (This is also the bit I'm not sure about). A new finite automata can be constructed to accept L1\cup L2 as follows: the starting state sends a string to "starting state" of L1 if the input character is from its alphabet, and to "starting state" of L2 if the input character is from the latter's alphabet. The automata accepting both languages are simply replicated thereby, and thus this automata accepts L1\cup L2.
Can I really make changes to the alphabet this way?
Or is the idea flawed at other places?
gritty crescent
I think this only addresses the case where they have different alphabet, but the theorem doesn't require that.
sacred spindle
You’re pretty close. It might help to think in terms of NFAs for constructing $L_1 \cup L_2$
vital dewBOT
noah
gritty crescent
Oh, I haven't covered NFA's and DFA's yet. The proof in the book seems slick, it considered the Cartesian product of states of both automaton and then did a nice construction.
ornate cliff
Could you have a set in this relation where x = y? Like R= {(1, 1), (2, 2) …}
I think so since you would get the value 0 which is an even number
(1, 1)
1^2 - 1^2 = 0
gritty crescent
Yes, all pairs of the form (n,n) would belong to this set for the reason you stated, but these are not the only ones.
ornate cliff
Thank you!
obtuse lance
Oh, I haven't covered NFA's and DFA's yet. The proof in the book seems slick, it...
just as a nice thing, it turns out NFA are actually equivalent to DFA, which helps me in reasoning out what all kinds of operations you can do. In particular if you ever use regex, like with grep, that's constructing NFA to to find text in files
gritty crescent
I don't know much about regex/grep 😅 But good to know. And the book did end up introducing NFA before writing a proof for closure of languages under concatenation. (I'm still a bit confused about how NFA handles empty string)
obtuse lance
hah, don't worry about them for now, just saying what you're learning has real world uses for you to look forward to possibly 😛
depending on the notation you use, NFA should accept an empty string if your starting/initial state is also an accepting state
gritty crescent
Oh, the bit I'm confused about is how the parsing tree for a string splits when a state with outgoing empty string arrow is encountered
Let me grab the example from the book
Like the splitting from q1->q3 didn't make immediate sense to me
Although I understand it would terminate afterwards since q3 has no outgoing arrow with 0
Is it like an option to either stick to the state with an outgoing empty string arrow, or to "jump" over it?
obtuse lance
weird, that doesn't seem right
gritty crescent
I'll try looking in a different book
obtuse lance
what does the different thickness arrow represent
seems strange, not familiar with empty string being used this way
looks like they're trying to immediately follow up going to q_2 with an empty string since it requires no steps
just seems foolish when you could just write an arrow directly from q1 to q3 instead of q1 to q2 and then an empty string step from q2 to q3
I see what they're doing, but I don't like it lol
gritty crescent
This seems to be a generalisation
The formal definition is in this article along with an example
gritty crescent
what does the different thickness arrow represent
Not sure either
obtuse lance
the way I learned was to simply draw two arrows with a 1 on them from q1 to both q2 and q3, this way of doing it just seems less clear
I understand what they're doing
when you do an epsilon move you're basically doing an optional free move that doesn't add any letter to your string
you could think of epsilon as like a placeholder for an empty string, like maybe to be a bit clearer,
gritty crescent
Not sure either
Oh, it seems they are using dark arrows for paths that end in an accepting state
gritty crescent
when you do an epsilon move you're basically doing an optional free move that do...
I see
obtuse lance
q1 -> q1 -> q2 would look like '0' + '1' while q1 -> q1 -> q2 -> q3 would look like '0' + '1' + ''
gritty crescent
Aah
obtuse lance
if that makes some sense, each character for each ->
gritty crescent
That makes sense
obtuse lance
cool
gritty crescent
Thanks for the help!
obtuse lance
yeah you're welcome
coarse cave
<@&286206848099549185>
obtuse lance
here's a cute interactive thing I used to learn some basic regex long time ago, it's pretty short and might be fun/useful to you to get a bit of "real world" practice https://regexone.com/
gritty crescent
Thankyou, will check it out. 
sacred spindle
This question is basically asking if you can come up with two infinite subsets of integers such that they have no elements in common and their union is all integers
meager cradle
is anyone good with permutation and combination?
say there is 5 books and you want to stack them on a stand. would you use the premutation formula or combination?
haughty garden
if the order matters, use permutations.
if the order doesn't matter, use combinations
meager cradle
@haughty garden yeah i get that but for this problem I’m not sure if the order matter or not
“How many ways could 5 books be stacked on a stand”
I was thinking it’s 5! But at the same time, I’m not sure bc it never really mention any orders
meager prairie
its 5!
meager cradle
O, is it because stacking stuff requires rearrangement?
meager prairie
idk id just figure
you have 5 choices for first book
4 choices for second
etc
i hate the permutation/combination thing like "order matters" because its not always clear
but im also in this class probably 
meager cradle
Ikr English not my first language and it often catches me off guard with these wordings
meager prairie
your first thought should always be direct enumeration i think
which works just fine here
"order matters" is really deceptive
especially in these like
"number of ways" questions
"number of ways to get 4 of a kind"
its not really clear if order matters or not
but its really an enumeration question either way
meager cradle
Yeah, normally they have like distinct words like like “5 different books” but this one has none which kinda threw me off track
Ty bud
meager prairie
factorial is your friend where youre not sure if order matters or not
generally youll want to reduce it to a case where youre completely agnostic of any ordering
then multiply by some factorial
that gives you all of the ordered cases directly
meager cradle
Ahh I see, thanks a lot man, I can sleep in peace now lol, been thinking about this question all night
meager prairie
here itd just be like
5 books, 5 spots, one way to fit 5 books in 5 slots if you dont care about order
then 5! is your factor
not super interesting example
np 😄
restive kettle
a(n) ?
stray reef
are you sure you didn't fuck up anywhere after substituting $a_n = An \cdot 3^{n}$?
vital dewBOT
Ann
stray reef
,w simplify A * n * 3^n - 3 * A * (n-1) * 3^(n-1)
stray reef
why do you have A3^(n-1)*(n-1) on the right hand side?
and not 3^(n-1), the actual RHS?
sand cipher
how do i prove this
do i first change it into
a=bq1+r == b=aq2+r
where q1 & q1 in some integer
vital dewBOT
james_ash_
sand cipher
**james\_ash\_**
sorry but still don't get it
torn tendon
by the trichotomy of integers we know that exactly one the following hold
a=b , a<b , a>b
since we assumed $a\neq b$ that leaves 2 options each leading to a contradiction
vital dewBOT
james_ash_
torn tendon
why? how does mod work ?
sand cipher
mod finds the remaider of a dividend and divison?
torn tendon
so whats b mod a for a>b ? and does the equality still holds that amodb=bmoda ?
torn tendon
it would be b
sand cipher
o wait my bad bad yep cuz if a>b then it can be integer but if b>a then it'll be rational
the equality would not holds that amodb=bmoda
since
ex:
3/9 is not equal to 9/3
torn tendon
amodb for a>b will be less than b certainly correct
likewise for the case of b>a and you have one option left which is the required a=b
sand cipher
well if a=b then amodb=bmoda
torn tendon
did you understand how we proved it?
sand cipher
by showing that if bmoda for a>b it would be b and if bmoda for b>a it would be a
therefore a>b=b>a == a=b?
tame isle
Please help someone
torn tendon
by showing that if bmoda for a>b it would be b and if bmoda for b>a it would be ...
you just need to prove that a>b and b>a lead to contradictions which we did
sand cipher
since a>b and b>a contradicts each other then a=b?
torn tendon
they dont contradict each other
each case leads to a contradiction for the statement itself
a>b leads you to amodb=b which is a contradiction
b>a leads you to bmoda=a which is a contradiction
sand cipher
ow so since they are each a contradiction which was just proven above then this prove that a=b
torn tendon
yep since by trichotomy of integers only 1 can be true
a>b a=b or a<b
sand cipher
wait so this question is same thing as saying prove that a trichotomy of an integers can only have 1 that is true
torn tendon
no it is not thats a property you can use
sand cipher
i see "For any two real numbers a and b, exactly one of the following is true: a < b, a = b, a > b."
torn tendon
yep
sand cipher
ok thanks @torn tendon
iron marsh
by the trichotomy of integers we know that exactly one the following hold
a=b ,...
Out of curiosity, is there a space in which a number is two of these?
Like a number/value is both bigger and smaller than some other number/value?
pale epoch
if both numbers are the same 😛
orders are antisymmetric, so using words like "bigger" or "smaller" would be very counterintuitive
iron marsh
Dang. So there really isn't some freaky space where it is possible for a<b and b<a? Bummer
pale epoch
it would be weird to use < for something that is not an order
austere swan
To add to this, you do have preorders which are usually denoted with $leq$ where you can have $a \leq b \land b \leq a$ but not $a=b$. Tho even in this context, if you use < you are referring to a strict preorder, wherein by definition you cannot have both a<b and b<a
vital dewBOT
ShiN
iron marsh
Ooo. What would be an example of such a preorder?
fallen vigil
can someone explain how the first equation (on the right side of it) is applied to the second one?
i've been trying to understand this for a good few hours
rancid osprey
does this question even make sense? lol. i don’t think this is how the greedy algorithm works
ornate cliff
Do my answers to 1a & 1c look correct?
ember obsidian
Do my answers to 1a & 1c look correct?
yes
minor pumice
hi
sharp ledge
Can i know given a natural number n , i knew that n is not divisible by 2 consecutive numbers between 1 and 25 inclusive , how do i find the 2 numbers ?
gritty crescent
Does such an n even exist? 🤔
The only two consecutive primes here are 2 and 3, and you can't rule out divisibility by 2 since it hits divisibility by all even numbers
Picking any consecutive pair with a composite value won't work because divisibility by its prime factors is already guaranteed
(at least if I understood your problem correctly, I'm assuming you have an n such that it is not divisible by exactly two consecutive numbers between 1 and 25, and divisible by all others)
sharp ledge
Yup, that is the questions
gritty crescent
If possible, can you provide the exact question with the original phrasing?
I feel I might not be interpreting it correctly
quaint star
Any prime number larger than 25 satisfies this unless I am misinterpreting
gritty crescent
I am additionally assuming that it is divisible by all but those 2 values
Otherwise yes, that's it
quaint star
sharp ledge
Yup, divisible by all numbers between 1-25 except the two , which have difference of 1 with each other
gritty crescent
Like the "2 consecutive values" hypothesis seems to impose more tedious solution than "pick 29 lol"
sharp ledge
The natural num n dont have to be in the 1-25 range though
gritty crescent
It won't be
quaint star
Okay, then no such n exists.
gritty crescent
Yeah
quaint star
Nvm, nonsense proof
cerulean wind
do u mean “n cannot be divisible by all factors of x and x + 1”
cerulean wind
wait why
quaint star
Last attempt
sharp ledge
LET N = 24, though n not divisible by 48, but n divisible by 6 which is a factor of 48 ?
quaint star
Yes,I wrote garbage
sharp ledge
So is there still no 2 numbers that satisfies this ?
quaint star
Let n be divisible by all numbers from 1 to 25 except x and x+1. If x or x+1 is > 1 and composite then it can be written as a product of two smaller integers but n is divisible by those so then n would be divisble by x or x+1. So either x is 1, or x and x+1 are prime (which can only be 2 and 3). But then n is divisble by 4 but not 2: absurd.
I hope that's right lmao
quaint star
So is there still no 2 numbers that satisfies this ?
This is definitely impossible. My proof was just bad lol
weary tiger
all i need to know is that will at least two of them have the same mod 7?
Prove that from any 100 integers one can pick 15 such that the difference between any two of them is divisible by 7.
brittle lily
If difference between any two is divisible by 7, then all those 15 numbers will have the same value mod 7
weary tiger
that's not true
only two of those 15 numbers need to have the same value mod 7
@brittle lily
but how do i prove that there will be two of those numbers
brittle lily
only two of those 15 numbers need to have the same value mod 7
I'm not sure if that's true
They say difference between "any two" out of the 15 right?
weary tiger
right
and if we have two number mod 7 that is 4, when we subtract them, we get 0, which is divisible by 7
@brittle lily
brittle lily
but how do i prove that there will be two of those numbers
Sure if this is what we want to do
Then
weary tiger
we have to prove with pigeonhole
brittle lily
Since we have the choice of picking which 15 we want
weary tiger
i mean
we know tat with pigeonhole, there will be at least one group that has 7 of the same numbers (mod 7)
which then will just garuntee
brittle lily
I'm saying that if you have typed the question correctly, then you are reading the question wrong
We can actually show that, we can find a subset of 15 integers out of the 100
weary tiger
ok
brittle lily
such that difference between any two of those 15 is divisible by 7
brittle lily
how do you prove that
Oh, should I tell the complete proof?
brittle lily
We have 100 pigeons and 7 holes
weary tiger
yes
they will have the same mod 7
so you could just subtract any two of them and get a multiple of 7
brittle lily
Yep
brittle lily
so is that theproof
Yep
violet bobcat
May I know how do I solve this question
weary tiger
We have 100 pigeons, and 7 pigeonholes. Let’s say that we can pick two numbers whose difference is divisible by 7. Based on the pigeonhole principle, there will be one pigeonhole that contains 15 pigeons, which in this case, are the numbers mod 7.
Out of these 15 numbers, we can take any two of these and subtract them, producing a multiple of 7. Therefore, it is possible.
@brittle lily ?
zealous forge
how would you find the domain and range of a function?
gritty crescent
May I know how do I solve this question
You have a recurrence relation that tells you how y_n depends on y_(n-1). For n=2, you'll need to know y_1. For y_1, you need to know y_0 which is already given to you. Put the pieces together.
gritty crescent
how would you find the domain and range of a function?
Domain of a function is generally specified, it's not something you can determine. Although, often you'd be able to find the largest set of values where the "expression" for the function is well-defined.
Range can sometimes be determined, but you need to be more explicit about the kind of function you have.
zealous forge
graph
gritty crescent
Then your domain corresponds to all the x values for which there is a corresponding y coordinate on the graph, and your range is the set of all y values that appear on your graph
brittle lily
<@!609088607143329833> ?
Yep
weary tiger
thanks
violet bobcat
Then your domain corresponds to all the x values for which there is a correspond...
okyy thanks so much
rancid osprey
hi can someone help me with this pls
(a) is this even a question? on its own i feel like it doesn't even make any sense
(b) I understand that this is the 0/1 knapsack problem, but is the greedy algorithm based off of "highest value" or "highest value to weight ratio"? sometimes it's one and sometimes it's the other so i feel like this is ambiguous
(c) does this mean that there are two separate knapsacks, and we perform the greedy algorithm once on each?
finally, how are you supposed to verify an optimal solution? using dynamic programming here wouldn't be feasible by hand...
sharp ledge
What info does the xy binary gives ?
I knew that the x+ y tells us that one of x or y is odd and other is even
so after all these, i got possible x and y pairs = {20,15}, {22,15}, {21, 15}
Is it the only way to check which one is the answer is to convert all of these 3 pairs into binary and check which have 1 on the 2^2 position ?
slate burrow
n=2
LHS: 2(2)-1=3
RHS: 2^2=4
how does this work? they say it holds for k+1 as well which it clearly doesn't xd
proven silo
its a sum that goes from 1 to 2n-1 with increments of 2. So 1+3+5+...+2n-1
so for n=2 its 1+2*2-1=1+3=4
slate burrow
that don't look right 
rancid osprey
?
slate burrow
my brain is lagging
proven silo
that is legit what the notation means my friend
coral raven
(2(1) - 1) + (2(2) - 1) = 4
slate burrow
aha
i see
i'm sorry
thanks it makes sense, i'm so bad at sums
oh shit it works
vital dewBOT
Steppaz
slate burrow
$p(k):1^2+2^2+3^2+...+(k+1)^2=\frac{(k+1)(k+2)(2k+3)}{6}$
vital dewBOT
Steppaz
slate burrow
I was wondering can i assume that this part : $(1^2+2^2+3^2)$ on the show part is equal to $\frac{k(k+1)(2k+1)}{6}$ and then solve it?
vital dewBOT
Steppaz
slate burrow
makes sense?
ornate cliff
I’m deciding whether permutation, combination, or selection should be used to answer this problem. I’m thinking selection since order does not matter and repetition is allowed?
pale epoch
**Steppaz**
this should be p(k+1)
anyways, you are supposed to assume p(k) and prove p(k+1)
slate burrow
right sorry
yeah, i'm aware of that, however i was wondering if i could do that step as i showed
i can show in paint
pale epoch
i dont really see what you are assuming
slate burrow
well i'm just saying that "1^2+2^2+3^2" is equal to "k(k+1)(2k+1)/6" so i can show that pk => p(k+1)
but wait
pale epoch
but that is not true
slate burrow
i cant do that
pale epoch
1^2 + 2^2 + 3^2 is 14
slate burrow
because of k^2 right?
pale epoch
no, because 1^2 + 2^2 + 3^2 = 14
slate burrow
Right, ok i can't do that then
pale epoch
i mean you are supposed to (and can) assume that p(k) is true
which says that $1^2 + 2^2 + 3^2 + \dots + k^2 = \frac{k(k+1)(2k+1)}{6}$
slate burrow
right i'm with on you on that
vital dewBOT
Lochverstärker
pale epoch
so just do that for your sum with the extra term (k+1)^2
slate burrow
Alright, let me see where it takes me. Thanks
slate burrow
That's my secret, i'm always overthinking it :D
snow sleet
I’m deciding whether permutation, combination, or selection should be used to an...
yes, this is unordered selection with replacement
elder atlas
would the elements of R basically be {(1,2),(2,3),(3,4),(4,5)}?
and would the domain be {1, 2, 3, 4}
and range be {2, 3, 4, 5}?
onyx zephyr
The last sentence simply means x1>=1, x2>=2..., x6>=6, right?
stray reef
yes
desert edge
How do I show the process for this computation?
(9987421*(32413+43256))mod57
Task is to Compute the following value, showing the process for each computation:
stray reef
@desert edge well how would you go about doing it?
can you at least describe in words what you have in mind?
...wait, it's been several hours. do you still need help with this?
desert edge
@stray reef hey.
sorry was busy doing other exercises but I skipped it for now
split drum
I have to prove that if x is irrational then x^(1/3) is irrational by contradiction. So far I just assumed that x is irrational and x^(1/3) is rational.
If I cube both sides I get x = p^3/q^3. Is this where I can stop? I think this shows that x is rational, which is a contradiction because I assumed it was irrational.
coral raven
yes
split drum
Noice, thanks
unborn pivot
Hi I was wondering if anyone can help explain the difference if there is between the following:
the first is basically ~a~b~c~d and the other is ~(abcd) unless I'm mistaken
It’s from this truth table so I’m wondering which of the following would be accepted for the first line
serene canopy
neon fulcrum
Hello
Why is the 2nd option not a correct answer?
I see why the first is correct
just not why the 2nd answer would be wrong
pale epoch
the second table does not satisfy the premise, so its not a counterexample
neon fulcrum
I still dont see it
P has one true in its column and Q has one true in its column
pale epoch
$\forall x; P(x) \lor \forall x; Q(x)$ is not satisfied
vital dewBOT
Lochverstärker
pale epoch
yw
shadow olive
Please someone help me with this question.
gritty pumice
n = 1 is trivial
true for n -1 propositions
prove for the nth case
(so just prove for n =2)
rich siren
coral raven
fermat's little theorem
split drum
I have to prove this using contradiction. Would the way to start be to assume that an m and n do exist?
cerulean wind
yes
split drum
OK, cool.
Would I end up showing m=n?
Actually, I'll just try and work it out first.
elder atlas
<@&286206848099549185> How do i go about solving these
split drum
OK, so I set $m + 2n +1 = 5m + n$ and solved for $n = 4m - 1$. Plugging this back into the original equations I got them both equal to $9m-1$. As it is not the case that $9 | 9m - 1$ so an $m$ and $n$ do not exist.
vital dewBOT
Umiguess4000
tidal tulip
could someone check my proof
knotty pulsar
Hi can someone help me with couple questions?
mystic elbow
Hi can anyone please help
So I have this
if we're adding a new square to the perimeter
it can be in 4 conditions
radiant oasis
I've never studied graphs. However, in my research I'm required for basic knowledge of graphs. Say I have a graph G and a subgraph of G which we denote by H. Can I say that H is obtained from G by deleting some edges (and keeping all vertices)? If so, why? If not so, why? and what needs to be done in order for that to be possible?
mystic elbow
it can be in 4 conditions
1: It is attached to the previous shape only on one side
2: it is attached to the previous shape on two sides
3: it is attached to the previous shapes on three sides
4: it is attached to the previous shape on every side
in essense, we are trying to show that adding a square anywhere would keep the perimeter even
idk what to do next
can anyone pls help
stray reef
you want to show that the perimeter stays even
so show that it stays even in all four cases
mystic elbow
how
stray reef
well let's consider for example the case where the new square is attached only on one side
by how much does the perimeter of the shape change?
@mystic elbow
mystic elbow
by how much does the perimeter of the shape change?
By 1?
stray reef
and how did you conclude that?
stray reef
"shift"?
what shift?
we aren't shifting anything here.
what led you to conclude that the perimeter changed by 1 unit?
mystic elbow
I dont know I’m not getting it
stray reef
do you know what the word "perimeter" even means?
mystic elbow
The total distance of the shape
mystic elbow
It’s adding all the sides I know
stray reef
the perimeter is a length, not an area.
it's the total length of the boundary of your shape
now go back to my picture
when you add the new square attached to the shape by one side,
this one side stops being part of the perimeter
and the other three sides are now added to the perimeter
@mystic elbow do you understand this Y/N
mystic elbow
Yes
stray reef
so what's the net change in the perimeter?
mystic elbow
I’m not sure +3?
stray reef
no
wrong
we gain three new units, but we also lose one unit.
do i need to repeat this before you understand it?
do you claim that when you lose 1 dollar and gain 3 dollars, you end up with 3 dollars more than you start with?
mystic elbow
we **gain** three new units, but we also **lose** one unit.
Got it
But how do we say in terms of this question
stray reef
this one side stops being part of the perimeter
and the other three sides are now added to the perimeter
you lose 1 you gain 3 your total change is?
tidal tulip
“which means m^2 - 1 is the product of two positive integers that are neither equal to 1 or m^2 -1”
could someone check my proof ^
quaint star
@tidal tulip looks good
tidal tulip
thanks!
quaint star
Except product of two positive integers at the end
tidal tulip
what should i fix? or say to fix it
quaint star
Say m^2-1 is the product of two positive integers
Rather than just integers
Otherwise 5 is a product of -1 and -5, but it's not prime. So you need to restrict to positive integers
quaint star
👍
tidal tulip
so just add the word “positive integers” to the sentence
which means m^2 - 1 is the product of two positive integers that are neither equal to 1 or m^2 -1
stray reef
it seems i got ghosted again because someone couldn't add 3 and -1 together 
tidal tulip
crap i accidentally deleted my proof
i’ll re paste with your correction. my phone was being wonky
quaint star
it seems i got ghosted again because someone couldn't add 3 and -1 together <:th...
lmao
tidal tulip
We want to prove that for all integers m >= 3, m^2 -1 is not prime
Proof:
m^2 - 1 = (m-1)(m+1)
Since m >= 3,
1 < 2 <= m - 1
1 < 4 <= m + 1
and
If we multiply (m+1) on both sides of 1 <= m-1 we obtain,
(m+1) <= (m-1)(m+1) = m^2 - 1
If we multiply (m-1) on both sides of 1 <= m+1 we obtain,
(m-1) <= (m+1)(m-1) = m^2 - 1
Thus we have
1 < m - 1 <= m^2 -1
1 < m + 1 <= m^2 -1
which means m^2 - 1 is the product of two positive integers that are neither equal to 1 or m^2 -1
Thus m^2 -1 is not prime for all m >= 3
boom correction added, thanks again!
@quaint star i saw someone say for this problem:
“ for positive x,y then x > y is the same as x / y > 1
then
(m^2-1)/(m+1) = m - 1 >= 2 > 1”
but didn’t understand that solution, could you explain what they’re doing?
quaint star
It's confusing. But they are saying m^2-1 and m+1 are positive, and the quotient is > 1 so then m^2-1 > m+1
tidal tulip
ah, i see. ty
mystic elbow
you lose 1 you gain 3 your total change is?
2
mystic elbow
it seems i got ghosted again because someone couldn't add 3 and -1 together <:th...
😞 I’m hereee my internet went in my area
stray reef
okay great
so in the case that your square is attached to the shape by one side, the perimeter goes up by 2
now are you able to write out the changes in perimeter for the other cases?
i.e. when the number of attached sides is two, three or four
mystic elbow
so in the case that your square is attached to the shape by one side, the perime...
Oh so we have to show it in the same way with case 2,3,4 and done?
stray reef
do what i ask you to do.
mystic elbow
That’s what u said dude
stray reef
idk what you mean by "show it in the same way"
you haven't yet given me an answer
"if there are two attached sides the change in perimeter is ___, if there are three attached sides the change is ___, if there are four attached sides the change is ___"
fill in the blanks
mystic elbow
4,6,8?
stray reef
incorrect. wildly so.
let's consider the case of two attached sides
how many sides are lost from the perimeter, and how many are gained?
@mystic elbow is your internet malfunctioning again?
stray reef
how about you tell me why you think it's right?
mystic elbow
When we attach by 1 side it goes by 2
So by attaching 2 sides it goes by 4 coz (6-2)?
stray reef
why 6-2?
attaching a square by two sides is not the same as attaching two squares by one side each.
mystic elbow
Lose 2 gain 6
mystic elbow
A square has 4
stray reef
yes, see? you don't even have 6 sides to gain from anywhere!
how can you gain 6 sides when attaching one square?
stray reef
no you don't gain 3 sides
a square has four sides. two of them are lost because you attached by them. the other two sides are the ones gained.
unless you would have us all believe 2+3=4?
mystic elbow
Ohhh
stray reef
so what's the change in perimeter when the square is attached by two sides?
mystic elbow
4+4=8 -2 coz we lose 2 sides so 6
mystic elbow
do you agree that you lose two sides and gain two sides???
Yeah
stray reef
so???
mystic elbow
0
stray reef
what was that business with 4+4???
yes that's correct the change is 0 in this case
now let's try the case where we attach one square by three sides.
stray reef
no we aren't even close to the final answer yet
mystic elbow
I thought so but I thought the values couldn’t be in negative
stray reef
you thought we could never get a shorter perimeter by adding a new square?
mystic elbow
Yeah 😅
stray reef
imagine 5 squares glued together to form a C shape
if you insert a square into the cavity of the C, the perimeter will go from 12 to 10
mystic elbow
Ahhhh
stray reef
and if we attach by 4 sides
what we're really doing is filling a 1-square hole inside the shape
we lose 4 sides and gain nothing
so the possible changes in perimeter from adding one square are:
+2
0
-2
-4
mystic elbow
Yup I figured the pattern
stray reef
it's best not to hunt for "patterns" but rather to understand where each of these numbers came from
in any case, you may notice that all of the numbers here are even
tidal tulip
<@!738650399359238195> i saw someone say for this problem:
“ for positive x,y t...
@quaint star i thought i understood this alternative solution but i don’t.
could you elaborate on it? the last bit i was trying to prove was that both (m-1) and (m+1) is strictly less than m^2 -1
is that what’s they’re showing too? if so can you explain a little more how didn’t see it
mystic elbow
in any case, you may notice that all of the numbers here are *even*
Ahhh ok ok
stray reef
this is what i was trying to build up to
mystic elbow
I see
stray reef
the perimeter of a single square is of course just 4
4 plus a bunch of even numbers is even
quaint star
<@!738650399359238195> i thought i understood this alternative solution but i do...
A positive integer is not prime iff it has a divisor strictly between 1 and itself. So you don't actually have to prove both m-1 and m+1 are such divisors. Having that one is, is enough.
weary tiger
Just a general graph theory question: if in a directed graph, every node has even degree then does it hold that the in degree is equal to the out degree?
stray reef
@mystic elbow wasn't that your goal? to prove the perimeter is always even?
@weary tiger no
quaint star
No. Consider vertices A,B,C and edges AB, CB, AC. Then every vertex has degree 2, but degree in of A is 0 and degree out 2.
weary tiger
Yeah right
I was trying to get an equivalent argument for "an euler path uses an even number of edges at every node"
but in a directed graph setting
mystic elbow
<@750639066420215858> wasn't that your goal? to prove the perimeter is always ev...
Ah just wanted to confirm if that’s all or not anyways thank you so much I got it y
tidal tulip
@quaint star
how do they know (m^2 -1) > (m+1) such that they can justify (m^2 -1) / (m+1) > 1?
and hence the fact that m^2 - 1 has divisors strictly between 1 and itself
tidal tulip
ok i see
@quaint star
so putting it all together is this understanding correct:
a positive integer is not prime iff it has a divisor strictly between 1 and itself
we know m^2 -1 > m+1 because
(m^2 - 1)/m+1 = m - 1 >= 2 > 1
hence we see m^2 - 1 has a divisor strictly between 1 and itself and thus isn’t prime
quaint star
Yeah
tidal tulip
ty
open glacier
stray reef
no to both
A is nowhere near being the entire real number line
consider that the letter Z refers to the set of integers not the set of real numbers
also 2 is a member of A but not of B
tidal tulip
We want to prove that for all integers m >= 3, m^2 -1 is not prime
Proof:
m^2 ...
@quaint star lastly, lol i confused myself with my own proof a little.
why does showing what i did
1 < m-1 <= m^2 - 1
1 < m+1 <= m^2 -1
work?
should i instead have shown
1 < m-1 < m^2 - 1
1 < m+1 < m^2 -1
quaint star
Yeah
But, your proof works
You could have just said < where you said <=
1 < m+1 multiply through by m-1, so m-1 < m^2 -1
Same for other one
weary tiger
If we have an Eulerian path E from node a to node b, how can I prove "informally" that E exits a one more time than it enters it and E exists b one fewer time than it enters it?
The idea I have is: E starts at node a. At every subsequent visit, it'll use an even number of distinct edges at a where it leaves a as many times as it enters it. Combined with the first edge that goes out of a, we get outdeg(a) = indeg(a) + 1
coral raven
yes
split drum
Like, find a number n such that 4n is even and n^2 +1 is odd?
quaint star
Yes, hint: ||4n is always even||
quaint star
👍
split drum
Thank you guys!
tidal tulip
Could I get a proof check?
Prove the for all n in Z, 6n^2 + 27 is not prime
Proof:
6n^2 + 27 = 3(n^2 + 9), where n^2 + 9 in Z
A square of any integer is positive, thus n^2 + 9 is positive, so 6n^2 + 27 is the product of two positive numbers that aren’t both equal to 1 or 6n^2 + 27, hence 6n^2 + 27 is not prime
pale epoch
works but 6n^2 + 27 = 3(2n^2 + 9)
plucky slate
MMmmmmmm Graph theory
Right. So.
Isomorphic graphs only rely on 4 things:
1 - Number of verticies
2 - Number of edges
3 - Degree Sequence
4 - Connected or disconnected
Here...I'm struggling to fine 2 simple graphs that are not isomorphic. because in this example/question they have the same number of verticies, same number of edges and the same degree sequence. That only leaves disconnected.
A disconnected graph would most likely have loops or multiple edges between verticies so...Any of you guys got any idea on how this would work?
(Also sorry if I just butted in)
tidal tulip
thanks @pale epoch , didn't even realize my typo there
pale epoch
your assumption is wrong, those things together do not characterize isomorphic graphs
plucky slate
Then...what does characterize isomorphic graphs?
pale epoch
that's an open problem
plucky slate
Oh
pale epoch
in general you can't do much better than brute force
which takes exponential time
anyways in this case just draw a few graphs with this degree sequence
i just drew two and they are non-isomorphic
without even trying
plucky slate
No loops, no double edges
pale epoch
ye, they are simple
plucky slate
Each vertex is connected by at most 1 edge
How the hell
Could you show the graphs please?
pale epoch
did you try drawing some yourself?
plucky slate
Yes
pale epoch
do you have any more isomorphism invariants than those listed
plucky slate
"Isomorphism invariants"
I...don't actually know what that means
This is basically the limit of my knowledge on isomorphic graphs
pale epoch
its some kind of property that is the same for isomorphic graphs
number of vertices, edges, degree sequence, connectivity are all isomorphism invariants
you can use them to detect non-isomorphic graphs mostly
plucky slate
Alrighty
I don't know any other invariants other than those 4
pale epoch
well ok
a graph with this degree sequence will have 5 vertices
i draw them like this
plucky slate
Yep, so that's common between graphs
pale epoch
now one of those vertices will have degree 3
i choose the top left one but it doesnt really matter which, this is highly 'symmetric'
also it doesnt matter which vertices i connect it to
an isomorphism could relabel the names of verticies and change it
i get this
the top left vertex is done, because no vertex has degree greater than 3
the bottom right vertex still needs 2 edges but cannot be connected to the top left
so there are 3 choices left, but a graph isomorphism could exchange the 3 vertices so it doesnt matter which two i choose
i choose this
plucky slate
Now the degree sequence is (3,2,2,2,1)
pale epoch
ok so now the middle one lacks an edge
and i can connect it to any of the non checkmarked vertices
there are 3 choices left
two of those will be isomorphic, one will be different
this is my thought process for crafting this, but if you dont know more about isomorphism invariants its probably not obvious which one is the different one
plucky slate
It's gonna be a hamiltonian cycle, isn't it?
If so...Hecc
pale epoch
actually that works
plucky slate
I'm yet to touch on hamiltonian cycles
So that's why I'm a bit worried if that's what you're gonna show
pale epoch
looking at cycles is the correct way
stray reef
this is my thought process for crafting this, but if you dont know more about is...
why not? two of the vertices (aside from the center and its one neighbor) can be told apart from the third but not each other
pale epoch
not necessarily hamiltonian
stray reef
the only nontrivial automorphism of your last graph is a reflection, no?
pale epoch
MMmmmmmm Graph theory
Right. So.
Isomorphic graphs only rely on 4 things:
1 - N...
my point is that you cant tell them apart by the things listed in the original post ^
i would use the fact that one of them has ||a cycle of length 3 and the other does not||
sand cipher
Quick question, for discrete maths, how do you know what to proof the question with, like by contradiction or not
stray reef
over time you gain experience in what works and what doesn't and your brain learns to spot certain patterns
however none of said patterns are set in stone or can be codified for direct transmission from teacher to student
stray reef
my point is that you cant tell them apart by the things listed in the original p...
right, yes, good point
pale epoch
so i think you will have to argue about graph isomorphisms preserving the degree of neighbours (additional hint: ||consider the non checkmarked vertex of degree 3||) @plucky slate
stray reef
is there actually a universal graph invariant
or set of invariants
bc i feel there isn't
pale epoch
there is no "two graphs are isomorphic iff"
at least we havent found any for general graphs
stray reef
yeah, thought so
pale epoch
special cases have better ways
stray reef
so trying to come up with a list is kind of fruitless, isn't it?
plucky slate
Could I show 2 of my graphs and get your opinions on them?
pale epoch
and there is a good probabilistic algorithm using graph colorings
stray reef
go ahead @plucky slate
pale epoch
ye, invariants are only good to tell non-isomorphic graphs apart
the only way to prove isomorphic is to give an explicit isomorphism
plucky slate
These are isomorphic in my eyes. Correct me if I'm wrong
Same degree sequence, same number of vertices, same number of edges and both are connected
stray reef
nope these are not iso
left one has two adjacent deg 2 vertices, right one doesn't
just because they match on all four of your criteria does not by itself mean they are isomorphic
stray reef
to prove two graphs are isomorphic you pretty much need to construct an isomorphism explicitly, ie match up the vertices of your two graphs in a way that exactly matches up all the edges too
stray reef
i'm not coming from anywhere
plucky slate
In the first the 2 vertices with 3 edges are connected while in the second, they are not.
That shows they are not isomorphic
stray reef
okay yeah
that's slightly different than what i said, but it tells the graphs apart just as well
stray reef
i was actually talking about the two vertices at the bottom in the left graph
pale epoch
(a side note: this whole graph isomorphism thing is super interesting, for a long time people used to think that some linear algebra thing via the adjacency matrix could be used to characterize isomorphic graphs and that just nobody managed to prove it yet, but with brute forcing on early computers those hopes were shattered)
plucky slate
This is why maths is so interesting
velvet geyser
school is annoying they will change everything to weird looking 1+1=2 the school changes that to 1+x=2 i still dont get the point of adding x
and other stuff
wheat leaf
Can anyone help on where to go from here
wild merlin
going from the third line to the fourth line you did demorgan's law wrong
not (p and q) is not p or not q
does anyone know how to do (8)?
<@&286206848099549185>
coarse cave
anyone know how to prove that the hockey-stick theorem and the backwards hockey stick theorem the same thing with symmetry involved (without factorials)
elder berry
Well \binom{2n}{n} is basically the sum of (\binom{n}{i})^2 for i=0, 1, ..., n.
So maybe try arguing that for each set containing i even (odd) numbers there is a total of (\binom{n}{i})^2. The proof of the sum of \binom{n}{i}^2 = \binom{2n}{n} should be straight-forward (it is well-known)
elder berry
anyone know how to prove that the hockey-stick theorem and the backwards hockey ...
Induction
Though I do not know what the backwards hockey stick identity is
(and by without factorials do you mean counting arguments?)
wild merlin
consider stars and bars
coarse cave
working with combination notation and/or summation notation
elder berry
Yeah the hockey stick identity can be shown with a counting argument using stars and bars as tadders said. You try and find two different way to count the same thing (idea) which is the identity. Pretty tricky however have a think about it
compact gorge
Sorry if this is a dumb questions but do you think learning discrete math will help with solving data structure and algorithm programming problems?
tidal tulip
@compact gorge topics in recursion, induction, graphs, trees, combinatorics, probability theory etc. can be helpful with understanding certain data structures / algorithms
wild merlin
Well `\binom{2n}{n}` is basically the sum of `(\binom{n}{i})^2` for `i=0, 1, ......
thank you so much, this is exactly what i needed
tidal tulip
instead of using the axioms the book required in this proof, couldn't you just prove this using the sum, difference, product closure properties for integers to prove this result?
pale epoch
how so?
tidal tulip
nvm i see because division gets you
wait
def of rational is p,q where p,q in Z and q != 0
so a^2 + b^2 + 1 is an int due to closure props
2 is obvs an int
wait
i got super confused
pale epoch
well, everything you said is correct
tidal tulip
i see why now
pale epoch
but you need the thing divided by 2 to be an integer
pale epoch
i.e. a^2+b^2+1 needs to be even
tidal tulip
ok i see now ty
pale epoch
because you want to talk about inverses?
if two numbers are the same mod n, then their inverses (mod n) are as well (if they exist)
hasty glade
Yeah, I know that is about inverses
But the question should have been: does it assume that b^-1 exists? Why?
coral raven
if a = b (mod n) and a^-1 exists, prove b^-1 exists
that's fun
well not really but
you can do it pretty easily
hasty glade
Any hint?
coral raven
hint: just do it
neon fulcrum
Hi
I need help with logic
Rachel is a student in the class.
Rachel got a detention.
____________________________________________
Rachel missed class.```This is invalid right? Because Rachel could have punched a wall and gotten detention that wat too right?
coral raven
yes
elder berry
Pretty sure you need to write the statements and logical operators. Your reasoning is correct but isn't rigorous
neon fulcrum
yeah, I can turn some parts into predicaates
and plug rachel into them
after doing universal instantiation for the first line.
but beyond that I am lost
elder berry
What have you got so far?
elder berry
It should be M(x) ^ S(x)
Every student in the class and they miss class implies that they get detention
neon fulcrum
I don't think so. What you are saying then is that every student missed class and got detention
elder berry
Hmm, true
From the last part, you are given that M(Rachel) => D(Rachel) is a tautology.
Also D(Rachel) is also true.
So we would have M(Rachel) => T is a tautology which happens regardless of whether M(Rachel) is true or not
So we can't conclude that M(Rachel) is true.
neon fulcrum
M(Rachel) => D(Rachel) is a tautology.
how is this a tautology?
is rachel misses class and does not get detention it would be false?
elder berry
Isn't it given Every student who missed class got a detention.?
elder berry
So, the way I'd finish the problem is consider when tau(M(Rachel) => T) which is enough to show that when M(Rachel) is false, the given condition is still true. However I still feel like you must incorporate the fact that they are students.
Since Every student who missed class got a detention. can be rewritten like
If (you are a student and you missed class), then you got detention
The last sentence doesn't imply it for all students, since S(x) just says that x is a student
neon fulcrum
Ok, thank you
lofty cloudBOT
queen zenith
anyone know how i can numerically plot the function f(x).
f(x) = 1/2 cos(f(x^2))
gloomy aurora
function within a function? @.@
queen zenith
yeah
stray reef
send the questions and your answers
sharp ledge
How many 6 letter string i can get from A,B,C that do not include CCC ?
cerulean wind
How many 6 letter string i can get from A,B,C that do not include CCC ?
it’s easier to count how many strings have CCC in them and then subtract that from the total number of strings
sharp ledge
So , its like 3^ 6 - 333 * 4 ?
cerulean wind
where’d u get 333 from
sharp ledge
Oops, should be 3 ^ 3
cerulean wind
i think that’s over counting still
sharp ledge
To count the string with CCC, i take CCC as item , so now i have 4 items right? Then CCC could be in one of 7 positions besides the remaining 3 items
cerulean wind
one of 4 positions
cerulean wind
so i think doing it that way is over counting and here’s is why.
let’s say i have a string CCC CAB where my CCC block is in the first position
this gets double counted when you move the block one slot to the right to get the string C CCC AB
cerulean wind
let me think a little bit more. or somebody else may be able to answer
mystic elbow
@stray reef
fresh venture
dusky island
ah this is nice