just to be clear by n you mean the number that can be composite and have prime factors
#discrete-math
coral raven
here n is just any number, yeah
weary tiger
so if you know all the prime factors =< m, then all the composite numbers up to m^2 have one of those prime factors why tho ? where does this theorem come from?
Does ANYONE know how to factor equations
coral raven
so if you know all the prime factors =< sqrt(n), then all the composite numbers up to n have one of those prime factors
would you agree with that
coral raven
Does ANYONE know how to factor equations
go to like #prealg-and-algebra or one of the questions channels lol
we're busy here
so if you know all the prime factors =< sqrt(n), then all the composite numbers up to n have one of those prime factors
would you agree with that
weary tiger
I mean show me the proof of it
coral raven
bruh
weary tiger
I don't agree yet
it is true but why? I didn't understand why
if n is composite and has prime factors < sqrt(n) then why all numbers up to n are either prime or has those prime factors in them
or you meant potentially have those prime factors in them ?
take 18 and 22
or take 9 and 22 they don't have the same prime factors
coral raven
if n = kp and p > sqrt(n), then k < sqrt(n)
k must either be a prime or have even smaller prime factors
either way there is a prime factor < sqrt(n)
[P]: so whenever n is not prime and you have a prime factor > sqrt(n) [A], you have a prime factor =< sqrt(n) [B]
so if you think n is not prime but you don't have a prime factor =< sqrt(n) [not-B], you don't have a prime factor > sqrt(n) [not-A]
so if n has no prime factors =< sqrt(n), n has to be prime
and if n is composite, then it has a prime factor < n, call it p
then if p =< n, we're done
and if p > sqrt(n), by [P] there is a prime factor =< sqrt(n)
weary tiger
ok I understand those
but this was not my question
you said if I have a number say 12 and it has prime factors
coral raven
yes
weary tiger
so if you know all the prime factors =< sqrt(n), then all the composite numbers up to n have one of those prime factors would you agree with that
coral raven
no
weary tiger
2 -5 -7
coral raven
no
weary tiger
only the prime factors of 12?
coral raven
if you know all the prime factors < sqrt(12), just 2 and 3
coral raven
i have to go at half past
if you know all the prime factors < sqrt(12), then all the composite numbers =< 12 have one of those prime factors
so 10 has a factor of 2
9 has a factor of 3
8 has a factor of 2
coral raven
if you know all the prime factors < sqrt(n), then all the composite numbers < n have one of those prime factors
now let m = sqrt(n)
then if you know all the prime factors < m, then all the composite numbers < m^2 have one of those prime factors
so if you know all the prime factors < 5, so just 2 and 3, then all the composite numbers < 5^2 = 25 have a factor of 2 or 3
if you know all the prime factors < 7, so 2, 3 and 5, then all the composite numbers < 7^2 = 49 have a factor of 2, 3 or 5
if you know all the prime factors < 11, so 2, 3, 5 and 7, then all the composite numbers < 11^2 = 121 have a factor of 2, 3, 5 or 7
i have to go now
weary tiger
if you know all the prime factors < sqrt(12), then all the composite numbers =< ...
one more question about this if I have a prime factor > sqrt(12)
does it still apply?
weary tiger
bye
opaque chasm
how should i go about doing this?
lyric pumice
@opaque chasm Have you tried utilizing the definition of expectation value as a linear combination?
fallow pawn
heavy spindle
Any help on how to prove this statement without just showing examples of n = 2, 4, 6, 8
I used n^4 = k mod 10
and for n=2m, k is always 6
faint narwhal
note that n^4 mod 10 only depends on the last digit of n
heavy spindle
So because of that fact, is it valid to prove for only 2, 4, 6, 8
faint narwhal
kind of
for example, you can say that if the final digit of n is 2
then since n = 2 mod 10, that n^4 = 2^4 = 6 (mod 10)
heavy spindle
ok thank you
weary tiger
hey
the name 
is it true to say that if A is a proper subset of B, A is a subset of B?
or does the nuance between proper and improper subsets render that statement false?
abstract otter
can someone help me start this problem? I can only think of the vandemonde identity
that says
but summation is on the wrong side
stray reef
it's simpler than that is it not
left hand side is just (2^n)^2 while the right is 2^(2n)
@abstract otter
weary tiger
When using an element argument to prove something, are you allowed to use laws of sets to just rearrange the sets to be the same?
last timber
@weary tiger wym "use laws of sets to rearragne"
weary tiger
Let $G$ be a graph with $n$ vertices, $A$ its adjacency matrix and $I$ the identity matrix. Show that $G$ is connected if and only if $(I + A)^{n-1}$ contains no zeroes. If $G$ were to be disconnected, where would the zeroes of the matrix lie?
vital dewBOT
963271
weary tiger
i really don't see how this can be determined 
i guess there's some linear algebra argument i'm missing?
faint narwhal
@weary tiger So if A is the adjacency matrix, what does A^i represent in terms of the graph? For some integer i
weary tiger
well it should be just whatever our matrix is, to that power... but i believe its also the matrix that indicates whether there exists a path of length i from the two relevant vertices
faint narwhal
right
so if you think about expanding out (I + A)^(n-1)
you're going to add up a lot of things of A^i
weary tiger
mhm
faint narwhal
so if something is nonzero in A^i, that means there's a path between those two vertices
so by adding up all these A^i (since everything is positive and nothing cancels out), the places where you get a zero entry in (I + A)^(n-1) is where all the A^i were zero
but that must mean there's no path between those two vertices
weary tiger
(I + A)^(n-1) = (I) + (n-1)*A^(1) + (?)*A^(2) + ... + (n-1)*A^(n-2) + A^(n-1)
you mean this?
faint narwhal
yeah
weary tiger
ah i see
thanks!
also, do you happen to know the proof for the correlation between the power of the adjacency matrix and the fact that it also indicates path lengths i ?
my prof scibbled some stuff, induction apparently, but i don't quite see how A^(k-1) * A^(1) = A^(k)
faint narwhal
Uh, that's just matrix multiplication and exponent rules?
obtuse lance
what your prof scribbled looks good, just gotta think about what it means in that sum
weary tiger
sorry i meant how he gets to those A * A
obtuse lance
for instance let's just look at one entry $(A^2){ik} = \sum{j=1}^n A_{ij}A_{jk}$
vital dewBOT
96
obtuse lance
the ik entry of A^2 come exactly from looking if A_ij and A_jk are both 1
you just gotta think about this and that's what's going on
winter nexus
Need help with this problem
faint narwhal
what have you tried?
winter nexus
approximate complexity for g(n) is O(f(n)) if $g(n)\leq cf(n)$ for some constant c. If I can show that g(n) is less that or equal to epsilon/c then I can show it to be of order f(n)?
vital dewBOT
0708805962847259
abstract otter
thanks a lot 558!
what about this one? i'm not sure how to handle both m and n
i thought that maybe i could just put n = m+1
weary tiger
You can quite easily see that $\binom{n}{k} \binom{n-k}{m-k} = \binom{m}{k} \binom{n}{m}$ Now you can factor out $\binom{n}{m}$, cancel it out and you have a pretty obvious identity.
vital dewBOT
06695
abstract otter
thank you 🙏
winter nexus
Need help with this problem
Anyone?
untold raptor
There is a professor who is liked by every student who likes at least one professor. Every student likes some professor or the other. Therefore, there is a professor who is liked by all students. can someone help explain to me why this wff is valid?
grand elm
every student likes at least one professor and there is a professor who is liked by all students who like at least one professor, thus there is a professor that is liked by all students
untold raptor
if S(x) = x is a student P(x) = x is a professor L(x, y) = x likes y
does that mean the wff is L( (∀)L( S(X) ,( ∃x)P(X)) ,( ∃x)P(X)) L( S(X) ,( ∃x)P(X)) → L( (∀) S(X) ,( ∃x)P(X))
frosty hollow
Hi, I have a question on exercise set 1.2, problem 17 from Discrete Mathematical Structures Third Edition by Kolman , Busby , Ross.
The question is as follows:
In a survey of 260 college students, the following data were obtained: 64 had taken a mathematics course, 94 had taken a computer science course, 58 had taken a business course, 28 had taken both a mathematics and a business course, 26 had taken both a mathematics and a computer science course, 22 had taken both a computer science and a business course, and 14 had taken all three types of course.
How many students were surveyed who had taken none of the three types of courses?
My thought process is this would be the cardinality of the union of the three types of course, math, cs, business minus the universal. From the data provided I know that the cardinality of the universal is 260 distinct elements and the union of the three types of courses can be found using this theorem.
I then plugged in the data into the theorem I got 154 distinct elements (or students) who had taken at least 1 of the three courses. I then subtracted it from the cardinality of the universal which is 260 and got 106. The problem is that when I checked the answer the correct answer is 116. My question is, where did I go wrong? Is there something I forgot to include or were my calculations wrong? I appreciate it if you've read up till this point and would also be grateful for any help. Thank you.
weary tiger
It follows from the fact that gcd(a,b) = gcd(b, a-b)
you meant a-qb?
?
yes if a = bq+r
hint : you have to prove that every divisor of a and b divides b and a-bq. this shows that gcd(a,b) C gcd(b,a-bq)=gcd(b,r)
then you prove (trivially) that every divisor of b and a-qb=r divides a and b
so gcd(b,r) C gcd(a,b)
ok we proved that
equality of sets thus follows
but the conclusion still doesn't make sense
why
why gcd(b,r)=gcd(a,b) uh?
does't make sense 😦
so r = a-qb not a
why doesn't it make sense if you proved it ? 😄
check this out
why gcd(b,a-qb)= gcd(b,a) ok b=b and a-qb !=a
ah is this a property
grand elm
gcd(a, b) is a common divisor of a and a-b, thus it's less than the greatest common divisor of a and a-b
weary tiger
why less tho?
a-b is less than b
thus the gcd of a and a-b should be less than the gcd of a and b
@grand elm
I am getting confused
anyone help please
grand elm
it's less strictly by definition
think of it as "it's also less than or equal"
since it's equal anyways
abstract otter
i have the general idea for this question but i can't formulate a legit proof
so my idea:
since every pair must have one movie together
since seating capacity is < 2/3, some person must sit on ground
the proof i'm attempting is by induction
base case n = 2
2/3n is 1.33
since the two citizens must have a movie in common, then for one of the movies there has to be 2 people in the cinema
but i'm stuck figuring out an induction step
pallid belfry
For the shortest path problem. When can the shortest path not be determined?
last timber
when there is no path
weary tiger
A hamiltonian cycle of a graph $G$ is a cycle that visits every vertice exactly once, regardless of the edges. Show that a graph with $n$ vertices all of degree $≥n/2$ must have a hamiltonian cycle.
vital dewBOT
ɐʎxʎuɹɐ
weary tiger
I'm not sure what argument is needed here...
I tried contradicition but that didn't work
weary tiger
You need to give a construction of such a graph
weary tiger
I tried contradicition but that didn't work <:thonk:406575732563902485>
What was the contraction you tried ?
You assumed that there exists a vertex whose degree is less than n/2
?
I tried to find an argument but I didn't get very far
You need to give a construction of such a graph
i can see a construction for n/2+1, but you can go further than that?
Not really as you expected
First thing first you have to prove that the graph is connected
With the fact that all its vertices have degree greater than n/2
Then once you proved this
You have to show that a Hamilton cycle exists by induction
A cycle is a path that starts and ends at the same vertex
As long as m + 1 <= n, there is a path visiting m + 1 distinct vertices with no repetition.
Consider the case where m+1<n and m+1=n and show that in both cases you can use connectedness to show that your path extends to form a Hamilton cycle
I'm still stuck on step one 
For connectedness ?
ye
is this pigeonhole?
Suppose G is not connected, so that G has at least two components, say V0 and V1
...
Since n = |V | = |V0|+|V1|, we must have either |V0| <=n/2 or |V1| <=n/2.
Wlog, suppose |V0|<=n/2
then both components (must have degrees at most n/2-1) cannot have vertices with degrees ≥n/2
hmmm
hybrid tendon
I need to find the number of square sub-matrices of N x M matrix where the average of elements of the sub-matrix is >= k, Provided that all the elements in the given matrix is strictly increasing row-wise and column-wise .
Any help on how to approach this problem? I already tried brute force approach, I need something efficient.
weary tiger
Wlog, suppose |V0|<=n/2
then the degrees of the vertices will be at most n/2-1, but since we impose n/2, then that means that one of its vertices is linked to a vertice in the other component, thus it is connected
Would anyone be willing to check my work for a problem?
weary tiger
> Wlog, suppose |V0|<=n/2
then the degrees of the vertices will be at most n/2-1...
Sure
More formally
pick any v in V0. Then deg(v) >= n/2, but every neighbour of v is contained in V0 and is not v, so deg(v) < n/2; this is a contradiction.
that's a cleaner argument
makes more sense
weary tiger
Reflexivity, symmetry and transitivity are the properties you must prove
Yes I did that
I was just wondering if the work was correct
So by induction, we have n points, we know that for n-1 we can find a path. Worst case would be n even and n-1 odd. Regardless, we have a cycle of n-1 we can construct. Furthermore, the left-out point is connected to ≥n/2 points. By pigeonhole, it must be connected to two points in a row. Thus we can construct a new n length cycle.
weary tiger
So by induction, we have n points, we know that for n-1 we can find a path. Wors...
Looks fine
@weary tiger are you good at knowing how to find equivalence classes?
Hmm. It depends on the equivalence relation that’s given
If I upload my work for a different problem, do you think you would be able to tell me if my work is correct?
It’s for the same problem I uploaded and it’s asking for the equivalent class for [ (1,2) ] and [ (3,5) ]
weary tiger
So by induction, we have n points, we know that for n-1 we can find a path. Wors...
Lacks a bit of details tbh
weary tiger
It’s for the same problem I uploaded and it’s asking for the equivalent class fo...
You can send ur answer
Does it?
Suppose v0,v1....,vn is a path
How can you extend this to be a cycle ?
v0 is adjacent to vn then we already have a cycle.
How about the case where v0 is not adjacent to vn?
That is the harder case
Doesn't my argument already provide us with a cycle?
of length n-1, to which we add the last vertice
b and c
weary tiger
So by induction, we have n points, we know that for n-1 we can find a path. Wors...
Hmm.. actually using pigeonhole is quite smart, I think that will do!
Alright, thanks!
hybrid tendon
I need to find the number of square sub-matrices of `N x M` matrix where the ave...
It would be great if someone can help me with this question
tired hawk
Is there any k s.t. every bipartite and k-connected simple graph G with parts X and Y s.t. | |X| - |Y| | <= 1 is traceable? If |X| = |Y|, then is there any k s.t. G as defined above is Hamiltonian?
Clarification : This is not an exercise question... I'm asking whether there's any theorem which implies this or can help with proving/disproving this
P.S. There's a related result which says that every ciel(n/2)-connected graph of n vertices is Hamilton
prisma cypress
i could use a little help when it comes to understanding vertex and edge connectivity
prisma cypress
you want to find the vertex and edge connectivities for this graph?
is what i need to do but im not exactly understanding how to do so
stray reef
okay
so the ideas behind vertex and edge connectivity are almost the same, in a way. i will explain this based on vertex connectivity.
when finding the vertex connectivity of a graph, what we want to ask ourselves is this: How many vertices do we need to remove so that the graph falls apart (i.e. stops being connected after we remove the vertices & all edges incident to them)?
and when we say that, for example, a certain graph G has vertex connectivity 4, we mean that removing 1, 2 or 3 vertices never makes G fall apart, but there is a way to remove 4 such that it does fall apart.
prisma cypress
okay... so taking that into account.. it looks like removing vertex 6 makes it fall apart?
stray reef
yup.
a single vertex.
this means your graph has vertex connectivity 1.
for edge connectivity it's exactly the same! just replace vertex with edge. and deleting an edge just means cutting the edge out; we keep the vertices that the edge was incident to.
prisma cypress
hm.. okay, so for this one.. if i remove 3 it cuts off 1 but im not sure if cutting off one vertex counts as making the entire thing fall apart
prisma cypress
alright, thank you
prisma cypress
what vertex would you recommend for a euler circuit if there is one, ive made multiple attempts but all of em fall short at the end
the one to start with i mean
stray reef
an euler circuit is a cycle which visits every edge once, right
i would suggest visually rearranging the vertices in this graph to untangle it a little
prisma cypress
has to have every single vertex, every edge only once, and cannot be done if there is a vertex with an odd degree, unpaired edge, etc
stray reef
also why not start with g or e
prisma cypress
well uh i did come up with this but whether its exactly right i am not 100% sure
prisma cypress
alright.. hm. for whit values of n does kn have a euler circuit..
prisma cypress
i need to make a... planar embedded graph with this?
last timber
embedded?
prisma cypress
okay my mistake its planar embedding not planar embedded
prisma cypress
im not sure what it should look like..
last timber
well what makes it nonplanar rn?
i mean consider what happens if you put vertex F inside BED
prisma cypress
...? but then idk how to tell how many regions it has if this is right
last timber
use defns tho
prisma cypress
what
prisma cypress
also im not sure how to do this..
lilac delta
Is d true?
for example 1/2 is 0.5 -> not an integer
Is it supposed to be false?
prisma cypress
could i get some assistance on how to actually use BFS and DFS
faint narwhal
shadow pond
Hey guys
I am looking to write a recurrence relation and an explicit formula for.
My recurrence relation is something along the lines of a(n) = 1 + a(floor(n/2)).
However, for my explicit, I am a bit lost. Could I get some guidance/help? And I guess that depends on whether my reccurence relation is right?
unreal stump
It would just be 0
shadow pond
wait what?
unreal stump
For example ,5->2->1->0
unreal stump
Take n=5 and apply that loop
unreal stump
You know binary?
shadow pond
a little bit
i'm supposed to get something that resembles log n
ik this is log
but idk how to show it
unreal stump
How's the reccurence related to this?
stray reef
@unreal stump we aren't interested in the result
we are interested in the run time
(presumably)
shadow pond
yeah
unreal stump
Yea,That would be log_2(n)
stray reef
you halve n a bunch of times until it's less than 1
unreal stump
Maybe a +1
shadow pond
okay i see how you're doing it
i learned about the substitution method
to showing proof
so i know a(n/2) = 1 + a(n/4)
unreal stump
Try converting the input to binary,and note that each step chops off a digit
shadow pond
and i know a(n/4) = 1 + 1(n/8)
thus a(n) = 1 + 1 + 1 + a(n/8)
how can i show that from this?
stray reef
?
your loop (approximately) halves the value of n
if you want to be formal about it i guess you can do something like T(n) = T(n/2)+1 and apply master theorem idk
shadow pond
if you want to be formal about it i guess you can do something like T(n) = T(n/2...
yeah this is what i have fo rmyecurrence relation r
so if i want to solve my recurrence relation
to get an explicit formula, how could I do so?
stray reef
it's either impossible or not worth the effort imo
and really it's T(n) = T(floor(n/2))+1... meh
shadow pond
and really it's T(n) = T(floor(n/2))+1... meh
yeah ik i have this xd
i leanred about using 2^logn
so could a(n) be
1 + n/2^logn ?
stray reef
you don't need to reply-ping me every time btw
shadow pond
oh sorry
stray reef
idk idc
unreal stump
You haven't been taught guessing?
shadow pond
it's guessing?
unreal stump
I mean,I guessed binary works because it's /2
And n in base 2 representation has log_2(n) digits
pallid lintel
can anyone tell me the least upper bound on the number of dimensions a 20 coloured n-dimensional complete icosahedron must have in order to guarentee the existence of a 20 vertex monochromatic clique on a face of the icosahedon. I've been thinking about this question a lot lately, i'm sure many others have too.
weary tiger
I'm sure everyone has at least once in their lives thought about this problem.
modest spoke
Confused about what theorem 1 is proving
If it is a well-ordered set, doesn't that imply we can just use mathematical induction
quaint pike
I need some help figuring out what T(n) would be if I was given this set of patterns, trying to figure out an adequate function:
(n, x)
(1, 1)
(2, 2)
(3, 3)
(4, 4)
(5, 5)
(6, 7)
(7, 10)
(8, 14)
(9, 19)
(10, 25)
So basically, the first 5 loops are the same number as whatever n is, but once n becomes 6, x starts increasing by a certain amount, starting at an increase of 2 (when n=6), but the pattern I noticed is that whatever the next number for X is, it's 1 PLUS the previous amounted increase. So if X increased by 3 when n=6 became n=7, then X will be increased by 4 when n=7 becomes n=8.
If someone can help me figure out how to put this into the form of a function, that would be appreciated, thanks.
unreal stump
Do you know iverson brackets?
quaint pike
Not really
unreal stump
Ok,I suck at latex,so I am doing it this way:
f(x)=x+x>5(x-5)/2
[x>5] is 1 if x>5 and 0 otherwise
quaint pike
I updated my summary thing below the pattern because I made a mistake in what was going on
But let me observe your answer
I think I did something wrong or the answer you gave is not the same format. Here is an example from another similar problem with the solution:
This is from my friend btw
Essentially you have to figure out how many loops/iterations have been made (x) based on whatever the value of n is
Here's my original problem if you were wondering how it looks like
I did all the work and the pattern that I posted above is what I got
unreal stump
It should be O(n^2) I think
quaint pike
what is O again?
unreal stump
If g is O(f),it means there's a constant c such that g<cf for all inputs of n>=n_0 for some n_0
quaint pike
Okay I have to apologize here lol, but so far the teacher didn't teach any of this to us, so I think the pattern that I got seems to be wrong
quaint pike
yeah this one is related with complexity classes
my other friend who was helping me said it might be complexity class n!
the factorial or whatever
floral dome
does any one understand this How big is “countably infinite”.
unreal stump
As big as N
grand elm
If it is a well-ordered set, doesn't that imply we can just use mathematical ind...
yes, that's what the theorem is proving
gritty crescent
does any one understand this How big is “countably infinite”.
The set under consideration has exactly as many distinct elements as the set of natural numbers. Alternatively, there exists a bijection between the natural numbers and this set.
abstract otter
can someone give me an example of double counting vs algebraic manipulation?
558 helped me a few days ago with this :
i used binomial theorem to show both sides are 2^(2n)
but how is this different from "algebraic manipulation"
weary tiger
what you did sounds like algebraic manipulation
by counting argument I think we usually mean telling the a story how to count something but using two different ways to count it
For example, you can say that both RHS and LHS describe the number of all subsets of set [2n]. Try to justify both sides of this equation by counting the subsets in two different ways
@abstract otter
abstract otter
hmmmm how do i count in different ways?
abstract otter
oh so i can expand the right side summation>?
abstract otter
nCk?
weary tiger
One way is to count all the subsets containing 0 elements, all subsets containing 1 element and so on up to all subsetes of [2n] containing 2n elements
which is exactly RHS
abstract otter
weary tiger
think about it for a bit if you dont see it
we are not doing algebraic proof
we want to do a combinatorial proof
(counting argument)
do you get it?
abstract otter
yeah im here
weary tiger
So, lets say someone asks you how many subsetes are there in the set {1,2,...,n}
do you know how many there are?
abstract otter
yes, because it's a finite set
weary tiger
well what is the number then
abstract otter
at most n?
weary tiger
it's exactly 2^n
for any set of length n, number of subsets of that set is 2^n
that you should know by now
abstract otter
ok
weary tiger
so lets assume we know that
so if I gave you a set, how could you count all the subsets of that set, without using that formula (2^n)?
abstract otter
the dumb way would be to list it out
weary tiger
exactly
you list the subsets that have 0 elelements (empty set), list all teh subsets that have 1 elements and so on
abstract otter
isn't that just nCk?
weary tiger
yep
sooo, if you wanted to count the subsets of the set [n], you could just count the ways you can choose 1 element, 2 elements and so on
abstract otter
so like nC0 + nC1... nCn?
vital dewBOT
Godel
weary tiger
So in your problem, the RHS is all the possible subsets of the set [2n]
Left side also counts all the subsets but in a different way
I'll give you a hint which is major in that reasoning
abstract otter
im listening
weary tiger
Consider dividing the set 2n on two sets of size n
Try to count the subsets of those sets to justify the LHS of equation
Then you will show using a counting argument that both sides are equal to 2^(2n) (all subsets of set [2n])
abstract otter
ok imma go try
abstract otter
when you separate the sets in 2, to account for the "lost" possibilities, you just multiply the two sets by each other?
doing this gives me 2^2n at the end
weary tiger
lost?
abstract otter
well if you split the set in 2
lets say it goes from 0 to n
and n+1 to 2n
the combinations between, say, n and n+1
are lost
weary tiger
I don't understand tbh
weary tiger
just like you wanted to list all the subsets, you can count the subsets in a different way
For example, you divide it into 2 like you said
how can you find a subset of size n+1
modest spoke
Is b an upper bound of the subset S = {a,b}
modest spoke
i dont know how
abstract otter
ok... i think i understand now
weary tiger
anyways, you can choose element from one side and from the other one
nocturne sapphire
Imagine using graph theory cringe-this post was made by set gang
weary tiger
so for example ivey homie, if you wanted to find all subsets of size 3, you can choose 0 from the first one and 3 from the second one, or 1 from first one 2 from second one and so on
abstract otter
ok so when i split in half
it becomes sum from 0 to n (n k )
sum from n+1 -> 2n (n k)
weary tiger
why +
no
like
how many 3 element subsets are there in the[2n] set if you divide it in half
abstract otter
nC3?
weary tiger
no
why
that would be numbers of subsets of size 3 from the left one
(or right obviously)
abstract otter
okok wait
weary tiger
by left right I mean 1 to n and from n+1 to 2n
abstract otter
does that mean how many subsets contain 3 elements?
abstract otter
im not sure how to find that, maybe 1?
weary tiger
what 1?
weary tiger
Ok wait
from set [2n] we want to find all subsets containing 3 elelments
we divide 2n into two sets: from 1 to n and n+1 to 2n
abstract otter
yes
weary tiger
that amount would be $\binom{n}{0} \cdot \binom{n}{3} + \binom{n}{1} \cdot \binom{n}{2} + \binom{n}{2} \cdot \binom{n}{1} + \binom{n}{3} \cdot \binom{n}{0}$
vital dewBOT
Godel
abstract otter
ohhhhh
weary tiger
because thats the number of ways you can choose 3 elements: 0 from 1 to n and 3 from n+1 to 2n
or you can choose 1 element from left one
so you have then 2 left in the right one to choose
etc
abstract otter
ok yeah that makes sense
weary tiger
so that was for subsets of size 3
the LHS in your problem counts all the subsets just try to figure out why, thats literally the same argument
weary tiger
yw
neon frost
Hello! Nice to meet you all. Would someone be able to verify my answer? I'm pretty confident for the first two points but I'm not too certain about the last bit
weary tiger
looks correct
neon frost
Cool thanks!
Also I know this might be much more to ask but the next question is
Where S is still {1,2,3,...,100} and I've been looking at this since yesterday and I have no idea where to start with this
weary tiger
idk looks like some pigeonhole assume none hold
neon frost
I have a feeling it calls for the pigeonhole principle as we were looking at that in class but I really don't know how to make the boxes for this
What do you mean by none hold?
weary tiger
you want to show at least one of those two is true
assume both are false and maybe try to find contradiction
It really looks like pigeonhole problem
neon frost
Ooh I see
Yeah I agree, I'll see if I can do this one. Otherwise I'll try to practice more pigeonhole problems
weary tiger
wait no either means only one right
so assume 1 and show 2 cant be true and vice versa
neon frost
Yeah but If I assume both are false and I get a contradiction does that mean both are true or at least one is true?
Oh I see
Thank you
weary tiger
like if you assume 2 there will be uniqueness problems I think
I mean they might not be distinct if 1 was also to hold
neon frost
Okay yeah
prime parcel
To make the power 8
Go with some simple expansion examples then u will get how to do it
naive gulch
ooh I see thanks!
naive gulch
For the first example they can just do that easily because x and y are alone right? as in (x+y)^25 with no coefficients
naive gulch
Also
How do I exactly prove by algebraic manipulation? Im not too sure do I just use expressions?
weary tiger
you can write nCk as n!/(n-k)!k! for example, using algebra show RHS = LHS
naive gulch
Ah okay, I got that but where exactly does the n^2 still come in ?
weary tiger
?
naive gulch
?
I tried writing both 2n choose 2 and 2 (n choose 2) in the form of n!/(n-k)!k!, but after that I'm not sure where to go
stray reef
nC2 = n(n-1)/2
(2n)C2 = 2n(2n-1)/2
your goal is now to prove that 2n(2n-1)/2 = 2 * n(n-1)/2 + n^2
and then do algebruh
carmine vine
for a subset of 6 vertices, the max number of edges is $\frac{(|V|)(|V|-1|)}{2}$
where $|V| <= 6$, but how can i extend this to a larger number of vertices?
vital dewBOT
Vaizex
stray reef
well by the handshake lemma you can say |E| <= 5|V|/2 can't you?
carmine vine
i actually don't know that lemma
carmine vine
yea
stray reef
that's the handshake lemma
stray reef
sum of all degrees is obviously bounded above by 5|V|
carmine vine
yeah
stray reef
now can we produce a 5-regular graph on n vertices for, say, all sufficiently high even n
wait of course you can
take n vertices evenly spaced around a circle, and connect two vertices whenever they're diametrically opposite or up to 2 steps away from each other
this will give you a 5-regular graph
not sure how tight the 5|V|/2 bound is when |V| is odd, but when it's even the bound is the best you can get
stray reef
okay so
when |V| = 2k+1 it sounds like you can have as many as 5k+4 edges (as opposed to the 5k+2 predicted by the bound 5|V|/2)
start with the 5-regular graph on 2k vertices as described before, and add to it a new vertex, not connected to anything yet
pick two edges in the graph which don't have common endpoints
cut them both in half
connect all four loose ends to the new vertex
quasi horizon
Hey guys, I am having a problem with not understanding how to write this equation into a reverse polish notation
(7+3) * 4-16 * 3 + 24 - (12/4)
quasi horizon
Nevermind, I got it
weary tiger
why exactly will we end up with no remainder like why is it guaranteed ?
like how do we know that eventually a remainder of 0 will end up in this sequence?
stray reef
we have a decreasing sequence of natural numbers
it must go down by at least 1 at every step
weary tiger
ok but why exactly does it have to reach 0?
and why the sequence can't contain more than a terms?
@stray reef
stray reef
you start with a and you keep going down
theres no way for you to cram more than a steps, each of size at least 1, into the interval [0,a]
stray reef
if at any point you get a 1 in your sequence then the next term is guaranteed to be 0
weary tiger
so I am going down by 1 but like we are doing a division there
stray reef
if at any point you get a 2, the next term is guaranteed to be 0 or 1
weary tiger
ah
stray reef
if at any point you get a 3, the next term is guaranteed to be 0, 1 or 2
there is a strong induction argument that can be set up here
weary tiger
there is a strong induction argument that can be set up here
yeah makes sense
stray reef
0, 1, 2 or 3
weary tiger
some things you just can't directly see , I am trying to understand it intuitively but I didn't see this coming
yeah and 3
just needed some deep explanation
thank you now I understand it
naive gulch
For something like this, how do I run each side through the factorial formula?
I know the left hand side translates into (2n!) / (n-2) 2!
stray reef
no it doesn't
if you want to go with factorials, then $\binom{2n}{2} = \frac{(2n)!}{(2n-2)! \cdot 2!}$
vital dewBOT
Ann
stray reef
also i said this but it seems you chose to ignore it
naive gulch
oh shoot yeah I meant 2n-2* oops I didn't write that in
And I didn't see that message I scrolled up :o lemme find it
Oooh I see it thanks!
naive gulch
Hmm I tried it they're similar but def couldn't get them to equal each other, might've screwed the algebra somewhere
stray reef
bruh for real
2n(2n-1)/2 = n(2n-1)
2 * n(n-1)/2 + n^2 = n(n-1) + n^2 = n(n-1 + n) = n(2n-1)
naive gulch
Oh thanks! I alr managed to get it I was just dumb and I had forgotten to remember the 2
blissful zenith
does anyone know abt adjacency matrices
sly fractal
i was looking in my lecture notes for discrete math and i saw these properties of floors and ceilings. are these just like math rules or is there an actual way of proving this? since the notes dont actually show any proof it just says: this equals this
faint narwhal
you can prove them
for example, you can define the floor of x as the unique integer n such that n <= x < n + 1
and then use this to prove these properties
sly fractal
is it possible that you can give me a simple example of this since the ones i see online are a bit convoluted
faint narwhal
An example of what?
sly fractal
for ⌊− x ⌋ = −⌈ x ⌉
runic thicket
for ⌊− x ⌋ = −⌈ x ⌉
e.g. let x = 0.5 so that ⌊− 0.5 ⌋ = -1 and −⌈ 0.5⌉ = - 1
sly fractal
right i can see that whenever i type and 'x' into symbolab but i dont think its sufficient proof in terms of words/explaining it out
faint narwhal
So the floor of x is the unique integer n such that n <= x < n + 1
and the ceiling of x is the unique integer n such that n-1 < x <= n
So if the ceiling of x is n, then we have that n - 1 < x <= n
which means that -n <= -x < -n + 1
and so by looking at the definition of floor, this means that the floor of -x is -n which is what we want to show
delicate hinge
is it possible to make an adjacency list on a directed graph with multiple edges?
faint narwhal
i think you mean an adjacency matrix? But yeah, you can just have numbers greater than 1
faint narwhal
what have you tried?
mint bane
ik it's gotta be strong induction but that's about it lol
stuck at that last step
it's 3 am where i am any help would be a godsend
faint narwhal
I think you might want to recalculate that product at the end
you still have an i in the last two lines, but i was the index of the product so doesn't really make sense
faint narwhal
also I'm not sure it should be an equals sign, you probably want a less than or equal sign when you remove the product
mint bane
theyre equivalent tho?
faint narwhal
uh, you're multiplying 2^(2^0) * 2^(2 ^ 1) * 2^(2^2) *... * 2^(2^(N-1)) so I'm not sure they're equal
mint bane
ok well regardless of that then, do you have any advice pls
i see how that's wrong tho
faint narwhal
you should analyze this product a bit more carefully
your bound right now isn't good enough
you want to use the fact that 1 + 2 + ... + n = n(n-1)/2 when you're adding up the exponents
mint bane
this feels like it's getting closer
bc i can separate those exponents but i'd still have the n-2/2
sorry for ping @faint narwhal but bro pls im so tired rn
mint bane
😔
faint narwhal
but you've used the exponent rules wrong here
so what you get is $$2^{2^0 + 2^1 + 2^2 + \cdots + 2^{N-1}} + 1$$ if you apply the exponent rules
vital dewBOT
Zopherus
mint bane
whoops
faint narwhal
so you can see that whats in the exponent is a geometric series and just use the formula for that
to see that the exponent is 2^{N} - 1
mint bane
you lost me at that last part
faint narwhal
do you see how that's a geometric series in the exponent
mint bane
yes
faint narwhal
so you can just the formula to sum geometric series
or there are a lot of other ways too
mint bane
remind me pls
faint narwhal
to see that $2^0 + 2^1 + \cdots + 2^{N-1} = 2^N - 1$
vital dewBOT
Zopherus
mint bane
ahhhhh ok lemme type it up one sec
this feels incomplete tho
@faint narwhal
appreciate the help btw <3
faint narwhal
you're not quite done yet
since this isn't exactly what you want to prove
also I had a typo in my earlier statement
should be 2^N - 1 rather than 2^N + 1 on the right
faint narwhal
write it out
mint bane
currently on a bathroom toilet w no pen/paper, long story lol
faint narwhal
$$\prod_{i = 1}^N 2^{2^{i-1}} + 1 = 2^{2^0 + 2^1 + \cdots + 2^{N-1}} + 1 = 2^{2^N - 1} + 1 \leq 2^{2^N}$$
vital dewBOT
Zopherus
mint bane
oh that's what you meant
faint narwhal
yeah, it's not too hard to see that the last inequality holds
mint bane
oh fuck i was staring at the picture i sent above where it was +1 and not -1
faint narwhal
yea sry
mint bane
no worries but that should be the end right
yeeeee haw, thank you @faint narwhal (pinged for karma but oh well)
can i bother u w one more question pls
mint bane
A convex shape is one which contains every point between any two points in its interior. Show that every convex n-gon can be divided into n-2 (that's a minus sign) triangles, each of which shares its vertices with the vertices of the n-gon. (Such a division is called a triangulation of the n-gon)
this fuckshit
ive definitely seen this somewhere
but idk where
faint narwhal
yea so think about how the induction would work
how can you get from an n-gon to a smaller polygon
mint bane
see that's the thing idk about this one, my prof told me i gotta go smaller but im used to going from small to big in induction proofs
if i remove a triangle that shares two vertices with the ngon
faint narwhal
what exactly do you mean by that
faint narwhal
yeah exactly
maybe it's more accurate to say that you're looking at the triangle formed by two adjacent edges of the n-gon
mint bane
fair enough yeah
faint narwhal
and then how do you use the induction from here
mint bane
hmmmmmm
well im assuming that an ngon can be divided into n-2 triangles
my confusion is that if i remove shit, wont i eventually get down to the base case
faint narwhal
if you continue removing shit yes
but you're assuming that an ngon can be divided into n-2 triangles
and you're trying to prove that an (n+1)gon can be divided into n - 1 triangles
mint bane
OHHHHHH
so if the n-1 gon has the triangles that implies the n+1 gon has the triangles by the inductive hypothesis
ok i get that step but now it's a matter of spreading it out i guess
faint narwhal
right
mint bane
wait does the n-1 gon make this strong induction then?
bc youd need to assume an n-1 gon can also be triangulated?
faint narwhal
I think you just miswrote what you said earlier
mint bane
wdym
faint narwhal
when you take an n-gon and remove a triangle like you described, you get an n-1 gon
mint bane
yes but dont we need to include the fact that an n-1 gon can be triangulated in our assumptions
mint bane
ok im overthinking nvm
almost done
Inductive Hypothesis: assume that every convex n-gon can be divided into $n-2$ triangles, each of which shares its vertices with the vertices of the n-gon. Thus, a convex ($n-1$)-gon can be divided into $n-3$ triangles. Using an ($n-1$)-gon, removing and edge and putting two in its place in such a way that the shape remains convex results in simply adding a triangle to the ($n-1$)-gon, in turn creating an ($n+1$)-gon. However, since this ($n+1$)-gon was created by the addition of a triangle to a shape that already had a triangulation, this new shape must also have a triangulation. Thus, the hypothesis is true.
vital dewBOT
nitezba
faint narwhal
You're overthinking a lot
faint narwhal
No
You want to show that for all (n+1)-gons, you can subdivide them into n-1 triangles
you don't know that all (n+1)-gons can be created by your process of adding a triangle to an (n-1)-gon
All you need to do is take an (n+1)-gon and cut off a triangle from it like you described earlier. This will give you a n-gon to which you can apply your inductive hypothesis to
mint bane
okok brb then
Inductive Hypothesis: assume that every convex n-gon can be divided into $n-2$ triangles, each of which shares its vertices with the vertices of the n-gon. Consider an $(n+1)$-gon. By removing a triangle formed by two adjacent edges of the $(n+1)$-gon, we are left with an n-gon. By the inductive hypothesis, the resulting n-gon must have a triangulation. Since the n-gon was created by the removal of a triangle, the $(n+1)$-gon must also have a triangulation. Thus, the hypothesis is true.
vital dewBOT
nitezba
faint narwhal
yeah
mint bane
i feel like drawings would help but im feeling lazy
in any case
thank you so much
i really appreciated this <3
glossy flume
recently did this problem in a discrete class
just basic inclusion-exclusion principle
how would you generalize this to an arbitrary bitstring length and an arbitrary number of 1s?
indigo glen
how would you generalize this to an arbitrary bitstring length and an arbitrary ...
For a size $n$ bitstring and $d$ number of ones, I believe it would be $2^n - 2^{n-d}\times(n-d+1)$
vital dewBOT
Ryan Leal
indigo glen
but i am a novice so take that lightly
oh nevermind you'd have to account for double counting and whatnot
tight lotus
what's your work for this one?
glossy flume
tight lotus
wow pain
glossy flume
there has to be a way to do this rigorously
tight lotus
once I figure out how tf to use TeXit I can show you a recursive thing that maybe you can play with
this might be useless
but we're effectively choosing the position of the *left-most* consecutive string of 1s to avoid over counting
then we allow all the bits to the right to be anything
the bits to the left are anything such that there isn't any consecutive string of 1s, hence the recursion
glossy flume
i think you want p to start at 1 (otherwise you end up with 121 instead of 120)
thorn axle
any tips on how to start this/ relevant theorems- im having a blank! (these are supposed to be warm up questions 😢
faint narwhal
Try simple cases, like when there's only one m
thorn axle
tyyy
glossy flume
i need to test this with different cases when im back home
but the recursion seems unnecessary right
tight lotus
i think you want p to start at 1 (otherwise you end up with 121 instead of 120)
Looks like there's a fundamental problem in that I did not consider the previous part of the string containing only part of the consecutive sequence that would then be "completed" by the current part
tight lotus
There's probably a non recursive way known to people who are more familiar with inclusion exclusion, which n choose k and stuff
glossy flume
yeah i think that would be cleaner
tight lotus
but I think recursion is probably inherently relevant bc the process of inclusion and exclusion can be applied in a divide-and-conquer style where you only look at two sets at a time
which smells recursive to me
if you do hear about a non recursive solution, I'd be interested to see it btw
carmine vine
is there a way to do the 2nd one without contradiction?
weary tiger
if you can do it with contradiction why do you care about doing it without
weary tiger
a constructive proof doesnt rlly make sense in this context though right
carmine vine
ah okay
tight lotus
it probably can
create a graph in a way that implicates it has at least two vertices of degree 1
then show that it's a tree with >= 2 verts
carmine vine
if i showed its contradictory for 2 vertices only thats not enough is it
weary tiger
wait what do you mean by that
carmine vine
ok hold on
the statement is Suppose that every tree with ≥ 2 vertices had less than two vertices of degree 1, right?
weary tiger
you can just assume it's false i.e there's a tree with less than 2 vertices of degree 1
and then show how that can't exist
tight lotus
the statement is Suppose that every tree with ≥ 2 vertices had less than two ver...
no, it has at least two vertices of degree 1
carmine vine
i mean when you are talking about contradiction
carmine vine
you can just assume it's false i.e there's a tree with less than 2 vertices of d...
like this
weary tiger
what you said isn't actually the same
carmine vine
if i changed the word every
weary tiger
but for a contradiction we want to assume a counter example exists
carmine vine
ooh
weary tiger
and then show how that leads to a contradiction
in this case a counter example is a tree without the property (so it has to have less than 2 vertices of degree 1)
carmine vine
the idea im getting is that there will be >= 2 leaves
weary tiger
yeh exactly
carmine vine
o
weary tiger
basically the idea is just showing how it contradicts the property that a tree has to be minimal
because you can remove edges
carmine vine
oh lol i dont quite recall some of the tree properties formally
weary tiger
(an alternate way to do it if you're allowed to use the fact that a tree of size n has n-1 vertices is using pigeonhole principle on the degree sequence)
So a tree is a minimal connected graph
carmine vine
ah okay
weary tiger
meaning that there exists a path from every vertex to every other vertex and you can't remove any edges without disconnecting it
weary tiger
f would be 1 in eulers and u shouldnt need eulers
weary tiger
eulers formula but you shouldnt need it especially if you haven't gone over it in class
it's probs later in your course
tight lotus
^
weary tiger
if you want the general idea though
take a vertex with the lowest order in the graph (that isn't 0) and just remove an edge
tight lotus
damb eulers formula makes this cheese
tight lotus
hm?
weary tiger
like this is kind of weaker than that e=n-1 for a tree
glossy flume
@tight lotus yeah it works for 5 and 3
weary tiger
A nice way imo though if we assume that e=n-1 is that
tight lotus
no that doesn't work either
kind of a rip but I don't have the energy to go back and fix it lol
ok I might have summoned the energy
I think the only new assumption I need to make is that the digit before p is a 0
glossy flume
so you would need to divide by 2 in those cases right
tight lotus
I tried putting in A(p - 1, k) but to no avail
Oh, that's roughly correct
but you have to account for the negative n values you would get
and just return 1
so for 7, 5 I get 120
glossy flume
5 3 should be 24
tight lotus
matches 24
glossy flume
but you have to account for the negative `n` values you would get
yeah just lower bound 0
wait whats your new function then
tight lotus
I don't have time to draw it with my touch screen 
hope you can read this
function A(n, k)
if n < 0 then
return 1
end
local current_sum = 0
for p = 0, n - k do
current_sum = current_sum + A(p - 1, k) * 2 ^ (n - p - k)
end
return 2 ^ n - current_sum
end
so it's just
p starts at 0 still
recursive call with p - 1 instead of p
but hopefully this can be rewritten to avoid the dumb negative n case
I just don't have time
minor lake
How many functions f : [12] -> [4] that are increasing?
weary tiger
can someone help me?
i know this is countably infinite
but idk how to prove it
it's just all integers for x values and the square of all integers for y coordinates
which should be countably infinite right?
weary tiger
Oh I think I get what ur saying
errant bear
u can just say its a subset of a countably inf set 
distant bobcat
Is the polynomial: $$ an^2 + bn + c $$ contained both in "big O" as well as in $$\theta $$? . I proved it is in "big O", but for theta I have to fulfill $$c_1 g(n) \leq f(n) \leq c_2g(n)$$ right? Choosing $$g(n) = n^2$$ for example Im not sure this works for both sides of the relation.
vital dewBOT
Fredrikpiano
unreal stump
Take c_1=a and c_2=(a+1)
Let n_0 be the smallest integer such bn_0+c <n_0^2
Then for all n>=n_0
c_1 n^2< f(n) <c_2 n^2
@distant bobcat
distant bobcat
Understood thanks! BTW it still fails to be in "little o" time complexity since dividing the polynomial as n ---> infinity by n^2 does not equal to 0?
last timber
@distant bobcat you can just see that there two polynoms (n^2) and (an^2+bn+c) are asymptotically equivalent
limpid estuary
Any algorithms experts here?🙄
minor lake
Can someone give me two examples of different combinatoric problems
I know that for instance if I have repetitions, I have to use bars and stars for encoding
however I totally how I would proceed to any sort of encoding in binary if there were no repetitions
errant bear
Any algorithms experts here?🙄
🙄✋
weary tiger
@minor lake how many increasing functions are there from {1,....,n} to {1,...,k}? (a) strictly increasing, (b) not-strictly increasing
(for strictly increasing assume k>=n)
minor lake
Hold on
switching laptop
@weary tiger ?
if you don't mind I'd like to ask you a question related to two specific examples that nearly look the same except one consider repetitions while the other one doesn't
minor lake
minor lake
"It is just that some binary strings won't correspond to outcomes of the type you are interested in."
Could someone clarify this
So like there isn't really any way the encoding would have a meaningful meaning if it wouldn't take in account repetitions?
I'm not sure if I really recall someone using binary strings- maybe in a different fashion- for combination without repetitions, maybe I'm just high
quaint pike
I have a complexity class
T(n) = 8n^4 + 2n^3 + log5n
I'm unsure which common complexity class the above function belongs to. I know it's log, but I'm unsure if it's "log n" class or "log 5n" class
vital dewBOT
quaint pike
It's n^4, that's the correct answer
balmy hornet
if you have an unsigned 4 bit integer, what is the largest value you can store? Would this be 1111 for binary and 15 for decimal?
weary tiger
yes? why do you doubt it?
weary tiger
hey
would someone be able to look over a few questions on my last exam?
i believe my professor is wrong
coral raven
weary tiger
#14 — i put ~p->r
#s 21 and 22:
ExEy(P(x,y)^~T(x,y))
ExEyT(x,y)
are these answers incorrect? if so, why?
weary tiger
#s 21 and 22:
ExEy(P(x,y)^~T(x,y))
ExEyT(x,y)
post an image of this instead
really hard to read
one sec
@weary tiger
my explanation as to why his #14 is wrong
weary tiger
14 might be wrong, have someone check it (i'm not great at discrete)
yeah I was about to say 14 looks incorrect
he didn’t post solutions for 21 or 22
mine was ~p—>r
14 is sorta tough but I'm pretty sure that's not the right answer like you say
if it did not rain, then we went
There are different ways to "phrase" it or equivalent expressions
i believe
yeah
well his 14 is straight incorrect because he thinks that
"if we do not go to the park then it will not rain" which is absurd
I think it's trying to say more so
"p -> ~r"
but double check
p->~r is the inverse of my solution
yeah it's equivalent i think
yeah
he took 10 points off my test bc i didn’t see the back page lol
i asked him if we only had 2 proofs before i submitted my exam
he said yes
there were 4
weary tiger
#s 21 and 22:
ExEy(P(x,y)^~T(x,y))
ExEyT(x,y)
21 I'm not sure ExEy is what we want here.
Maybe Ex in the set of all pres s.t. P(x,t) ^ ~T(x,t)
t = texas ? again double check with someone else