Oh I see, using more than one inductive case
#discrete-math
sour arrow
whole cobalt
so P(1) and P(2)
its just
writing down the math right
i go
P(k) = n - 1
but what is P(k) = ?
sour arrow
P is a "true or false" kind of thing. It doesn't equal any number
P(k) is true. Is P(k + 1) true?
Well yeah, if you multiply a number into the first case, you get the second
Hmm. I wonder if the question intends it this way though?
whole cobalt
P(k) = k - 1
im pretty sure thats what the question says
the proof being to calculate it for P(k + 1)
so P(4) = 3 multiplications
because 1 * 2 * 3 * 4
im just struggling with the next step then, that being P(k + 1)
is that P(k + 1) = (k-1) + (k + 1)?
or is it just k?
and how do i relate the answer to that back to the proof again? because the calculation is pretty much done
stray reef
ok so
suppose we're multiplying n numbers
and we know for all k less than n that multiplying k numbers together takes k-1 multiplications no matter how the parentheses are put
do you follow so far @whole cobalt
for the record, all i've stated so far is the (strong) inductive hypothesis
whole cobalt
i follow
stray reef
ok
so
focus on the outermost multiplication
our product is gonna look like this
$(\underbrace{................}{k \text{ terms}}) \times (\underbrace{................}{n-k \text{ terms}})$
vital dewBOT
Ann:
stray reef
by the IH, the left parenthesis is going to contain k-1 multiplications
and again by the IH, the right parenthesis is going to contain n-k-1 multiplications
so in total, you'll have (k-1) + (n-k-1) + 1 = n-1 multiplications, as desired
whole cobalt
gotta have a look at it later, groupmates went onto other projects for now
whole cobalt
Well thanks for the help both of you
I managed that one problem
Think ill have to go over the stuff again, maybe find a YouTube video...
rapid herald
can someone explain to me mathematically why the dijikstra algorithm works? Like why can we make a node permanent and how do we know the distance is actually the shortest?
in other words, how do we know we have checked all the paths available?
pale epoch
you don't have to check all the paths available
the proof that the algorithm works is simple induction
rapid herald
does it not check all the paths available
how does it just conclude the shortest path to a node without all the paths to it
also, i dont really understand the proof im a newbie highschooler
rapid herald
why?
pale epoch
because if you have a shortest path between two nodes
and there is another node on that path
the subpath is also the shortest path between this node and the original node
ehh
let me get an example
pale epoch
sure
pale epoch
ok, so the first path it finds is from A to D
rapid herald
yup
pale epoch
thats the shortest path between A and D
you could also reach D via B
and go 6+7
but that path is never considered
rapid herald
but why? how does it even know that an unconsidered path isnt shorter?
pale epoch
because if it were not larger
then the path from A to B must at the very least be less than 5
it isn't so every path going from A to B and then elsewhere must be at least 6
so those paths are not worth considering if you want to go from A to D
rapid herald
ah okay i get that case
pale epoch
this is essentially the induction proof
it works for every step
if the path you select at current step isnt the shortest
you would have made a "mistake" before
rapid herald
but like for example when i look it up it is phrased in suh a complicated way
pale epoch
what is, the proof or the algorithm?
pale epoch
hm, it's a standard induction proof
rapid herald
like this thing
pale epoch
but i guess it's the "hard" part about this algorithm
the algorithm is literally the first thing you would try given that problem
and its kinda surprising, that it works
rapid herald
wdym its suprising it works?
pale epoch
well, if you told me that dijkstras algorithm solves the shortest path problem
i wouldnt believe it at first
pale epoch
i guess you can try checking youtube for a more visual proof
its basically the same argument i had for your drawing, but phrased more general
rapid herald
yeah bcoz i tried writing it in my investigation, first of all i didnt get it fully, and the whole point is that my highschool peers are supposed to get it too, which they didnt
i really didnt understand the proof of contradiction
i gave up on induction
ur argument explained it well
thank you
idk why they try to make everything in discrete math harder than it actually is
hearty crane
the notation for your algorithms looks weirdly familiar... @rapid herald you're not using Kreher's book are you
rapid herald
@hearty crane nop jisg self studying over the internet
hearty crane
oh ok
rapid herald
@pale epoch could you, by any chance, help me understand the actual proof of induction using that same example
like the notations and stuff
worthy grotto
how many ways are there to make a path from a connected graph of n vertices?
stray reef
what
lean creek
depends on connectivity
worthy grotto
oops sorry
stray reef
ok your question is still impossible to answer w/o context
can you post the exact statement of the problem
worthy grotto
i was trying to break the question down into parts.
The question is "Find the closed form of the exponential generating function for the number of ways of creating
a path graph on n vertices. "
A path graph is a connected graph where two vertices have degree 1, and every other vertex has degree 2
worthy grotto
just a simple graph, undirected
worthy grotto
why is it n!/2?
stray reef
to account for the undirectedness
1 - 2 - 3 - 4 - 5 is the same graph as 5 - 4 - 3 - 2 - 1
worthy grotto
couldn't there be paths that use less than n vertices?
lean creek
I guess we are considering factorial exponential
stray reef
that'd make it fail to be connected.
stray reef
so since the $n!$ cancel out in every term, this is... $\frac12x^2 + \frac12x^3 + \frac12x^4 + \cdots$
vital dewBOT
Ann:
stray reef
or $\frac{x^2}{2(1-x)}$
vital dewBOT
Ann:
stray reef
and there's your EGF
lean creek
@ Ann, do you think you could help me with the last part of a Ramsey problem?
I have most of it done, but I feel really dumb bc I'm not seeing the final pigeonhole step haha
worthy grotto
Thank you so much Ann. I been stuck on this for hours, For some reason i never thought of them to be disconnected.
lean creek
I'm trying to force at least #m of the #(M choose 2) total intersections to use the same k-1 vertices
@stray reef
lean creek
no problem, same haha
worthy grotto
i think the question states that the graph must be connected.
so i don't think its necessary that the path go through all the vertices
stray reef
the vertices that don't get hit are their own connected components
worthy grotto
i am not sure what you mean
i was thinking it would be like $\frac{n!}{2((n-k)!)}$ for $ k = 1 ,2, ... , n$
vital dewBOT
boat:
stray reef
ok say you have a graph on 7 vertices
and the following connections
12, 23, 34 and 45
so that 6 and 7 are not incident to any edges
this has three connected components
{1,2,3,4,5}, {6} and {7}
so it is not connected
worthy grotto
ohh i see
i have been confusing path graphs with paths
im sorry for the confusion
:/
thank you so much ๐
granite wyvern
I guys, I recently posted this problem related to Ramsey Theorem here, however no one answered it and I still need help. Could anyone please help me?
What is r(n,3)
<@&286206848099549185> Can you guys please help me
analog sonnet
For what n?
granite wyvern
It's just r(s,t) where t is 3 and s is some general number n
analog sonnet
There's no general formula for R(n, 3) for n greater than 2
worthy grotto
Using Exponential generating functions, how would i calculate how many ways are there to choose an even amount of even number from {0,1,2,3,4,5,6,7,8,9}?
my guess is to choose have a generating function for each of 0,2,4,6,8 with $ 1 + \frac{x^2}{2!}+ \frac{x^4}{4!} + ...$
vital dewBOT
boat:
worthy grotto
so in total there are $ ( 1 + \frac{x^2}{2!}+ \frac{4}{4!})^5$
vital dewBOT
boat:
lethal sequoia
I need some help with combinatorics. Not sure if my thinking is correct.
Q5
I prove by induction.
Base case is true for m and n = 0.
Induction Hypothesis:
Sum from k=0 to n (m+k/k) = (m+n/n)
$ \sum_{k=0}^{n} \binom{m+k}{k} = \binom{m+n}{n}
lethal sequoia
Yea, sorry I was trying to figure out how to write the proper symbols
vital dewBOT
Mac:
Compile Error! Click the 
reaction for details. (You may edit your message)
robust mango
it's m+n+1, right?
lethal sequoia
We need to prove Q5
robust mango
yeh, so it's m+n+1 on the right side
lethal sequoia
I'm doing the induction hypothesis is what I wrote above correct?
And then for induction step, I split the sum so it will be
robust mango
lemme try
lethal sequoia
$\sum_{k=0}^{n+1} \binom{m+k}{k} \ = \sum_{k=0}{n} \binom{m+k}{k} + \binom{m+n+1}{n+1} \ = \binom{m+n}{n} + \binom{m+n+1}{n+1} \ = \binom{2m+2n+1}{2n+1} \ = \binom{2(m+n)+1}{2(n+1)}$
vital dewBOT
Mac:
robust mango
that's not right
lethal sequoia
Which part is not right?
robust mango
How'd you just add em up
lethal sequoia
Since we want to show that it is true for n+1, the sum goes from k=0 to n+1
Which is the same thing as splitting it into: sum from k=0 to n (m+k k) + (m+n+1 n+1)
From the induction hypothesis, we know that the sum from k=0 to n(m+k k) = (m+n n)
But not sure if I can do the next parts
lethal sequoia
So what can I do?
vital dewBOT
Sup?:
robust mango
@lethal sequoia I did it
robust mango
alright
robust mango
well you had to use the hint i gave
lethal sequoia
stuck on here
$\frac{(m+n)!}{n!(m+n-n)!} + \frac{(m+n+1)!}{n+1!(m+n+1-n)!} \ = \frac{(m+n)!}{n!m!} + \frac{(m+n+1)!}{n+1!m+1!}$
vital dewBOT
Mac:
robust mango
first ofall
you wrote the question wrong
$\sum_{k=0}^{n} \binom{m+k}{k} = \binom{m+n+1}{n}$
that's the question, so start again ๐
vital dewBOT
Sup?:
lethal sequoia
Oh, what I wrote down was what I thought the induction hypothesis was
That's what I wanted to confirm from the start
robust mango
i did tell you b4
lethal sequoia
Oh did you mean that the induction hypothesis is supposed to be:
$\sum_{k=0}^{n} \binom{m+k}{k} = \binom{m+n+1}{n}$
vital dewBOT
Mac:
robust mango
Yeah, we assume it's true for k=n
What you need to do is
$\sum_{k=0}^{n+1} \binom{m+k}{k}= \binom{m+n+1}{n} + \binom{m+n+1}{n+1}$
vital dewBOT
Sup?:
robust mango
Just work some stuff out on the RHS using the hint
and you're good to go
did you get it @lethal sequoia
lethal sequoia
I'm at this point
$\frac{(m+n+1)!}{n!(m+1)} + \frac{(m+n+1)!}{n+1!m+2!}$
vital dewBOT
Mac:
robust mango
Should be $\frac{(m+n+1)!}{n!(m+1)} + \frac{(m+n+1)!}{(n+1!)m!}$
lethal sequoia
Something doesn't seem right
vital dewBOT
Sup?:
robust mango
check your working again
lethal sequoia
Oh oops, I thought I could just subtract the n's on the 2nd fraction and leave the 1's
But I have to do n+1 - n+1 and get rid of all
robust mango
At this point
The denominators are not equal, so you cannot add both the expressions
How do we make the denominators the same, so we can add them both
$\frac{(m+n+1)!}{n!(m+1)!} + \frac{(m+n+1)!}{(n+1!)m!}$
lethal sequoia
We multiply both denominators ?
vital dewBOT
Sup?:
robust mango
sorry my bad, there was a ! sign missing on m+1
close.
check both the denominators
we have n and m+1, then n+1 then m
robust mango
you should also know that $(n+1)!=(n+1)(n!)$
vital dewBOT
Sup?:
robust mango
But that'll come later on
lethal sequoia
Does that property still hold even if it is $ n!(m+1)!$
vital dewBOT
Mac:
lethal sequoia
Waitttt
lethal sequoia
Shit I suck lol
robust mango
$\frac{a}{b}=\frac{ac}{bc}$
vital dewBOT
Sup?:
robust mango
given that c is not equal to 0, but you get the idea
you need to multiply and divide both expressions, but with what?
lethal sequoia
?
robust mango
?
lethal sequoia
I'm sorry I don't know
robust mango
alright
maybe I overcomplicated it for you. If I did, I apologize. You have $\frac{(m+n+1)!}{n!(m+1)!} + \frac{(m+n+1)!}{(n+1!)m!}$
vital dewBOT
Sup?:
robust mango
You had to $\frac{(m+n+1)!(n+1)}{(n+1)n!(m+1)!} + \frac{(m+1)(m+n+1)!}{(n+1!)(m+1)m!}$
vital dewBOT
Sup?:
robust mango
Multiply and divide left expression by n+1, right by m+1
and now the denominators become same
lethal sequoia
Ah because of that property that I havent seen yet okay
robust mango
$(n+1)!=(n+1)(n!)$
vital dewBOT
Sup?:
robust mango
$(m+1)!=(m+1)(n!)$
vital dewBOT
Sup?:
lethal sequoia
What would happen if I did this
robust mango
then both the denominators become same, and simplified
so you can add both the expressions under just one denominator
lethal sequoia
I mean this: \
$\frac{(m+n+1)!(n+1)!}{n!(m+1)!(n+1)!} + \frac{(m+n+1)!(m+1)!}{(n+1!)m!(m+1)!}$
Does that not work?
robust mango
it works yes
robust mango
wdym?
vital dewBOT
Mac:
lethal sequoia
Does this work?
robust mango
No
it will work when you open the factorial, and it's a huge mess
and you have an extra factorial on the numerator
so it's just messy and i don't know if it'll work or not
What I did was to make the denominators same, yes.. but there's also another reason
$\frac{(m+n+1)!(n+1)}{(n+1)n!(m+1)!} + \frac{(m+1)(m+n+1)!}{(n+1!)(m+1)m!}$
vital dewBOT
Sup?:
vital dewBOT
Mac:
Compile Error! Click the reaction for details. (You may edit your message)
lethal sequoia
Sorry btw for taking up so much time
opal crescent
you don't have to rederive the identity from pascal's triangle tbh
it's literally just applying that
instead of going into this messy expanding stuff
rip mate @lethal sequoia
lethal sequoia
Oh yea I know this
So from here, $\sum_{k=0}^{n+1} \binom{m+k}{k}= \binom{m+n+1}{n} + \binom{m+n+1}{n+1}$
vital dewBOT
Mac:
opal crescent
and from Pascal's identity $$\binom{m+n+1}{n}+\binom{m+n+1}{n+1} = \binom{(m+n+1)+1}{n+1} = \boxed{\binom{m+(n+1)+1}{n+1}}$$
vital dewBOT
emeric75:
opal crescent
Qed
worthy grotto
can someone help me with this question
vital dewBOT
boat:
worthy grotto
i think the answer is $e^{\frac{1}{2}(e^x - e^{-x} -2)}}$
vital dewBOT
boat:
Compile Error! Click the reaction for details. (You may edit your message)
worthy grotto
but i assumed here that there is only one way to arrange a one set into subsets of an even size
glossy pollen
i have what i asusme is a pretty easy graph problem from my discrete class, but i was unsure about my answer
The question is
Consider a social network with 100 users in which each person knows on average 10 other people. Let G be the corresponding (undirected) graph where each user corresponds to a node such that if two users know each other then there is an edge between them. What is the total number of edges in G?
and my strategy was to assume that a valid permutation of these nodes would be isolated groups of ten that all point to each other
so i counted the edges in a circle of 10 nodes all connected and then multiplied by 10
worthy grotto
i think you can use the handshaking lemma here
vital dewBOT
boat:
worthy grotto
so you have 100 vertices with an average of 10 degrees
so 100*10 = 2|E|
so |E| = 500
worthy grotto
did you learn the handshaking lemma?
glossy pollen
my method gives 45 edges, and then if theres 10 of those systems its 45(10)
no
oh wait ive only got 10 nodes in my circle, but thats degree 9
worthy grotto
basically the idea behind it is that, you start at a vertex, and you have 10 edges, then you move to a vertex that is connected to it, which also has 10 edges, but you counted the connecting edges twice. You do that for all the vertices, here all the edges have been counted twice. So you divide by 2.
so you have 100*10/ 2
glossy pollen
neat
good thing i asked
thanks for the help
seems odd that i would be given a question that has a known solution, without being given or referencing that solution
olive dragon
Hey guys, there is a question I need help with. Could someone please help?
Considering this function:
f(n) = log(log(2n))
If we replace n by 2n, we get:
f(2n) = log(log(2n))
= log(log(n)+log(2))
So if we replace n by 2n, it just takes little more time but the difference is insignificant
I don't get the part where it says "input size n is 3^n"
is it asking for replacing 3^(n) to 3^(2n)?
Then is can it be like this:
f(n) = 3^(n)
replace n by 2n
f(2n)=3^(2n) = 2*3^(2n)*(1/3)
Which in this case, if n is replaced by 2n, then it takes 8 times the time taken for input size n.
glossy pollen
that makes sense because the growth of those functions is still O(loglogn) and O(n^3)
but i think since n is in the exponent this will make the time skyrocket, im not entirely sure how to quantify it tho im in the same class at my college
olive dragon
Oh yeah that was 3^n not n^3 sorry
glossy pollen
hmm let me p[lay with it, i cant promise anything tho im mad stupid
oh wait
could you just say that the time is squared 3^2n = (3^n)^2
olive dragon
Yes that makes sense, 3^(2n) is just doubled the time compared to 3^(n)
glossy pollen
squared
2(3^n) =/= 3^2n
i guess the point is just to show how time complexity grows when n is doubled under different circumstances
in log functions the growth really doesnt make a big difference
but in exponential functions the size of n is crucial to the viability of the algorithm
olive dragon
Okay, I get it now.
Considering this function:
f(n) = 3^n
Replace n by 2n to get:
f(n) = 3^n
f(2n) =3^(2n)
= (3^(n))^2
The time taken now is squared
Thank you for your help @glossy pollen
glossy pollen
no problem we got through it together
olive dragon
Yay!
weary tiger
Can anyone help me with this question
stray reef
what is giving you trouble here?
stray reef
"to me"
weary tiger
yes to me but I am wrong
stray reef
why do you think the one you marked is onto, then?
stray reef
explain your reasoning
weary tiger
wait
its not
cause R^+
but even if it is not I dont see why any other one would be onto
stray reef
do you know the definition of an onto function
weary tiger
well I thought it was when there are two x values that map to the same y value
but i think I am wrong since I cant understand this question
stray reef
well I thought it was when there are two x values that map to the same y value
no
that's called "not being one-to-one"
weary tiger
then what is onto (surjective)?
cause I thought if something is not one - to - one isnt it onto
stray reef
no that's very wrong
weary tiger
ok
stray reef
if that were the case, then it would be logically impossible for a function to be one to one and onto at the same time
a function f: X -> Y is said to be onto when for all y in Y the equation f(x)=y has at least one solution in X
weary tiger
I have not learned about a case where a function is both so I didnt know they could be both ๐
okay I dont know what your definition means
stray reef
uh
weary tiger
is it saying that there is atleast one x that has a y value
stray reef
no
not only can a function be both one to one an onto, we have a name for that.
such functions are called bijective.
is it saying that there is atleast one x that has a y value
no
weary tiger
okay I think i get it
so for every y in Y there is x that maps to it
so every y in Y is being mapped to by x
stray reef
why did you mark the Z->Z one as onto
weary tiger
isnt that just all integers
so I thought that would mapp over
now I know it R to R only but I was wondering if someone could explain it cause I dont get it
stray reef
okay so let's name the functions f_1 through f_4 top to bottom for clarity
so that you marked f_3 an f_4 as being onto
and f_1 and f_2 as not onto
so given that you claim $f_3: \bZ \to \bZ$ is onto... find me an integer $x$ such that $f_3(x)=0$.
vital dewBOT
Ann:
stray reef
no, $-2.5 = 0$ is not true.
vital dewBOT
Ann:
stray reef
if you mean $f_4(-2.5) = 0$, then say $f_4(-2.5) = 0$.
vital dewBOT
Ann:
weary tiger
makes sense alright thanks!!
whole cobalt
what a terrible day today
more induction proofs
harder induction proofs
if someones got time to help me again that would be swell
a is undefined, so im stuck at question b
tranquil cargo
what have you tried
whole cobalt
but im probably gonna need help again once i get to next question
tranquil cargo
sure
whole cobalt
you know induction proofs but not recursion?
whole cobalt
of course just as i complain about induction proofs we stop getting tasks regarding them
now its just recursion
tranquil cargo
lmao
whole cobalt
@tranquil cargo here we go
just completed the basis step
that was the easy part
whole cobalt
yes
sour arrow
I'd try to induct on the height of the tree, since you can get a unique tree from the height
sour arrow
Does that one have height 4 or 3? Lol
whole cobalt
3
sour arrow
If the height is h, then adding another layer increases the amount of verticies by 2^(h+1)
As we'd need 16 more verticies to get another layer on that
whole cobalt
yeah thats what the problem states and it makes good enough sense
but im clueless on how to do the proof
sour arrow
Let's say h is the height, and n(h) is the number of nodes. Let's induct on h. Induction always has the below form.
P(h) is true:
n(h) โฅ 2h + 1
Now, prove that P(h + 1) is true:
n(h + 1) โฅ 2h + 3
n(h) + 2^(h+1) โฅ 2h + 3
n(h) โฅ (2h + 1) + (2 - 2^(h+1))
We're done if we can show that 2 - 2^(h+1) is not positive
whole cobalt
well, my groupmates wanted to move on so they helped me with this one
and the result was very different from what you wrote ๐
but thanks for the help
mint salmon
can someone help me understand this? it says write this as a direct product and prove it
I don't really understand the notation for a linear list, with the capital letter pi
there are four elements in each tuple, right?
does x1 appear in every tuple?
stray reef
idk why they wrote $(x_1, \cdots, x_n)$ and not $(x_1, x_2, x_3, x_4)$
vital dewBOT
Ann:
stray reef
but anyway like
x_1 is just the notation for the first component of the tuple
internal to the set notation
mint salmon
ok so for every tuple of the form (x1,x2,x3,x4) x1 will be 1 or 2 and x3 will be 3
stray reef
that's the criterion for it to be in the set
mint salmon
I won't look yet
is this the way that the linear list should be written? โดฮ แตขโโMแตข
Proving this seems odd. Isn't it already true, by the very fact that we've defined it?
vital dewBOT
Ann:
stray reef
is that what you tried to write there?
mint salmon
yeah, I just didn't know the latex command for it and was too lazy to look it up
ok now I'm starting to see why this wasn't making sense
I was confusing this with linear lists
this is the general product
static ivy
failed to prove this identity
i tried a combinatorical approach and an algebra one but couldnt reach anywher :/
vital dewBOT
Totoxic:
daring bane
how do I start to tackle this? I have been staring at this problem for hours and derived nothing in the end
stray reef
you may wish to write both p and q in cycle notation
daring bane
I have done that and I went through some cycle properties like checking if the the composition of them would give an odd or even permutation but no luck ๐ฆ
stray reef
if any cycle of q involves points from two or more different cycles in p, then q is not a power of p
daring bane
Can you please define what do you mean by points?
daring bane
cycles?
stray reef
no like
how are your permutations given
as bijective functions from {1,...,n} to itself?
daring bane
in the matrix form of two rows like
so i could conclude the cycle notation
stray reef
is the top row [1 2 3 ... n]
ok so when i say points i mean those numbers from 1 to n
the cycle (1 2 7 4) is a cycle on the points 1, 2, 4 and 7
daring bane
Ok there are only two numbers which fall out for example one contains a cycle (...)(8 9) and the other contains a one cycle (...)(8)(9) which we do not write in a cycle notation
Other than that the other cycles matches
stray reef
yeah those numbers
i call them points
less clunky imo
whatever
and uh
okay so
are there any cycles in q that involve two or more numbers from different cycles of p
yes or no
daring bane
no
stray reef
right.
daring bane
let me represent the cycles
p = (1 3 4)(2 7 6 5)(8 9)
```q = (1 3 4)(2 7 6 5)(8)(9)````
stray reef
okay so
alright
assume q is a power of p
ie p^k = q for some integer k
then clearly since (8 9)^k = (8)(9) = e, k must be even
does that make sense
daring bane
yes because the composite of these are two give an even
daring bane
yes so if q is a power of p^2
stray reef
p^2 = (1 4 3)(2 6)(5 7)
and now it can be seen more clearly that q cannot be a power of p^2, bc q has a cycle, (2 7 6 5), that involves points from different cycles of p^2, (2 6) and (5 7)
daring bane
but why do we start by assuming p^q
I can understand all the following but I don't get it how or why do we assume p^{q}
stray reef
"assuming p^q"?
stray reef
my ultimate goal was to prove q is not a power of p
daring bane
wait a sec ๐ค
Nvm I got it now
Sorry I am just too tired
Thank you so much @stray reef
wintry rock
509! - 507! would basically be 509 * 508 right?
faint narwhal
Can you do anything?
wintry rock
distribute 505!?
wintry rock
yeah lol
stray reef
you get $\frac{509!}{505!} - \frac{507!}{505!}$
vital dewBOT
Ann:
robust mango
Can someone help me please with chinese remainder theorem? studying it in discrete math atm
have a few questions
sour arrow
Go nuts
robust mango
so we're solv
I mean we've done this in class before, we managed to do it by taking a1=1, a2=11, a3=6, we have m1=7, m2=13, m3=22. then we do M = m1xm2xm3
Hold on, I'll post the pic of the main question I have.
I have a question where we have 286yi~1(mod7)
What's the story with 0~1715(mod7) beneath it? Is it because we add both of them so we have 286yi~1716(mod7). And gcd of (286,7) and (1716,7) is 1? So now we are able to divide both sides by 286?
Just wanna know if I'm right, thanks guys
sour arrow
What's a1, a2, a3?
sour arrow
No like what do they mean lol
robust mango
I'm not sure
actually, I don't know.
But what I do know is, that the remainder of these numbers, and the value x when divided by 7, 13, or 22 will be same
sour arrow
Let's walk through the process.
x = 1 (mod 7)
Is a fancy way of saying
x = 1 + 7k for some k
robust mango
by = you mean congruent right?
robust mango
yes, you're right about x=1+7k
sour arrow
1 + 7k = 11 (mod 13)
7k = 10 (mod 13)
robust mango
we can subtract or add even when there's a congruent sign?
or is there some conditions?
sour arrow
Nope, you can add/subtract onto both sides just like a regular equation
You can even multiply both sides
robust mango
and divide too?
sour arrow
kind of
You can only divide both sides if the number you're dividing is coprime to the mod you're working under
robust mango
I looked at a video, it said you can divide when gcd is 1
robust mango
Yes.
sour arrow
So,
7k = 10 (mod 13)
Implies
7k = 49 (mod 13)
Implies
k = 7 (mod 13)
And we can divide by 7 since it's coprime to 13. That's essentially the CRT in that single statement
sour arrow
- Note I divided by 7 to get the last line
robust mango
I see.
so the only thing that matters when dividing on both sides is that the number we're dividing, (7k) in this case has to be coprime with the mod we're working under, 13 here.
sour arrow
Exactly. If you're dividing a number that's not coprime to n, there's other things you need to do. Don't worry too much about that. CRT fails in that case
robust mango
hm
so 49 here, it doesn't matter at all?
I looked at a video. Let's say we have x=amod(b). What it said was the gcd b/w (a,b) and (x,b) both has to be 1.
In order to divide both sides
I just wanna make sure what's right before we continue
sour arrow
That's coprime, yeah
There's no number that divides both, other than 1
The 49 does matter, because I divided it by 7 to give 7
I had to find some number divisible by 7 lol
robust mango
yes i understand, but what i'm trying to ask is gcd(7k,13) = 1, gcd(49,13)=1. Both of the gcds need to be 1 in order to divide both sides, am I right?
That's all I'm asking.
sour arrow
I'm trying to divide by 7 in a (mod 13) equation
So I need gcd(7,13) = 1
And that's it
robust mango
I see.
sour arrow
Since they're both prime, this is easy to see
robust mango
Yes.
But 10/7 would've been complicated, so you used 49mod13
to make things easier?
sour arrow
10/7 doesn't make sense in a modular equation, but 49/7 does!
You'll always be able to find something like that yeah
robust mango
cause we're talking integers?
sour arrow
Integers are the only existent things
sour arrow
Yeah! We've shown that
k = 7 + 13p
For some p
Now, repeat the process.
x = 6 (mod 22)
1 + 7k = 6 (m22)
1 + 7(7 + 13p) = 6 (m22)
robust mango
Yes, I'm copying down what we're doing. Don't think I'm not here!
sour arrow
It gets a little messy oop. Thank God this is the last step
Just like last time, we want to algebraically solve for p
robust mango
Right..
So we have 91P + 50=6 mod (22)
if we subtract both sides by 50, we'll get 91P=-44mod(22)
does that negative number bother us?
sour arrow
Nope! You can always add 22 to it over and over if you're not comfortable
robust mango
How?
robust mango
ah yes, when -44 is divided by 22, remainder is 0.
and once again, we checked gcd(91,22)=1.
sour arrow
Exactly
robust mango
so, we've got x, k and p
sour arrow
91 = 7ร13, so it's enough to know that 7,13,22 are each coprime to eachother
p = 0 + 22q
for some q
Now! That's a lot of seemingly random info but we're essentially done lol
robust mango
so how do we put it all together into something that makes sense? ๐
sour arrow
x
= 1 + 7k
= 1 + 7(7 + 13p)
= 50 + 91p
= 50 + 91(0 + 22q)
= 50 + 2002q
So,
x = 50 (mod 2002)
And that answer is unique due to CRT
sour arrow
There is no other answer that can't be reduced to x = 50
Like, x = 17 (mod 2002) is definitely not a solution to those equations
robust mango
so 50 is the only one?
robust mango
i don't quite follow you
will the answer be always unique?
suppose we had x=2052(mod 2002), then we can reduce it to x=50mod(2002), is that what you mean?
sour arrow
Exactly
robust mango
so x=50mod(2002) can't be reduced further
sour arrow
But no number that reduces to 17 (mod 2002) can be a solution to this
I know that without needing to check, since CRT guarantees it
robust mango
Yeah.
sour arrow
One might say THAT is really CRT
robust mango
I'd really appreciate if you could give me an example of this uniqueness you tried to explain
it's not in my course, but I do want to know
sour arrow
There's no solution in the form x = 17 (mod 2002)
robust mango
but why 17 only? there's no solution anything except 50, 50 + 2002, 50+4004
robust mango
what about everything from 0to49
sour arrow
The only solutions will reduce to 50
robust mango
Ah yes
sour arrow
And any number that reduces to 50 is a solution
(mod 2002) is the number that makes this work
robust mango
just one more question
can we do it like 50+2001, lets say. Now that is also divisible by 2002
but it does not give the remainder of 50, so it's not acceptable?
sour arrow
Not acceptable
robust mango
Because the remainder is not 50?
sour arrow
Exactly all solutions are x = 50 (mod 2002)
robust mango
Man, thanks a lot! ๐
robust mango
I'm ready
sour arrow
The solution is unique (mod 9ร13ร22)
You can just search for solutions using this
This can sometimes be slow, it can sometimes be fast
robust mango
9x13x22 or 7x13x22?
sour arrow
Sorry 7 lol
robust mango
so how do I search that way?
sour arrow
I'd start with the biggest mod. The solution needs to satisfy x = 6 (mod 22)
Does x = 6 (mod 2002) work? You can try 6 in the other equations
No, because 6 isn't 1 (mod 7). That's not the solution.
robust mango
ah I see
sour arrow
So then try the next. Is x = 28 (mod 2002) a solution?
And it won't be long before you realize 50 works for all
robust mango
no it's not
ah yes, for "all"
how'd you pick x=28mod(2002), where'd that 28 come from
robust mango
ah
sour arrow
I picked the largest mod to run through solutions fast
robust mango
Don't mind, I think it might be more lengthy and it's trial and error. I'm required to do it by CRT
But your method is good to check the answers
sour arrow
CRT is used to guarantee the unique solution (mod 2002)
This is a trial and error way to find the unique solution
If you want to show work, then yeah do the first lol
But very often you can find that solution mentally and quickly
robust mango
Thanks a lot man!
sour arrow
Np. Good luck with it lol. Feel free to ask if there's anything else
daring bane
Quick question: I am required to find all anti-symmetric relation on a defined set with n elements? I don't know where to start? I tried using PIE (Inclusion-Exclusion Principle) but that resulted with a lot of requirements. I also thought about induction by laying out some arbitrary sets with n elements increasing one by one (let's say till 10) in hope of finding a formula, but that seems inefficient and I don't think it will even work out. So can someone help me?
Edit: I repositioned my question because I saw that I was interrupting an discussion before
floral wind
How do you calculate the radius and interval of convergence for a power series
sum from 0 -> infinity
((-1) ^ n)((4x + 1)^ n)
weary tiger
Do you know the cauchy hadamard theorem ?
floral wind
No
we just started with the power series
we have term-by-term differentiation theorem
but not sure whther that has to do with radius
floral wind
Link tutorial or smth?
daring bane
Can smd explain why dividing a range of a an ordered set of natural numbers by an integer, gives all the numbers which are divisible with this number?
daring bane
Let's say you have a set A with natural numbers from 1 to 100. How would you find the numbers which are divisible by 7 in this set?
You find the largest multiple with the floor operator?
stray reef
you can find the largest of those numbers like that, sure
daring bane
What if we want to find the number divisible by 7,8,9?
Do we use the PIE (Principle Inclusion Exclusion) like this:
vital dewBOT
Totoxic:
stray reef
if D_k is the set of all multiples of k, and by "7,8,9" you meant "7, 8 or 9", and you want to count all these numbers...
then no.
those $\cup$'s should be $\cap$'s.
vital dewBOT
Ann:
stray reef
then no.
not even close.
divisibility by 7, 8 and 9 is the same as divisibility by lcm(7,8,9).
and since 7, 8 and 9 happen to all be coprime, their LCM is their product.
7 * 8 * 9 = 504
no number between 1 and 100 is divisible by 7, 8 and 9 all at once.
daring bane
oh i get it, i must have misinterpreted the question :/ because it makes sense what you said
stray reef
or you failed to communicate properly what exactly you want here.
vital dewBOT
Totoxic:
stray reef
there you go
daring bane
So let me get the intuition,
aren't we removing the intersection of the three sets three times by doing the removal of two intersection per each set
daring bane
Oh! So since it cancels out we add it with the intersection of these three
ok i get it
Ok i get the intuition but now i am stuck at counting. I know how to do it for one set
But i dont know how you do it for two intersections :\
vital dewBOT
Totoxic:
daring bane
How would this be calculated :/
Wait
This means the elements that are both divisible by 7 and 8
stray reef
divisibility by a collection of numbers is equivalent to divisibility by their LCM, and i definitely mentioned that before.
daring bane
Oh ok i understand this
stray reef
D_7 \cap D_9 = D_63
daring bane
What if we want to find the number not divisible by 7,8,9?
Do we find the numbers divisible by 7,8,9 as shown above and than substract the total range of the set with the numbers divisible 7,8,9?
stray reef
what do you mean by "not divisible by 7,8,9"
do you mean divisible by none of them, or divisible by some but not all
stray reef
then yes that's just $|\overline{D_7 \cup D_8 \cup D_9}|$
vital dewBOT
Ann:
daring bane
okay thank you!!
daring bane
quick question: a set containing integers from 1 to 500 contains 500 elements or 499 elements in total?
stray reef
1 to 500 inclusive?
daring bane
yes
because idk but I cannot find how to calculate the numbers which are not divisible with any integer from 3 to 10. I made an attempt but got the wrong answer
it should have have been 172 but i got 200
vital dewBOT
Totoxic:
daring bane
and i did
stray reef
that... counts the number of integers divisible by 3, 4, 5 or 7
daring bane
yes
daring bane
Consider the set A of integers from 1$to 500. How many numbers are in A that are not divisible by any integer from 3 to 10
stray reef
you might have just fucked up your arithmetic
daring bane
here
vital dewBOT
Totoxic:
stray reef
_<
daring bane
๐ i am sorry i am not a pro in LaTeX
stray reef
i mean
what even
why are you computing those lcms and then adding them together
this just makes no sense
daring bane
I am encountering this problem which I don't how how to solve? The problem also gives an hint but I don't know either what that means
cerulean sentinel
Prove that
vital dewBOT
bilyan:
lean creek
@daring bane I think he was asking a completely separate question lol
tight spire
lean creek
nah
write as a series sum for each
you'll see that one is "backwards" the other by symmetry
we're counting n/2 terms of each
so together it's 2^n
is your proof sketch
there's a useful sum by newton
@cerulean sentinel
daring bane
Can someone give me an example of an order embedding
vital dewBOT
trashman:
weary tiger
?
stray reef
8! in the numerator.
weary tiger
it asked for a 10-letter though
thats what i was confused about
"calculus" is 8 letters while it asks for 10 letter words
stray reef
oh
uhh
zero then
unless we allow letters to repeat as many times as we want, then 5^10
rare vortex
Hello? I'm a bit confused of how this goes:
x and y are any strings of a's and b's
Which ones are substrings, and which ones are not
clever nacelle
Pumping Lemma States: If A is a Regular Langage then A has a Pumping length P such that any string S where |s|>= P may be divided into three parts S = x y z such that the following conditions must be true:
x yi z ะ A for every i >= 0
|y| > 0
|xy| <= P
Proof using pumping lemma, that language is not regular.
L = { w | w belongs to {a,b}* and w is a palindrome of even length }
Let L be regular
Let P be the pumping length, P=6
Let a valid S be aabaababbabaabaa with a pumping length of P
Now, divide it into 3 parts, such that x =aabaa, y=babba z=baabaa
Now per pumping lemma if L is a regular language,
for all i > = 1, x yi z ะ L
Therefore, when i = 1, aabaababbabaabaa ะ L
And then i = 2, aabaababbababbabaabaa notะ L as it is not an even palindrome
Therefore our assumption is wrong and we proved that L is a non-regular lagnuage
Can someone verify this is true
weary tiger
Can anyone just help me with traslating what the statment says in to english just looking for clairification
faint narwhal
What don't you get
weary tiger
baically I was just wondering how to say the statement I think If I new that I might be able to figure it out
I know it has to be something like for x and y such that y = 2x + 1
is what I said correct for A?
no really sure how to work with these statements
weary tiger
well one other thing thats confusing me is R^2
does that mean the things in the set are
1, 4 , 9, 16......
weary tiger
ahh okay
errant bear
think of it as the dimensions of each element
weary tiger
okay
errant bear
R is one dimensional, and so on
weary tiger
so if it was (x, y, z) it would be R^3
errant bear
so what are the members of A
errant bear
?
errant bear
well no, the elements of A are cordinates, right
weary tiger
so like
{(1, 3) , (2, 5), (3, 7)......}
errant bear
yes
can you say in english a rule that they all follow, or describe A in general
keep in mind x and y arent defined to be in Z
weary tiger
in defined to be in R
which is All reall numbers
so for all x y is a odd number?
is that correct?
errant bear
noo
errant bear
R^2 only implies that the elments of A are an ordered pair
weary tiger
y is not always odd
weary tiger
for x in R
weary tiger
they the statement 2x + 1 is not always negative
then arent x and y both just real numbers?
weary tiger
linear function
errant bear
ok
weary tiger
like I mean linear graph
errant bear
aka a line
weary tiger
yes
errant bear
so now we are defining a set A to be composed of elements (x, y) such that they ________
weary tiger
are linear?
errant bear
specifically what do they satisfy
weary tiger
I dont know what they satisfy ๐
weary tiger
for all n such that n is odd
errant bear
yes, also the same as { n : n is odd}
so this new set A is the set of ordered pairs (x, y) that satisfy what
weary tiger
yes so this is for all x and y such that y is 2x + 1
weary tiger
satisfy the equation 2x +1
weary tiger
so is the set of points that lie on the line y = 2x + 1
weary tiger
yes yes mistake in typing
errant bear
now what is B and C
weary tiger
and then B is the set of points that lie on the line 3x
errant bear
ok , now you should be able to do the problems
weary tiger
x is the set of points that lie on the line x - y =5
errant bear
yes
weary tiger
how does this help me with A intersect B though
A intersect B is everything in A
and B
but not in the same one
errant bear
A intersect B is the elements that are shared between them
weary tiger
I thought A union B was the shared ones??
weary tiger
A U B is what is common in A and B no?
for example
A = { 1, 2, 3, 4}, B = {1, 2, 3}
A U B here is 1 2 3no?
weary tiger
okay so A intersect B is the similarties basically
weary tiger
would it just be 3x
weary tiger
yes
errant bear
so
weary tiger
is it just one spot
how do I find that?
I know that 3 times 1
so they both have (1, 3)
weary tiger
thats should be it