discrete-math

[weary tiger]

<I do not know how to solve recurrences or anything related to them, I just followed another example I found online>
I get

[vital dew]

yika

[unreal stump]

It doesn't work that way

[obtuse lance]

not quite your second term is off

also your last term is off too

[stray reef]

#help-21｜아리스킨충1 if y'all want to continue

[weary tiger]

o ok. Thanks time to learn recurrences

[weary tiger]

yeah it should be 4. I mistyped. Not sure about what the second is supposed to be! Ann's solution looks the same Totally not!. Oh th Cn term. Alright

[obtuse lance]

check out the channel Ann linked you might learn from there what to do

[stone wing]

This is a problem from the textbook Graphs and Digraphs by Chartrand and Zhang. I would like to know if my attempt for this problem is valid and if anyone has any suggestions for a better proof.

[weary tiger]

Sure DM me

[ruby torrent]

A friend of mine sent this to me - it's the "solution" to a previous exam problem

I'm not mad right? "algebraic fact" is straight up false, and the solution is objectively wrong

Note that, I haven't taken a course in graph theory, but I've pieced together bits (so please be gentle)

[obtuse lance]

oh do you have a counterexample

[ruby torrent]

Yes

[obtuse lance]

I mean the algebraic fact

like a,b,t

[ruby torrent]

Lemme think

without doing the workings pretty sure Lagrange multipliers shows a = b = t/2 gives the minimum

For an explicit example though I believe a = 1, b = 5, t = 6 works:
1+5≤6
1²+5²=26
but 6²/2 = 18

[vale cairn]

I like how the algebraic fact is neither a fact nor algebraic

[obtuse lance]

wild, yeah a=0, b=1, t=1 gives 0+1<=1 and 0^2+1^2 <= 1^2/2 is mega false as well

[sudden minnow]

yeah LMAO

[ruby torrent]

if you're confident enough, anything's a fact

[obtuse lance]

is there some kind of way to make it right though, like this is some kind of typo

[vale cairn]

yes

[obtuse lance]

like in the solution they use the "right" form or something

[ruby torrent]

The first example I gave contradicts their solution I believe

[vale cairn]

Wait hm

[obtuse lance]

oh ok, I'm gonna go eat, but I believe you

can't wait to read what you all come up with whenI return

[vale cairn]

I wonder what the optimal bound on a^2 + b^2 is

[ruby torrent]

a = 0, b = t me thinks

well

a > 0 sorta makes this wrong, but call it epsilon

but still

[vale cairn]

Wait yeah like a^2 + b^2 >= (a+b)^2/2 by RMS-AM right lol

So their thing is almost the opposite of what we want ig

[ruby torrent]

I think their typo is the fact they meant "minimum" instead of maximum

[ruby torrent]

But yeah, the lower graph has 5 vertices and a critical point (remove the bottom middle vertex, and you get two components)
moreover this graph has 7 vertices

but the upperbound in the provided solution is (5^2 - 1)/4 = 6

[weary tiger]

#discrete-math guys tomorrow is my exam can anyone help?

[stray reef]

writing the name of a channel does not ping anyone, if that was your intention.

[stray reef]

how do you suppose we should help you?

[weary tiger]

can you solve all

[stray reef]

no.

in fact, given how long the PDF you sent is, it's even more of a no than it would've been with a single problem.

we don't do your homework for you, or anything similar to it.

[weary tiger]

ok sorry

[zinc kettle]

i realised that supremum $\neq$ greatest element so i ask the same question again

[vital dew]

ta

[brave rock]

There are no upper bounds at all, so there is no supremum (least upper bound)

[zinc kettle]

so if my poset is ({2,3}, | ) there's no supremum at all. but if my poset is ({2,3,6}, | ) sup {2,3} = 6?

[brave rock]

Yeah that's correct

It should be noted that we usually take the supremum of a subset of a poset.

So e.g. if your poset is ({2,3,6}, |) then the supremum of {2,3} is 6.

N.b. that 6 is not contained in the set {2,3}, but it is the least upper bound of {2,3} in the poset.

(I edited this message a couple of times for clarity; my apologies)

[zinc kettle]

ok that makes sense thanks !

[brave rock]

No worries

[zinc kettle]

no worries i do it too

[brave rock]

Just runs the risk of confusion

[zinc kettle]

seems correct

im not a pro tho

[blazing plaza]

tired of studying and my brain can't contain, can someone help me with my last question would make my day

[coral parcel]

Depends on exactly what you consider a "way" to arrange the keys. If you take the keyring and turn it around so a different key is at the top (but they're otherwise in the same sequence), is it a different way that you want to count separately? If you flip the entire keyring over so the sequence is now the reverse of what it was before, is that a different way that you want to count separately? If you take a single key off the ring and put it back in at the same place after flipping the key 180° so the teeth point in to the other side of the ring, is that a different way?
Thinking about these questions will probably lead you to conclude you're overcounting some arrangements.

[blazing plaza]

anyone?

[obtuse lance]

try making just a string of length 5 that's in R, don't worry about S right now

[blazing plaza]

abaaa

can you tell me another one?

[obtuse lance]

I don't know what + is here, some kind of OR? I don't want to assume it means "at least one of"

[coral parcel]

It seems to be two regular expressions with + representing the union of two languages.

[blazing plaza]

yh its regular expressions

[coral parcel]

One of the four questions looks impossible to me, by the way.

[blazing plaza]

first one i answered: abaab

[blazing plaza]

which one? i also got hella confused with it

[obtuse lance]

are you saying the spacing around this middle + (red) is union and the other two + (blue) mean at least one of?

I'm just trying to clarify what convention is being used here first

[blazing plaza]

• means union operator

[coral parcel]

I'm pretty sure the spacing is not significant.

[blazing plaza]

yh spacing doesn't mean anything

[blazing plaza]

or aabba

[coral parcel]

A crucial fact as I see it is that the language R can be written much simpler ...

[blazing plaza]

teachers love to make everything complicated

[blazing plaza]

is there any of the questions, you found an answer for?

[obtuse lance]

number 2 lol

[coral parcel]

Hmm, actually I can now see what Merosity was suggesting, if a plus without spacing means "at least one repetition of the previous expression" like + does in computer regexes, then R could be what computer notation would write (aa+b*|b+a*)*. But that would be a really perverse notation convention.

[obtuse lance]

something is messed up

[coral parcel]

(When you said "at least one of" I initially understood it as "at least one of these two", which was confusing).

[obtuse lance]

yeah sorry I forget what it's called, it's like the kleene's star but "plus one" I don't recall if it has a name

[coral parcel]

I don't immediately remember a fancy name for it either.

[blazing plaza]

that regular expression is bit long and has too many repeating thats what it makes it confusing it lol

[blazing plaza]

i found: abbab is that correct?

[coral parcel]

Leading question: Can you find anything that is not in R?

[blazing plaza]

abbab is not in R i guess

what else cant be in R but length has to be 5

[coral parcel]

Why not?

R = (something + b* + something + a*)*

[blazing plaza]

what can be in both tho

thats what i cant think of

[obtuse lance]

maybe pretend you're a finite state machine and you're looking at 'a', is that allowed to be picked for your first letter?

[blazing plaza]

i can't think of one

aabba?

[coral parcel]

Didn't you already answer that for the intersection?

Hmm, I don't think aabba is in S, though -- how would it be?

[blazing plaza]

I actually don’t know, just tried think of one on my head

It’s already late 00:07 my brain ain’t working 😂

[coral parcel]

Can you explain how you thought this? Reading back, I find nothing that really reassures me that you know how regular expressions work in general.

[blazing plaza]

R start with aa and S has a*—> which means one or more so I thought bout something starting with aa

And ik regular expressions, this one is confusing one

[haughty garden]

aabba doesn’t belong in S since you’d need to have two a’s at the end of the string you have rn

One way to do this systematically is to construct two DFAs that correspond to R and S respectively, and then simulate on both DFAs simultaneously

This gives you the intersection of two languages known as the “product automaton”

[dusk beacon]

Got a question,does anyone know why d'allenberts ratio test fails if l=1

I can't understand why it would be inconclusive

[stray reef]

@dusk beacon there exist both convergent and divergent series which give L=1 when the ratio test is applied to them

for example \sum 1/n and \sum 1/n^2

[dusk beacon]

Is it a geometric one?

[dusk beacon]

Is it because it be would both convergent and divergent?

[stray reef]

no, neither of the two series i gave are geometric.

[stray reef]

bad wording, but i suppose that i can say yes.

the reason the test is inconclusive is that, with L = 1, you cannot distinguish a convergent series from a divergent series.

[dusk beacon]

Hmm I want to look more into this

Anything I should look out for specifically?

[blazing plaza]

How about one that belongs to S and R ? can’t think of one

[blazing plaza]

For this question

[haughty garden]

Strings in R are pretty unrestricted so you probably want to consider strings in S. Note that, in R, you can generate any string of as or bs

[blazing plaza]

aabba, would this be in both?

can you give me another example another string that could be in S and R

[haughty garden]

aabba doesn't belong in S

one string that belongs in S is abbaa. See if this belongs in R

[blazing plaza]

I can’t think of any other string length five 😪

[weary tiger]

Anyone has a good online class/lectures that goes through most of Discrete Math by K. Rosen ?

[fringe siren]

how can one prove that in an finite undirected graph from every vertex with odd degree there exists a path to to another vertex with odd degree?

[rapid mural]

go by contradiction

[fringe siren]

i don't know how to prove it by contradiction. i mean my idea was to prove it by induction depending on the number of vertices but it didnt work. im not confident doing proofs

[little prism]

you can clearly go to some vertex. if that vertex has odd degree then you are done. what if this vertex has even degree. can you go further?

[fringe siren]

No, because there will be a cycle?

[little prism]

cycle where

[fringe siren]

in the path? i'm not sure i understand the purpose of the question

[little prism]

ok so you mean that you get to some vertex with even degree that you were previously already

I assume

can you ever be "stuck" in such a vertex. how many times did you "enter" the vertex and how often did you "leave" it

[fringe siren]

no, because we can "leave" it if the degree is even because an euler path exists? and if all vertices are even there is euler cycle

am i right?

[little prism]

well this is connected to euler paths but one of those doesn't necessarily have to exist

but it's the same idea, yes

and so we can always leave a vertex with even degree

so do we have to end somewhere? where

and in the end we can "cut off" all the cycles we went along the way

[fringe siren]

if there is a vertex with odd degree there must be another one

in order to connect the edge leaving from the vertex with something

[little prism]

cough cough handshake lemma

[fringe siren]

omg yes, i forgot about it. hmm let me think how we can prove it more farmally

[little prism]

how is the handshake lemma not formal

[fringe siren]

no, i mean i will try to peace together the proof of the question

is this proof legit? I mean will it be accepted on an exam?

[little prism]

yes definitely

[fringe siren]

thank you

Prove that in an finite undirected graph every path with odd length, for which the beginning and the end of it match, contains a simple cycle.
For this, will the proof be similar to the previous one?

[fringe siren]

What i came up with is this:
path for which the beginning and the end of it match => it is a cycle
|simple cycle| = the number of vertices forming the cycle.
the degree of the vertices must be even. If there is a V with odd deg then the path doesn't fulfill the requirement for the beginning and end of it to match

but i don't know how to write this proof

am i correct tho?

[coral parcel]

I would assume "simple cycle" means "cycle that doesn't repeat any vertex except for beginning=end".

[fringe siren]

yes

[coral parcel]

Hmm, I'm afraid I don't get much sense from your proof attempt at all.

(It also looks to me like the assumptions that the graph is finite, and that the original path has odd length are both superfluous).

[fringe siren]

they may be. There is a follow-up to the question: Is the statement true when the length of the path is even?

[fringe siren]

make sense. i'm just saying what i think and see so i may be wrong

[coral parcel]

Your argument for "the degree of the vertices must be even" sounds like you're confusing the original path with an Eulerian path (which would be required to use all edges).

[fringe siren]

yeah, now when i read it again i can't find the reasoning for the argument

[fringe siren]

then how can we prove the statement?

[coral parcel]

I'd suggest long induction on the length of the original path.

[fringe siren]

what is the difference between induction and long induction?

[coral parcel]

In ordinary mathematical inducton, you assume that the propery holds for n-1 and prove it holds for n.
In long induction you assume it is true for all smaller n and prove it folds for n.

[low gate]

Help please, Ex. 8

[coral parcel]

There's an example of this in your own very picture.

[fringe siren]

Suppose there is a tree with 4042 vertices, in which there is exactly one vertex with degree of 2 and the number of of the vertices with degree 1 is 2021. Does such a tree exists?

i dont know how to solve this problem

[coral parcel]

So the sum of the degrees must be at least 2021·1 + 1·2 + 2020·3.

How many edges does a tree with 4042 vertices have?

[fringe siren]

maybe we can work with the parity of the vertices?

[fringe siren]

4041

[coral parcel]

And then what is the sum of the degrees of all vertices?

[fringe siren]

lol i got confused for a moment

the sum of the degrees of all vertices is 2.4041 = 8082

am i right?

[stray reef]

indeed

[fringe siren]

and from here we get that the minimum sum of degrees should be 8083.
but the actual sum is 8082

so such a treee does not exist

[stray reef]

indeed it does not

[fringe siren]

thanks for the guidance

[stray reef]

Number of edges,
Sum of vertices' degrees:
One-two ratio.

[fringe siren]

Let X ⊆ A и |X| = k. Find the number of the idempotent functions
f : A → A, for which X = {x ∈ A|f(x) = x}.

how can we solve this? I don't know how to start

as far as i know idempotent function means f ◦ f = f, aka f(f(x)) = f(x)

[coral parcel]

In other words the output of f is always a fixed point.

And it's specified that the fixed points are exactly X.

[blazing plaza]

Can someone help me with question 1?

who has right Will this be p ---> q or q ---> p

i said q ----> p

[sudden minnow]

the first statement is a biconditional

[blazing plaza]

its implication

we use only if only something like that for biconditional

[sudden minnow]

it literally says only if

[blazing plaza]

the implication can be described in different ways one of them is only if

[sudden minnow]

okay then I guess I've never seen an if statement like this before

[blazing plaza]

biconditional would be p if and only if q

[coral parcel]

But it doesn't say "if and only if"

[sudden minnow]

yeah I get it

[blazing plaza]

translating the statement symbollically, its p --> q right?

[coral parcel]

So I agree wih "canceled -> rain", and the reasoning in the second line is invalid.

[sudden minnow]

taking this at face value, the q here would be the part about raining

[blazing plaza]

the statement doesn't look invalid tho

[sudden minnow]

but the statement doesn't say this, right?

[coral parcel]

The first line doesn't say the game must be cancelled in case of rain. It says rain is the only case where the umpire is allowed to cancel it, but he doesn't have to.

[sudden minnow]

if I understand correctly, the statement asserts "raining" as a necessary condition for cancellation, not a sufficient one

[blazing plaza]

i guess raining should be the only reason the game should be cancelled

[coral parcel]

This is not necessarily the only possible natural-language meaning of "only if", but it is without any doubt always the meaning of "only if" in mathematics.

[blazing plaza]

so the statement is invalid?

looking at that truth table, its making me more confusing tbh

[sudden minnow]

the sentence that starts with it rained should be wrong yes

[blazing plaza]

but the other one if it rains football game will be cancelled is ok?

[sudden minnow]

I mean, ok in what sense?

[blazing plaza]

valid argument

[sudden minnow]

we can't judge it as true or false, it is an assertion

and the 2nd statement is invalid, assuming it was deduced from the first

[sudden minnow]

okay wait, is this given beforehand?

I am confused as to the nature of your question now

[blazing plaza]

i need to translate the statement to a symbolic form

idk which now i am lost haha

[sudden minnow]

the first statement?

[blazing plaza]

then determine if its valid or invalid

[blazing plaza]

whole thing

[sudden minnow]

okay I see now

so the first statement asserts q -> p

then it says p

therefore q

so it is invalid as an argument

[blazing plaza]

i was writing it

[sudden minnow]

yeah that is right

[blazing plaza]

and its invalid?

[sudden minnow]

what do you think

[blazing plaza]

yh sounds invalid also looking at the truth table

thanks sm, i appriciate the help

[sudden minnow]

if I am at least 2 meters tall, then I am at least 1 meter tall

I am 1 meter tall, therefore I am 2 meters tall

same fallacy

[blazing plaza]

i understand know, first i didn't know which statement i had to translate lol

one last question

[blazing plaza]

is first question, impossible to find?

everyone saying it doesn't exsist

[sudden minnow]

never seen this topic before so 🤷

[blazing plaza]

its regular expression

[weary tiger]

\begin{tabular}{|c|c|c|c|}
\hline
p& q& p $\implies$ q& $\neg$ p \hphantom{y}${\wedge}$ (p $\implies$ q) \
\hline
T& T& T& F \
\hline
T& F& F& F \
\hline
F& T& T& T \
\hline
F& F& T& T \
\hline
\end{tabular}

this is right,right?

[vital dew]

♡Lex♡

[sudden minnow]

sure

[fringe siren]

so the number of these functions is k^|A|?

[stray reef]

k^|A\X| surely?

you're already told exactly what every function in your class does to points in X

[fringe siren]

why do we remove the |X| from |A|?

the number of all idempotent functions f : A → A is k^|A| right?

[chrome fossil]

It’s a union

[coral parcel]

As Ann said, you're told exactly what every function in your class does to points in X. There are no choices to make for them.

[errant sparrow]

I have an 8-vertex graph, ring around the outside, 4 edges across the middle (Wagner graph according to the interwebs). K_{3,3} with two extra edges. If I'm not mistaken, this still forms a partite graph, but {3,3,2}. I would like to show that the 8-vertex graph is non-planar by showing it has an embedding of K_{3,3}. I can draw K_{3,3} with 3 vertices in one set and {1, 2, 2} vertices in the other. Two pairs of vertices need to be combined into edge sets. I'm not sure if this sort of reduction is valid or allowed in this context. If you number the Wagner graph vertices 0-7, my embedding becomes {0, 2, 5} and {1, {7, 6}, {4, 3}}. Any pointers are greatly appreciated.

Oh, I just found it in a different book. I guess this is called a graph minor. 🤔

[tawdry night]

Hi, I want to ask question about euler circuit . Does anyone know why deg( ) need to used?

[errant sparrow]

I believe it is because of the theorem "A graph is Eulerian iff the degree of each vertex is even."

[tawdry night]

Except deg(), can I use others like deh() , ghj() ti instead of the deg() ?

[coral parcel]

"deg" here is an abbreviation of the word "degree". Its meaning has nothing to do with the vertices named d, e, and g.

[tawdry night]

Ohhh I see

Thanks I get it

[tawdry night]

Why abcda isn't the euler circuit?

[coral parcel]

It fails to contain the edge fh.

(And many other edges too; I chose fh at random).

[tawdry night]

Are all lines contain defghij to be considered as euler circuit?

[coral parcel]

Perhaps you need to go back and look at the definition of what "Euler circuit" means.

[zinc kettle]

if there is aleph 0, aleph 1 etc. is there aleph aleph

it must be the ultimate biggest infinity then right

[coral parcel]

Not really.

The subscript to the aleph must be an ordinal number (this includes all the natural numbers and a huge infinity of transfinite ordinals).
But "aleph" by itself is not the name of any ordinal number.

(Unless you adhere both to the very rare convention that "aleph" by itself means the cardinality of the real numbers, and to the common set-theoretic conventions of representing cardinals by initial ordinals).

(In that case $\aleph_\aleph$ -- or in more common notation $\aleph_{\mathfrak{c}}$ -- would be the name of an infinite cardinal. But by no means the "ultimate biggest" one; $\aleph_{\mathfrak{c} +_o 1}$ would be larger.)

[vital dew]

Troposphere

[sudden minnow]

it is one of the first thing you learn about cardinals that there is no biggest one

because you can always take its power set and get something bigger

[chrome fossil]

What’s the number of ways to write a positive integer n as a sum of distinct positive integers (swapping order counts as the same case)

[haughty garden]

you might be interested in the partition function, which returns the number of possible partitions of a non-negative n. There isn't a closed form for it atm but you could generate an algorithm that returns it for certain values of n

[chrome fossil]

Thanks

[zinc kettle]

what does o_1 even mean

i thought that c + 1 = c

[sudden minnow]

that is +_o, meant to indicate ordinal addition

[sudden minnow]

not for ordinals

[weary tiger]

i need helpp

guys

algebra 1

[sudden minnow]

#prealg-and-algebra #prealg-and-algebra

#❓how-to-get-help

[spiral aspen]

I dont understand what this observation is trying to say

the example they gavet

[stray reef]

what's delta(W)?

[haughty garden]

The idea is that, if you always require at least one edge to separate any vertex from another vertex, then the original graph must have been connected. The only way for you to ever have a disconnected graph in the first place is if some cut of the graph doesn’t have any edges at all because, well, it is already disconnected

That’s why it’s important to have that for all component at the end

If W were to be some empty induced cut, then there must have been some vertex that was already disconnected from another vertex. So your graph is disconnected

[spiral aspen]

so in the image provided above its trying to say the subset W is connected because for each vertex in it we can find an outside edge?

[haughty garden]

It’s just saying that, if you remove the edges that are inside the circled parts, you can always find edges outside of the circled bit that still joins the vertices of W

Specifically, the blue lines

[spiral aspen]

ahh.. is this also stated in the Observation?

[haughty garden]

That’s what the observation is saying

If G were to be connected, then no matter what subset of vertices you choose, you can always find edges outside of delta(W) that still end up connecting the vertices in W

And the converse holds too

The black lines are the edges in delta(W) and the blue lines are the edges outside of delta(W) that makes the vertices in W still reachable from some other vertex in G

[spiral aspen]

ohhh so delta(W) = the edges inside the circle (the black lines). Misunderstood that previously. E is all edges in G so the intersection of delta(W) and E are the black lines (only the ones in the red circle) correct?

(only given that example image since it does say "for all W")

[haughty garden]

Oh I misinterpreted the definition

Sorry the blue lines are delta(W)

You require edges such that one vertex is in W and one is in V \ W

But I believe the idea still remains the same

[haughty garden]

In this case, it would be the blue lines. My bad

[spiral aspen]

ok so just given the image
delta(W) intersection E are only the blue lines right?

[haughty garden]

Yup

[spiral aspen]

and by for all W subset V they mean we do this for all possible proper subsets

and this would imply its connected

[haughty garden]

Yeah

This seems to have links to the maximum flow and minimum cut

But yeah it might be useful to think about this result on a disconnected graph

[spiral aspen]

yeah they are heading there

[haughty garden]

Ah neato

[spiral aspen]

this is the proof they gave. I still dont really understand how they used the delta(w) intersection E to prove V=W

[haughty garden]

What happens if v is not reachable from w?

[spiral aspen]

it wont be connected

[haughty garden]

mhm

But what does that mean for delta(W)?

[spiral aspen]

ohhh! its gonna be empty

[haughty garden]

Right!

[spiral aspen]

ok i got it now

thank u!

[haughty garden]

nws!

[spiral aspen]

im not sure i understand what they mean by this sum

are they saying the sum only applies for vertices with degree higher than 2?

if that is the case, then is it not incorrect? I mean if i have 4 nodes each connected by 1 edge then ill have 4 pendant nodes

but the answer will be 2 based on what they gave

[stray reef]

yes

[stray reef]

4 nodes each connected by 1 edge? that won't be a tree.

[spiral aspen]

sorry 4 nodes 4 edges

4 nodes 3 edges

[stray reef]

draw the graph you have in mind

[spiral aspen]

nvm. I do see it now i apologize. Regarding the proof I am assuming the correct approach would be by induction right?

[stray reef]

induction...? sure, that could work perhaps

[spiral aspen]

alright will give it a try. thanks

[spiral aspen]

i tried a different approach but i am not able to solve it
my attempt:
there must always exist at least 2 nodes with degree 1 in a connected graph
case 1: if for all other nodes d(v) = 2 then the tree is linear and we know the condition is satisfied (since the sum is 0 and only the start and end node have degree 1)
case 2: there exists a vertex v in V with d(V) > 2

case 2 is my problem.

[haughty garden]

Since $T$ is a tree with $n$ vertices, there are $n - 1$ edges. So the {\em total} sum of the degrees of the vertices is $2n - 2$. That is, [ \sum_{v \in V} d(v) = 2n - 2.] Now, let $P$ be the number of pendant vertices. Then we break the sum we had above into three parts: a sum over degrees of 1, a sum over degrees of 2, and a sum over degrees of 3 or more.

[haughty garden]

To finish the proof, we can label the vertices from $v_1$ to $v_n$ so that it’s easy to see that [\sum_{i = 1}^n (d(v_i) - 2) = -2.] Then breaking up the sum into three parts as mentioned, the pendant vertices contribute $-1$ to the sum, vertices of degree 2 contribute 0 to the sum. Letting $P$ be the number of pendant vertices, we get [-2 = \sum_{i = 1}^n (d(v_i) - 2) = \underbrace{\sum_{i : d(v_i) = 1} (-1)}{-P} + \sum{i : d(v_i) = 2} 0 + \sum_{i : d(v_i) \geq 3} (d(v_i) - 2)] and the result follows from a bit of algebra.

[mortal crane]

Is there an algorithm for finding Hamiltonian cycles specific to Knödel graphs which is more efficient than the usual backtracking approach?

[frigid wave]

can someone help me with this?

is for a homework i have to send in 40 mins, and i cant manage to do it

[sudden minnow]

you take k of 1/2

20-k of -1/3

end up with 5

[main berry]

hey guys, just a quick question for the solution , why, according to the definition of m-i, that m-i+1 must be in a new block of the function?

I have read the text on the parts about set partition all over but I can't really find a explanation about this fact

[sudden minnow]

it's literally the definition

read the second sentence

let m-i be...

[main berry]

Why m-i and m-i+1 can't be in a same block

[sudden minnow]

okay that [i] might be meant to be [m-i]? then again I haven't studied partitions myself yet

so I might be misunderstanding stuff, don't wanna try correcting the author here

[main berry]

no worries!

[regal gate]

how many permutations of ABCDEFGH that fix exactly 4 letters are there? The anser should be binom(8 ,4)*9 right?

I'm tired and need a sanity check lol

uh lol

thats wrong

[main berry]

from my understanding, s(m-i,n-1) is a way to decide the blocks, but shouldn't there be n^i ways to assign the numbers though?

[regal gate]

edited. Is this right?

[sudden minnow]

it should be right

[regal gate]

Wtdym "should"

[sudden minnow]

8 choose 4 ways to decide which ones to fix, and there are 9 permutations of 4 that don't fix anything

[regal gate]

Yeah

So I was skeptical because I got that type of question wrong once long ago and now I was tired

@sudden minnow are you into combinatorics?

[haughty garden]

Combinatorics is a fairly broad topic that encompasses a lot of major subfields

[regal gate]

Ok?

[sudden minnow]

not at all

[sudden minnow]

this might give you a clue of how much I know about combinatorics

I'm taking a course on it this term though, so we will see

[regal gate]

Ah ok

[main berry]

hope you'd like the class

[sudden minnow]

same

[haughty garden]

it’s a very fun area of math

[reef juniper]

can anyone give me some pointers

my techer told me start off with 5%7 = 40%7

teacher

[brave rock]

I'd say your teacher gave you a good pointer

[reef juniper]

@brave rock what I'm currently think is that:

5%7 = 40%7
Therefore, 5 is congruent to 40 (mod 7)

Since 5 is congruent to 40 (mod 7)

5^k is congruent to 40^k (mod 7)

am i in the right direction? I don't know how to oprogress

[haughty garden]

That’s a start

Using that fact, try and simplify 5^n + 6 * 40^n, knowing that 5^n and 40^n reduce to the same modulo 7

[reef juniper]

can i say 5^n - 40^n = 7k?

[reef juniper]

where does the 6 go?

[haughty garden]

Consider the expression modulo 7. Since 5^n = 40^n in modulo 7, then you can write the expression as 5^n + 6 * 5^n (mod 7)

It should be easy to see that this reduces to 0 (mod 7) for any n

[reef juniper]

@haughty garden thanks!!

[hollow swallow]

Is discrete math just a set of select topics from other math subjects? I'm looking at a discrete math book and I just see things about probability, number theory, set theory, etc. And those are things that I either have already studied or am going to study in their respective subjects. Is there a reason to read a discrete math book in this case?

[little prism]

Discrete maths is a very wide topic which generally treats things that are finite or countable. So probabilities with stuff like dice rolls etc could be included cause that's mostly just counting how many events fit etc which is essentially combinatorics. Also for a lot of people a discrete math course is essentially an intro to proofs so it's also often the case that some number theory or set theory is included for that purpose

[hollow swallow]

So if I already know the things that are usually studied in discrete math I don't need to use a discrete math book for example?

If I study probability, graph theory, number theory, etc separately I mean

[wicked bolt]

i'd say yea, you can skip out on things labelled 'discrete math'

you could always skim through a book if you want to see 🙂

[hollow swallow]

I'm going to study the subjects separately instead of using a discrete math book. But I'm still going to skim through my discrete math book of choice because it seems to have interesting applications to computer science, and the books for the pure subjects don't

[wet flame]

Let (V,E) be a directed tree with root r. If $(r,v) \in E$ , then $V,E \backslash {(r,v)} \cup {(v,r)}$ is also a directed tree

[vital dew]

yotta

[wet flame]

is this false?

because there is no longer a root node with a path to every vertex

so no longer a directed tree

[warped storm]

Hey folks, I'm trying to convert NAND gates to other elementary gates such as And, Or, etc. Can I use boolean algebra and the boolean laws to convert Nand expressions to the pre-mentioned gates?

[crimson salmon]

There are several ways to do this mate . Since NAND gate is a universal gate you can use different combinationtions to derive any gate . It would be better if you post some question ,so i can narrate in details

[warped storm]

Thanks! I'm doing a project where I need to create about 15 gates using the NAND gate so I don't have a specific question at the moment. Though my struggle is I'm not sure what the best way is to figure out in what way I should use Nand gates to create for example an XOR gate.

How would you go about with creating an XOR gate from NAND gates? Would you write it out as a boolean expression (is that possible to use as a technique for deriving gates?)

[crimson salmon]

yes

let me oslve one for you step by step

Give me a moment please

[warped storm]

awesome thanks @crimson salmon

[crimson salmon]

@warped storm

Let me know mate if you have any query in understading

[warped storm]

hmm, which boolean law did you use on the 3rd expression?

[crimson salmon]

Third expression is double negation law followed by Demorgans law

[warped storm]

ohh okay

[regal gate]

Full solution:

Can someone help me understand this solution? I don't understand where ||the inequality 4k>3·2007|| comes from

[regal gate]

Like I don't understand his argument, so annoying. I could figure out the solution in seconds after seeing the problem but idk what he is doing.

[spiral aspen]

So discrete math is a topic i find more difficult than the other math topics ive done. Even if I understand the lectures whenever it comes to solving exercises I get stuck. How would you guys suggest I improve on this? (Currently doing graph theory if relevant) And how long should I spend on a problem before giving up and checking the solution?

[elder berry]

||4k is the number of tuples used by the k vertices|| - this is because the 4-tuples of consecutive vertices which vertex 'j' is a part of are
(j-3, j-2, j-1, j), (j-2, j-1, j, j+1), ..., (j, j+1, j+2, j+3)
[modulo 2007];

On the other hand
||3 * 2007 is the number of 4-tuples (2007) appearing only 3 times|| - this is the theoretical absolute maximum number of tuples you could have that does not satisfy the property that there is a 4-tuple of consecutive vertices.
(To have four consecutive vertices appear, you must have counted that 4-tuple four times, one time for each vertex.)
If you had ||3 * 2007 + 1|| number of tuples, by pigeonhole you must have 4 consecutive vertices.

||The obtained inequality on its own is not enough to show it is the minimum. You also must show there exists a construction where 1505 vertices fails this condition. I was surprised that the inequality is quite strong||

In case it wasn't obvious, there are indeed only 2007 4-tuples of consecutive integers and those are (1, 2, 3, 4), (2, 3, 4, 5), ..., (2007, 1, 2, 3)

[regal gate]

Oh no that is obvious

I didnt understand the 3x2007 thing

||Like I jus partitioned 2007 into 501 disjoint subsets of 4, each of four consecutive integers, and a subset of 3 consecutive integers, then its clear.||

[elder berry]

Yup, that was my first idea too

[fringe siren]

If we have a boolean function f that is self-dual and monotonous doest it keep the constants 0 and 1?

Aka
f∈S ^ f∈M => f∈T0 ^ f∈T1

[snow cedar]

hey does anyone have any tips for how to approach this problem?

for combinatorics

[haughty garden]

Start by distributing 1 pencil to Ahmed and Dieter, and 4 pencils to Barbara

You can now reduce this problem into placing r identical objects into k distinct boxes with one restriction

[snow cedar]

so, i can imagine 25 pencils, in between those pencils are 24 gaps

for Barbara I can either choose the 4th gap, or any gap after that (to allocate at least 4)

but im not sure how to work with this hand in hand with casper not receiving more than five pencils

here is a similar example we did

[sinful steeple]

Does anyone happen to know game theory here?

[weary tiger]

https://tenor.com/view/matpat-matthew-patrick-hey-theory-just-a-theory-gif-5669015

[sinful steeple]

So is that a yes?

[weary tiger]

No sorry

I'm just getting started with discrete maths coz people think it's unimportant for some reason

[snow cedar]

anyone have advice

[knotty cape]

Do what Opengangs said. Then give 5 more pencils to Casper; then solve the problem as you normally do. This would be all the unwanted cases. Subtract that from all the possible cases (assuming they all still have at least one). I believe this should do it.

[spiral aspen]

i dont really understand what the backward node created in a residual graph is supposed to mean

so basically if u -> v is 3/5 (flow 3 max 5)
what would a u <- v of 3 mean?

how would i "undo" it if an edge from v to u doesnt actually exist

[spiral aspen]

also what is meant by this lemma?

[pale epoch]

the residual capacity encodes how much flow can possibly change in a given direction

so the backwards edge in your example encodes that you can undo the 3 flow in direction u -> v

this lemma ensures that ford fulkerson works

i.e. you can maximize flow by finding an augmenting path in the residual graph

you need some connection between flows in a graph and the residual graph, otherwise introducing residual graphs would be useless

no idea if this is helpful @spiral aspen

[haughty garden]

It might be useful to think about why the residual graph was even invented in the first place. Consider an s-t augmenting path (or flow if you want to think of it this way). You want an operation that can push flow backwards in the case where we hit a dead end and no further s-t paths can be found (this is called a blocking flow). One way to do this is to “undo” our current flow path by figuring out how much flow is pushed forwards and backwards.

The residual graph encodes all of this information. The backward edge capacity tells us how much flow we can undo. So, if we pushed f flow from u to v, then the residual graph has a backwards edge (one from v to u) with weight f. The forward edge in the residual graph tells us how much flow we can still push in

[snow cedar]

ok, thanks. would that be 19C3 - 13C3?

[knotty cape]

I'm a bit tired, so I may be making an error.
24C3 - 19C3?

All cases:
Give 1 to each person. So, 21 pencils remain. Choose 3 of 21 + 3

Unwanted cases: Give each person 1, So, 21 pencils. Give Casper 5 more so it would be the unwanted cases. So, 16 pencils. Now choose 3 out of 16 + 3

[primal turret]

did the notation is find?

[little prism]

what?

that is pretty standard notation

in case that is your question

[primal turret]

ok , that what I wanted to know I like to use i in [n] instead of 1<=i<=n but i don't see my lecturers do that alot

[little prism]

well it's standard notation depending on the context

and you know, sometimes it's more readable to use something like 1 <= i <= n instead

at least imo

[vale cairn]

To me [n] means {0,1,...,n} so you have to be careful i suppose

[haughty garden]

Yeah I see that notation a lot to mean the set of the first n positive integers, especially in number theory and combinatorial texts

[snow cedar]

would this be summing up multiple cases of remaining letters?

after using 3 decimal digits on the last 3 characters, the number of possible charactes you can use is now 26 - 3

but when you choose 3 letters from the set of vowels that number of possible characters can be 23 - 1, 23 - 2, 23 - 3

[spiral aspen]

sorry for late response. @pale epoch and opengangs thanks for the explanation! it does make more sense now.

i do get what residual graph does. Still a bit unclear about the lemma

[spiral aspen]

oh so basically I already have my flow "f" from source to destination and I can find another flow "g" by looking at the residual graph? thats what its saying?

[pale epoch]

well, yes

but more, you can use that flow g to extend the original flow f to the flow h

which is better

[spiral aspen]

ah i see

alright thanks!

and once i cant do that anymore

its a maximum flow

[spiral aspen]

this is analysis of edmonds karp algorithm

I dont quite understand lemma 3

lemma 2 states that distance labels d(v) never decrease. I can sort of see how this is true. I am assuming its saying it never decreases since im always choosing the shortest path in this algorithm so the next iteration ill choose a longer path

[north apex]

?

[chrome slate]

How do you create a pulse using logic gates?

[slate rivet]

is the transitive closure of a irreflexive relation also irreflexive?

[grand totem]

No, take for example R = { (0, 1) }

oh wait woops i read that as equivalence closure not transitive closure

so also add (1, 0) in there

[slate rivet]

ok, thanks

that was much simpler than I thought

[regal gate]

So I was looking at Leibinz rule and I was wondering in which other cases does a form of a "binomial theorem" holds ?

Does anyone know other fun examples?

https://en.wikipedia.org/wiki/General_Leibniz_rule

[wet flame]

Is the first part just (0,0),(1,1),(2,2) and so on?

Second part pretty sure it's a function since it maps one digit to one location

[gritty crescent]

Only if your student number is 0123456789

Take a closer look at the defintion

[gritty crescent]

[wet flame]

Would S be a function aswell? For part 3

A bijection

[gritty crescent]

Think about it. Work with a random student number (ideally one that is not too nice, such as one that has repetitions).

Write down R and S explicitly

[wet flame]

ah

[broken sonnet]

can someone help me understand this problem?

You have 10 unique dark chocolates and 20 unique milk chocolates. You would like to select 5 dark chocolates and 5 milk chocolates to give to your friend as a gift. However, 3 of the milk chocolates contain nuts, and you only want to include at most one of these three nutty milk chocolates in your final selection.

How many ways can you select chocolates for your friend? That is, how many ways are there to select five dark chocolates and five milk chocolates so that no more than one of the three nutty milk chocolates is included?

This is my solution:

We can select chocolates as follows:

\begin{enumerate}
\item First, we select 5 dark chocolates, can be done in $10 \choose 5$ ways
\item In the first case, milk chocolates with 1 nutty milk chocolate:
\begin{enumerate}
\item Select 4 milk chocolates, can be done in $17 \choose 4$ ways
\item Select 1 nutty milk chocolate, can be done in $3 \choose 1$ ways
\end{enumerate}
\item In the second case, milk chocolates without nutty milk chocolate:
\begin{enumerate}
\item Select 5 milk chocolates, can be done in $17 \choose 5$ ways
\end{enumerate}
\end{enumerate}

Therefore, by the multiplication rule, we can select chocolates in
$10\choose 5$[$17 \choose 4$ $+$ $3 \choose 1$ $+$ $17 \choose 5$] ways.

[vital dew]

phamous

[vivid gust]

is anyone able to help me walk through solving a pseudocode

[cloud dirge]

If we think of the Power set of R^2 as every possible image, then the Power set of the Power set of R^2 as every possible set of steps to contruct every possible image

Does that make sense?

[sudden minnow]

no

[cloud dirge]

Why not?

Lets say the set that with all points (x,y) in R^2 : x^2+y^2=1

Nvm

I got why It doesnt make sense

[wicked widget]

This is from a graph algorithm class, I am not sure what the triangle operator means at the end represents, anyone has an idea?

Oh it is named Berge's theorem, so I found that it is symmetric difference, solved 😄

[fluid pine]

An orientation of a graph G=(V,E) is any directed graph G'=(V,E') arising by replacing each edge {u,v}∈E either by the directed edge (u,v) or by the directed edge (v,u).
Prove by induction that for every planar graph there is an orientation such that each vertex has at most five outgoing edges.

Can someone help with this? I am not sure what the induction hypothesis should be. I am also doubting between the cases of n=1 and n=0 for n=number of vertices.

[stray reef]

tbh it probably makes most sense to start with n=7, since for n ≤ 6 each vertex has no more than 5 adjacent edges period.

but then maybe induction on the number of vertices isnt really the way to go either?

n=7 sounds hairy to check explicitly

[fluid pine]

On what would you do induction on then?

[stray reef]

honestly not sure. edge count, maybe?

[fluid pine]

https://math.stackexchange.com/questions/2600153/show-that-every-planar-graph-admits-an-orientation-such-that-each-vertex-has-at

I found this. The first answer is not totally clear but it helps somewhat.

[wet flame]

part iii)

n has to be greater than 7 as your taking away 2m so must atleast be 8^2 =64
i think it cant be odd square numbers greater than 7 because that would lead to an odd number and therefore cant substract even number to get even
so the domain would be something like {(2k)^2 | k > 4}
for some natural number k
idk about the image
(8,7), (10,25),(12,47) (14,73)
m seems to be odd

[rapid mural]

are you not able to work out the image?

they give you the property of S

[wet flame]

how would i work it out

[rapid mural]

you seem to be doing just fine (second last line)

[wet flame]

i guess in this case I can rearrange for m

but would that always work?

[rapid mural]

it depends on the question

[broken sonnet]

im having trouble coming up with "closed form" to this problem

Alex and Petros are avid Marvel fans, and each one has collected all n of the limited-edition
Marvel figurines, with no repeats. Alex and Petros would each like to display some subset
of their collection at the upcoming Marvel convention. However, Petros does not want to be
outdone. He must include every figurine that Alex brings, and at least one additional figurine.
How many ways can Alex and Petros choose figurines in such a way for the convention?
Please note that the final answer must be expressed in closed form.

here is my solution

Let $n$ represent the number of limited edition Marvel figurines and let $r$ be a natural number.\newline
Since Alex and Petros have the same collection, let $A$ be a set with $n$ Marvel Figurines, that is $\mid A \mid = n$.\newline
Assume $n \geq 1$. \newline
Since Petros must include every figurine Alex brings and at least one additional figurine, to satisfy this condition, Alex can choose any subset of $A$ containing $r$ figurines from $n - 1$ figurines. Thus, Alex can choose to display figurines in $n - 1 \choose r$ ways.\newline
Then, Petros can choose to display figurines in $n \choose r + 1$ ways. \newline

Therefore, by the multiplication rule, if $n \geq 1$, then Alex and Petros can choose to display figurines in $n - 1 \choose r$$n \choose r + 1$ ways. \newline

[vital dew]

phamous

[elder berry]

the solution is incomplete and the counting isn't precise, it's incomplete because you are only considering when r items are picked (you would need to sum for all r <= n) and the counting method only accounts for when Petros brings one additional figurine

the problem asks that Petros brings at least one additional figurine, so he could have two, or more different figurines than Alex

[broken sonnet]

im not sure how i would incorporate that into my solution

we were also told to only care about cases that satisfy the condition for Petros

i appreciate your response btw

[elder berry]

well if I approached the problem correctly, I reversed the problem slightly by considering the following: first pick the figurines that Petros will bring, then consider a valid subset of the figurines Petros has for Alex to bring to the convention

[broken sonnet]

would I need an additional variable for Petros, so it is something like:

$n \choose r + g$

[vital dew]

phamous

[broken sonnet]

where g is the additional number of figurines Petros wants to bring

[elder berry]

no, that would only complicate matters, let's stick to n - number of total figurines and r - number of figurines Petros brings

[broken sonnet]

ok i see what youre saying, so basically Alex chooses a subset from a subset of A

it seems to me though that alex dictates what petros brings, since for Petros it is whatever Alex brings + some additional figurines that is 1 or more

[elder berry]

that's fair, but since we want all possible cases, that fact becomes irrelevant here and we may as well switch who dictates the choice of figurines (since all-in-all, all combinations will be counted either way)

As an example, suppose we have n = 5 figurines in A = {a, b, c, d, e}

Now let's consider the case r = 4, Petros picks four figurines for the display

In how many ways can Petros pick four figurines out of A?

[broken sonnet]

ok so that would be 5 choose 4

[elder berry]

mhm, and now the trickier part, from the 4 selected items, how many possible subsets are there?

[broken sonnet]

that would be 2^4 subsets

[elder berry]

perfect! but the tricky part is you need to remove 1 of those subsets

[broken sonnet]

so 2^4 - 1

[elder berry]

why do we remove one?

[broken sonnet]

so from lecture there was this example of overcounting

but i still dont quite understand it, because of the empty set

[elder berry]

well in our case we don't remove the empty set, rather we remove the set consisting of all those 4 figurines

[broken sonnet]

oh my

that is right

[elder berry]

if Petros has {a, b, c, d}, one of the counted subsets is {a, b, c, d} which can't be a valid subset for alex

right

so we found number of ways to pick items for Petros, and independent of that number of subsets for Alex

product rule gives you all possible combinations for the case r=4

[broken sonnet]

so Alex's subset has to be atleast - 1 elements from Petros

[elder berry]

$\binom{n}{r} \left( 2^r - 1 \right)$

[vital dew]

peaceGiant

[broken sonnet]

since Alex's subset can be empty, but cannot have all elements

[elder berry]

exactly, so far was the example clear?

[broken sonnet]

that makes sense but I still don't quite understand how you arrived at that solution

[elder berry]

well that isn't the solution

it's for the case when Petros has r items

[broken sonnet]

i see

[elder berry]

Petros takes r items from n, Alex takes any valid subset of items from the ones Petros has

the last step is to just sum all of these cases

remember, r can range from 0 to n, Petros can take any number of figurines

$\sum_{r=0}^n \binom{n}{r} \cdot (2^r - 1)$

[vital dew]

peaceGiant

[broken sonnet]

so do we just give some examples of A = 1, A = 2, A = 3, ... A = n?

for it to be "closed form"

[elder berry]

nope, we evaluate the sum, have you worked with the binomial theorem or binomial expansion before?

[broken sonnet]

no i havent

if i have it has been a very long time and i don't remember, im going into this class with just basic algebra that I refreshed myself with on Khan academy

[elder berry]

welp, there goes my motivation to introduce the solution to the problem out the window x)

there is another way to view and solve this problem, but again it is less intuitive than what I just had written

let me think of a way to motivate it

Alright, let me try again

instead of viewing the problem from the perspective of the players, you can view it from the perspective of the individual n figurines

for any combination that satisfies this problem, three things can happen

(Let's look at figurine 1)

1. either both Petros and Alex have the figurine in their display
2. only Petros has the figurine in their display
3. no one has the figurine in their display
   (notice that Alex can't have the figurine in his display, that would contradict the problem)

does it make sense that only these 3 situations can happen for each figurine?

[broken sonnet]

hmm

it sounds similar to when we count sequences, like when counting words of length m made of only vowels, which would be 5^m

[elder berry]

excellent, that is where we are headed

[broken sonnet]

without jumping too far ahead, i would think of something like n^3 subsets?

since there is 3 ways for each figurine to be displayed

[elder berry]

well 3^n actually

because remember, n figurines, 3 options, 3*3*...*3

[elder berry]

think of the situations mentioned above as the letters A, B, C.
now think about making a n - letter word using only the letters A B C with repetition

it's a bit of a stretch, but hopefully it's manageable and it makes sense

(three options for figurine 1) * (three options for figurine 2) * ... * (three options for figurine n)

cool?

[broken sonnet]

ok

so basically we think in terms of length

and the possibilities for each position, is 3

[elder berry]

right, if 3^n makes sense, that number is the number of ways to arrange the figurines so that Alex doesn't have more figurines than Petros

[broken sonnet]

kinda of like binary, where 0 is not present, and 1 is present

but we have a 3rd scenario

[elder berry]

great analogy, indeed

[elder berry]

going back to this, 3^n overcounts because it also considers the cases where Alex and Petros have the same number of figurines thus, we need to subtract those cases

do you want to give it a try and find the number of subsets so that Petros and Alex have the same figurines?

[broken sonnet]

yes i am going to try and work through this now with this approach

will you be around?

i really appreciate you helping me, i was having alot of anxiety but i feel better about it now

[elder berry]

i think so, if not someone else will respond

glad to hear that <3

math is about enjoying the process hahahha, don't stress it

[broken sonnet]

ok

Let $n$ represent the number of limited edition Marvel figurines.\newline
For each figurine in the entire collection, we consider: (1) a figurine that Alex and Petros is bringing, (2) a figurine that only Petros is bringing, (3) a figurine that was not chosen.
Suppose Alex and Petros can choose the Marvel figurines in $n$ steps as follows:
\begin{enumerate}
\item Step 1: Alex and Petros choose the 1st figurine, can be done in 3 ways.
\item Step 2: Alex and Petros choose the 2nd figurine, can be done in 3 ways.
\item Step 3: Alex and Petros choose the 3rd figurine, can be done in 3 ways.
\item ...
\item Step n: Alex and Petros choose the nth figurine, can be done in 3 ways.
\end{enumerate}
Therefore, the total possibilities to choose figurines is $3^n$.\newline

Since Petros must include every figurine Alex is bringing and at least one additional figurine, we can write $3^n - 1$ to account for when the size of Alex's subset is the same as $n$.
Therefore, Alex and Petros can choose figurines in
\begin{align*}
\boxed{3^n - 1}
\end{align*}
ways.

[vital dew]

phamous

[broken sonnet]

@elder berry i think i got it now

[elder berry]

reread this, you need to subtract more cases

if you do it right, that gives you (spoiler) ||3^n - 2^n||, number of options where Petros has all the figurines Alex has minus number of options where Petros and Alex have the same number of figurines (aka they have the same figurine, which furthermore is equal to just counting the number of subsets)

[broken sonnet]

ok

so we are using complementary counting

i didnt look at the spoiler yet btw

haha

ok

so then i think it would be 3^n - (2^n - 1)

$3^n - (2^n -1)$

[vital dew]

phamous

[elder berry]

Remind me why the -1?

in 2^n - 1

[broken sonnet]

there is a possibility that alex has the same size subset of a subset that petros has

and that is not possible based on the condition

[elder berry]

I'm not following

[broken sonnet]

hmm let me rethink this for a sec

ok nvm

it would be just 2^n, since we are only considering that it is a figurine that petros is also bringing or a figurine that alex himself is bringing

We don't consider that a figurine in Alex's subset is a figurine that only Petros is bringing

3^n already includes all of the possible subsets with figurines that only petros is bringing

so we just substract from that with 2^n

[elder berry]

indeed, quite an elegant solution but a bit tricky to spot

[broken sonnet]

is it necessary to show i counted for Alex?

this is what i did

Let $n$ represent the number of limited edition Marvel figurines.\newline
For each figurine in the entire collection, we consider it to be: (1) a figurine that Alex and Petros is bringing, (2) a figurine that only Petros is bringing, (3) a figurine that was not chosen.
Suppose Alex and Petros can choose the figurines in $n$ steps as follows:
\begin{enumerate}
\item Step 1: Alex and Petros choose the 1st figurine, can be done in 3 ways.
\item Step 2: Alex and Petros choose the 2nd figurine, can be done in 3 ways.
\item Step 3: Alex and Petros choose the 3rd figurine, can be done in 3 ways.
\item ...
\item Step n: Alex and Petros choose the nth figurine, can be done in 3 ways.
\end{enumerate}
Therefore, using the multiplication rule, the total possibilities for them to choose figurines is $3^n$.\newline
Since Alex's subset cannot include a figurine that only Petros is bringing, for each figurine in Alex's subset we consider: (1) a figurine that Alex and Petros is bringing, (2) a figurine that was not chosen.
Suppose Alex can choose the figurines in $n$ steps as follows:
\begin{enumerate}
\item Step 1: Alex chooses the 1st figurine, can be done in 2 ways.
\item Step 2: Alex chooses the 2nd figurine, can be done in 2 ways.
\item Step 3: Alex chooses the 3rd figurine, can be done in 2 ways.
\item ...
\item Step n: Alex chooses the nth figurine, can be done in 2 ways.
\end{enumerate}
Thus, Alex can choose figurines in $2^n$ ways using the multiplication rule.
Now, we can use complementary counting to find the ways Alex and Petros choose figurines. Therefore, Alex and Petros can choose figurines in
\begin{align*}
\boxed{3^n - 2^n}
\end{align*}
ways.

[vital dew]

phamous

[nimble crescent]

Hello

I don't know if I should post this here

But

"Conjuntos" Sets Problem I have and I can't identify what is the name of the problem or how to solve

Can anyone identify the name of this kind of Problem? Or at least provide an tutorial on how to fix it.

@wary phoenix Didn't get any answer about this in the question thread

[random thicket]

hi i have a problem that i need to solve: I need to show two different numbers, each of which is a power of 2, that the difference between them can be divided by 41.

[oak dune]

I need help with a logical equivalence problem

[rapid mural]

#proofs-and-logic might be better

but you can ask anyway

[rapid mural]

whats the exact question?

that proposition is definitely not always true

[hexed shore]

A bagel store sells onion, poppyseed, egg, salty, pumpernickel, sesame, raisin, and plain bagels. How many ways can you choose a dozen bagels that have at least one bagel of each type?
There's 8 spot filled with each type of bagel
and 4 other to be filled with one of all the types of bagel so 8C4 = 70
So technically 8 * 70 = 560
But the answer is 330 and I don't have any idea

[weary tiger]

i think this is algebra

not discrete mathematics

[hexed shore]

No its discrete mathematics

permutations and combinaisons

[vagrant ravine]

Guys!

I need help for a discrete math question

[sand talon]

shoot

[hexed shore]

A publisher owns 3,000 copies of a discrete mathematics textbook. How many ways can he store these books in the warehouse if the copies are indistinguishable? Wouldnt this be 3000!

[vagrant ravine]

This is the question

@hexed shore

(i) True. Since a<b and c is a positive number, a+c must be less than b+c.
(ii) False. Counterexample: let a=2, b=4, c=1, and d=3. Then a+d=5 and c+d=4, so a+d is not less than c+d.
(iii) True. Since c<d, b+c must be less than c+d.
(iv) True. Since a < b and c < d, it follows that a+c < b+d.

My answers

But I think I did some thing ls wrong

Some things*

For part a

[rapid mural]

iii is wrong

you made an assumption that isnt allowed

hint: ||look at b and c, what did you assume here?||

and so is iv

same problem

[vagrant ravine]

Ohh thanks!

Let me work it again

[haughty garden]

3000! assumes that the copies can be distinguished from one another

the problem here specifies that they are indistinguishable

[vagrant ravine]

(iii) True. Since a < b and c < d, it follows that b+c < c+d.

[haughty garden]

b + c < c + d is true if and only if b < d

so the question is: can you make the assumption that b < d?

[vagrant ravine]

You can't make that assumption. So then it's false?

[haughty garden]

well... can you come up with a counterexample?

[vagrant ravine]

Yeah!

So if b is 100

And d is 2

And c is 1

100+1 is bigger than 1+2

[haughty garden]

yeah basically anything that makes b < d false lol

[vagrant ravine]

So it only holds if b<d

Okay

Thankss

[haughty garden]

nwss

[vagrant ravine]

(i) True. Since a<b and c is a positive number, a+c must be less than b+c.
(ii) False. Counterexample: let a=2, b=4, c=1, and d=3. Then a+d=5 and c+d=4, so a+d is not less than c+d.
(iii) False. b + c < c + d is true if and only if b < d. Counterexample: let b = 100, d= 2 and c=1. b+c=101>c+d=1+2
(iv) True. Since a < b and c < d, it follows that a+c < b+d.

How is this for a revised answer?

I think iv is wrong too

I should probably fix that

I would need to give a counter examples for it?

[weary tiger]

can someone please verify if these answers are correct?

[analog hound]

I'm having a hard time understanding this, and I think it would be easy to get wrong just using intuition, so I was wondering if I could formalise disjointness.

Is disjointness the same thing as independence in the context of probability?

Here's my attempt at formalising this: Suppose we're counting objects in a set $U$. Let $C:\mathcal{P}(U)\rightarrow\mathbb{N}$ be the map $A\subseteq U \mapsto \frac{|A|}{|U|}$. Then $(U, C)$ is a sample space

[vital dew]

person2709505

[sudden minnow]

disjointness is the same thing as disjointness in probability

[analog hound]

Ok, so we just want that the count of the objects satisfying both conditions is the sum of the counts?

(Wait, this is just the additive principle. I guess that's a good sign?)

[sudden minnow]

yes

you want cardinality of A union B to be cardinality of A plus cardinality of B

[analog hound]

But in my previous notation, $A,B$ disjoint $\iff A\cap B=\varnothing$

[vital dew]

person2709505

[sudden minnow]

there is nothing deep here

yes that is what disjoint means

[analog hound]

Yeah I think I'm seeing that now

I'm very much getting used to the ideas (especially probability)

[glacial eagle]

Could someone explain to me how a polylogarithm works.

Would an equation such as $\sqrt{2}^{log(x)}$ be considered polylogarithmic? I am going off the pretense that the logarithm itself cannot be a exponent, but can be multiplied by a constant or be to the power of a constant. I might be wrong though and that is why I am checking

[vital dew]

torisutan

[glacial eagle]

Please excuse the bad LaTeX, undergraduate student here lol

This is for a class I am taking on DSA, asymptotic notation

[glacial eagle]

Also, does it matter what x is for a function to be considered polylogarithmic? I.E. Can a function such as f(x) = log(x!) or f(x) = log(3^x) be considered polylogarithmic?

[stray reef]

$(\sqrt{2})^{\log(x)} = (2^{\log(x)})^{1/2} = x^{1/2}$ surely

[vital dew]

Ann

[stray reef]

unless your log has a base other than 2

log(x!) is asymptotically x log(x) and log(3^x) is x log(3), and neither of these fit the definition of a polylogarithmic function, nor are asymptotic to one

[haughty garden]

An algorithm is said to be polylogarithmic if its running time is of order O((log(n))^k) for some constant k. You can see that logarithmic and polylogarithmic algorithms coincide if k = 1; this implies that all logarithmic functions are polylogarithmic. Another way you can think about polylogarithm is that it is polynomial in terms of its logarithms.

[steady path]

Definitely not, and in fact there are in some sense "opposites". If I have two disjoint events A and B, and I tell you that A has occurred, do you learn anything about the occurrence or non-occurrence of B? Can A and B be independent?

[analog hound]

Oh hmm

I should go revisit some definitions

[glacial eagle]

thank you Ann and opengangs, I see this now. So it doesn't matter what k is as a base or an exponent because it is a constant. However, something like $log_{5}(x^{2})$ can be a polylogarithm but something such as $log{(x!)}$ cannot since the asymptotic notation will differ depending on if it is polynomial, exponential, factorial, et cetera

[vital dew]

torisutan

[steady meadow]

I need help with this question:
How many integer solutions of the equation x1+x2+x3+x4+x5+x6 = 20.
while 1<=x1,x2,x3,x4,x5,x6<=4

need to use the principle of inclusion and exclusion

[haughty garden]

We have two hidden restrictions here; each x_i >= 1 and each x_i <= 4

The first restriction is easy to deal with

Start by allocating one to each of the x_i's to reduce this down to a problem of dealing with only the restriction that x_i <= 4

In other words, the number of solutions is now equivalent to the number of solutions to the equation x_1 + x_2 + x_3 + x_4 + x_5 + x_6 = 20 - 6 = 14 such that x_i <= 4 for each i

You now want to apply inclusion/exclusion

[steady meadow]

I tried to define U as (20+6-1 above 6-1) for all the cases but then i realised it's not true. then i need to consider cases that 0<=x<=3 but i dont really understand this method

[haughty garden]

remember that C(20 + 6 - 1, 6 - 1) also assumes that some x_i's could be 0

[haughty garden]

Do you understand everything up to here?

[steady meadow]

this is what i am trying to understand now lol

[haughty garden]

the idea is that, well if you want to force each x_i >= 1, then just start by allocating 1 to each of these x_i's

so now you can add 0 or more amount to each of the x_i terms

[steady meadow]

in another words, i can define new variable which is for example y=x-1 so y will be 0<=y<=3?

[haughty garden]

yup!

[steady meadow]

but the max amout will be 18

[haughty garden]

why would it be 18?

y_i = x_i - 1 for each x_i

So you have x_1 + x_2 + x_3 + x_4 + x_5 + x_6 = (y_1 + 1) + (y_2 + 1) + ... + (y_6 + 1) = 20

so y_1 + y_2 + ... + y_6 = 20 - 6 = 14

and you have 0 <= y_i <= 3 for each y_i

[steady meadow]

x_1 -1 + x_2 - 1 + x_3 - 1 + x_4 - 1 + x_5 - 1 + x_6 - 1 = y_1 + y_2 + ...y_6 = 20 it was like this before this:
x_1 + x_2 + x_3 + x_4 + x_5 + x_6 = (y_1 + 1) + (y_2 + 1) + ... + (y_6 + 1)
?

[haughty garden]

your original equation is x_1 + x_2 + x_3 + x_4 + x_5 + x_6 = 20

you have an equation for y_i in terms of x_i, namely y_i = x_i - 1 or x_i = y_i + 1

so wherever you see x_i, you just replace it with y_i + 1

[steady meadow]

ugh i still dont get it, what's the different between y_i = x_i - 1 or x_i = y_i + 1
it can be 0<=y<=3 || 2<=y<=5

oh wait, you tranfered 1 to other side

[haughty garden]

there's no difference between y_i = x_i - 1 or x_i = y_i + 1. The idea is that you begin with an equation with x_i terms with restrictions 1 <= x_i <= 4 and you transform it to a new (but equivalent) equation with y_i terms with simpler restrictions, namely 0 <= y_i <= 3

[steady meadow]

sorry for the delay, but thank you for the help!

[vivid gust]

hello, i had a question

is anyone able to call on here and help me with pseudocodes?

[weary tiger]

Determine all simple graphs G for which the adjacency matrix of G equals the incidence matrix of G (with an appropriate ordering of vertices and edges).
The 3-cycle satisfies this property, and by extension any disjoint union of distinct 3-cycles. I think that this is the only family of graphs that satisfies the property.
How do I prove that no other graphs satisfy this property? I know that in an incidence matrix, all columns have two 1's in them. For this to be equal to an adjacency matrix, it must be symmetric, so all rows have two 1's in them. Hence any graph satisfying this property must be 2-regular. The only finite 2-regular graphs are disjoint unions of cycles. In other words how do I prove that no n-cycles with n>3 satisfy this property?

[novel ore]

would this equivalence relation just partition R into every single real number? my reasoning is that say x= 5. Then the equivalence class of x would be all real numbers less than or equal to x. but taking, say, x1 = 4.9, the equivalence class would contain 4.9, which would intersect the equivalence class of x. by definition, a partition of R must be a disjoint union of sets. this leads me to conclude that a partition of R must be every real number in R. Is this true?

[little prism]

is it an equivalence relation?

[weary tiger]

if this is in the context of set theory, think of the relation curly R as a set

with elements from R x R, or R2

[novel ore]

is it not? xRx, since every single real number is equal to itself. if x >= y and y <= x, then x = y. if x >= y and y >= z, then x >= z

[sudden minnow]

if x >= y and y<= x, then x = y

[weary tiger]

the second property is not symmetry

[sudden minnow]

which axiom of an equivalence relation is that

[weary tiger]

that's antisymmetry

[novel ore]

oh wait

you're right

[sudden minnow]

you have perfectly described what a partial order is

and indeed, that relation sure looks like an ordering

[novel ore]

right, i completely forgot and got them mixed up loll

so it wouldn't be an equivalence relation then

[sudden minnow]

yes

[novel ore]

ah, so xRy doesn't imply yRx which makes sense

ok, got it, thank you

but this set is antisymmetric and transitive but also reflexive, does reflexivity not apply to the definition of a partial order? or does a partial order not care about reflexivity

well

[little prism]

well either you have a strict partial order or a non-strict partial order

non-strict partial order is reflexive

strict is irreflexive (or whatever it's called)

[novel ore]

got it, thanks

[weary tiger]

can anyone help? I'm still stuck

but I think it applies to odd cycles as well

not just 3

[vivid gust]

I have a question regarding a problem im working on right now (1) n=12 (2) m=20 (3)=for i = 1 to n + 4 (4) for j = 1 to m (5) print (i,j)

have to find how many times line 5 is executed
and i got 240? but it was wrong and im confused

[weary tiger]

n + 4 = 16
16 x 20 = 320

[analog flare]

am i right here?

I was thinking in general, multiplication is commutative, meaning that the order of the operands does not affect the result

so that was my reasoning for 1, then again not sure about it and the rest

[magic knoll]

ur supposed to answer what the table tells u

[ember obsidian]

pretty much this

after the informal calculation you can verify it by formal proof to check your intuition

like prove that set equality using the definition

[glacial eagle]

Would a function f(n) = $2^n$ have a different time complexity from a function f(n) = $2^{2^n}$?

[vital dew]

torisutan

[glacial eagle]

My guess is that it would, because the second function would grow massively larger than the first function, and thus making it it's own time complexity

[sudden minnow]

2^(2n) = (2^n)^2

make of that what you will

[glacial eagle]

Ahh, it is the same. thanks

gotta brush up on my algebra a bit lol

[sudden minnow]

I think you need to brush up even more after you said that man

do n and n^2 have the same time complexity?

[glacial eagle]

no they do not

[sudden minnow]

tbh I don't know what definition of complexity is used in these cases, but you can't bound 2^2n by a constant times 2^n

[glacial eagle]

$\Theta(2^{n})$

[vital dew]

torisutan

[glacial eagle]

this is what I am trying to find out if they are both equal to

[sudden minnow]

so you want to know whether there exists a constant C such that

,, 2^{2n} \leq C 2^{n}

correct?

[vital dew]

lems

[sudden minnow]

sry opposite way

[glacial eagle]

We are analyzing it where there is no bound and without regard to constants

[unreal stump]

Isn't it $2^{2^{n}}$

[vital dew]

Drake

[glacial eagle]

So in this case, it doesn't matter if it is $2^{n}$ or $4^{n}$ or $2^{2n}$

Yes

[vital dew]

torisutan

[sudden minnow]

again, I am asking if this is what you are asking

[sudden minnow]

depends on how you associate, but generally no

[glacial eagle]

I am asking this

[sudden minnow]

yeah sorry I'm not a compsci student, you have to explain to me mathematically what being "in the same time complexity" means

if I interpret it as being able to bound one by a constant multiple of the other, I can answer you

[unreal stump]

I guess here it means $f(n) \in \Theta(g(n))$

[vital dew]

Drake

[sudden minnow]

okay, so you are asking whether there exists a constant C such that
$2^{2n} \leq C 2^n$

glad to have an answer

[vital dew]

lems

[sudden minnow]

this is equivalent to asking for a C such that $2^n \leq C$

[vital dew]

lems

[sudden minnow]

and what do you think

I divided both sides by 2^n

[glacial eagle]

No, runtime analysis in our DSA class is regardless of constants

Sorry, it is kind of confusing

[sudden minnow]

...

[sudden minnow]

you posted this

what are c1 and c2

please read your text

[glacial eagle]

Where did you get $2^{2n}$, I was referring to $2^{2^n}$

[vital dew]

torisutan

[glacial eagle]

Second one grows a lot faster than the first

[sudden minnow]

oh, so you were asking for that

I mean, even for 2^(2n) and 2^n they are in different thetas

so for 2^(2^n) even moreso

[glacial eagle]

Yeah, we are looking at how similar two functions are when the limit is infinity

Yeah

I think so too

[sudden minnow]

it is not about thinking, the question is whether there exists a constant C such that
$$2^{2^n} \leq C2^n$$
for all n greater than some sufficiently large n0

it is the same thing, divide both sides by 2^n

such a C cannot exist

[haughty garden]

It might be worth noting that such a C cannot depend on the value of n

[vital dew]

lems

[glacial eagle]

Cause no matter how big C gets, it will never be able to reach the size of the LHS since it is larger when the limit is infinity

Is that true if you placed a constant C before n on the exponent as well?

So let's say $2^{cn}$

[vital dew]

torisutan

[sudden minnow]

yes, because then you are just comparing the exponents

one exponent is 2^n the other is cn

so it reduces to exponential vs linear

not close

[solemn zephyr]

Can anyone please explain me this proof - its a proof of cantor theorem saying |A| < |P(A)|
i understand we can do it by saying there is no injection from A to PA
but what fucks my mind is that subset B

https://media.discordapp.net/attachments/409596215697866773/1067089913851428985/pHmt.png

[grand totem]

we're trying to prove that there is no surjection from A to P(A), not that there is no injection (there is in fact a fairly simple injection from A to P(A), which is the "|A| ≤ |P(A)|" part of the theorem)

and to prove that f can't possibly be a surjection, we exhibit one element of P(A), i.e. a subset of A, that isn't in the image of f

and that subset happens to be B, hence why the rest of the proof proceeds by assuming that B is in the image of f (so there is some y in A such that f(y) = B) and then arrives at a contradiction

[solemn zephyr]

thanks

[analog hound]

Doesn't $S$ also have to be closed under taking unions? Otherwise, how can we talk about, say, $P(A\cup B)$?

[vital dew]

person2709505

[analog hound]

Which also means S has to contain only sets

Or I am being silly and we have to define $P(A)=\sum_{a\in A}P(a)$ for any $A\subseteq S$ (but shouldn't they mention that in the definition, where they use that??)

[vital dew]

person2709505

[analog hound]

Oh no sorry that's wrong too. I just can't read

[haughty garden]

P is a function that takes elements from S; so if it happens that A U B is not in S, then naturally P(A U B) = 0 or we just ignore those types of events

[analog hound]

Yes

I somehow thought they meant $P(S)=1$ when they said $\sum_{s\in S}P(s)=1$, which was why I was confused

[vital dew]

person2709505

[grand totem]

The definition in the image above is for a sample space, not an event space

I believe that might cause the confusion

So (set theoretic foundations aside), S doesn't contain sets and so it's not even a question whether it's closed under union (that's all stuff concerning the event space)

[analog hound]

Ah, I see. They define events in the next chapter, but never the event space

I guess defining the probability of a subset of S works out to the same thing as defining the event space though

[grand totem]

In discrete probability (like here) this is all a bit nicer. The event space is simply the power set of the sample space (the set of all subsets) and the probability measure of an event may be computed by adding up all the probabilities of each outcome of the event

[analog hound]

Right, I forgot about non-discrete probability

Well thanks for the clarification!

[idle wave]

Just making sure, given a combinatorial class of strings, is the weight of the empty string always 0 by convention?

[tawdry night]

Hi , can anyone explain this question? Why the remainder is 2 ? And how to get remainder 2 when 4m mod 11?

[obtuse lance]

the line after it says Thus, which starts with 4m= ... = 11(4q+2) + 2 sort of explains it

this shows 4m is 11*(stuff) + 2, so it has remainder 2

[tawdry night]

I don't understand how to use a calculator to get the remainder of 2, suppose I use 1 and 2 instead of m and divide by 11 how to get the remainder of 2

[rapid mural]

you dont need a calculator

[obtuse lance]

you can get the remainder with a calculator by dividing and taking the number left of the decimal, then subtracting that off from the original number

for instance what's the remainder when you divide 17 by 3? 17/3 = 5.666... so you take 5 and multiply it by 3 to get 15, subtract that from 17 to get 2, the remainder

that's cause the integer part to the left of the decimal is how many whole times you can put the number into it

[rapid mural]

or if you have access to a computer

ipython >>> number % thing

[whole island]

Hi, I need some help
I am studying factorial polynomials and I am trying to calculate sums using them and I have to calculate this

I am using the method which you make a function out of this (g(n)), using polynomials and you are using the difference of g(n) (Δ(g(n)) to calculate the result

it turns out this is the g(n) that comes out

but the example does the following calculation for which I have no idea what is going on

I mean I get that Δ(g(n)) = n(n+1)(n+2) thus we substitute that but I find that the way my professor calculates the difference in this instance is wrong
I thought the formula for calculating this difference would be g(n+1) - g(n) and in which world is g(1) equals to 0 and why when he simplifies the polynomials he goes from downwards instead of upwards (F4(n) = n(n+1)(n+2)(n+3) so why is he going F4 (n+1) = (n+1)n(n-1)(n-2) instead of F4(n+1) = (n+1)(n+2)(n+3)(n+4) which I believe is the correct answer...) am I that bad in this or is my professor that bad and can anyone pls explain this to me before my notebook meets my monitor?

ok polynomials have are stated as - instead of +, fck it im that bad at math

and g(1) is 0 I was substituting to the n+1 formula so I was doing basically g(2)... the only thing I want if someone can tell me why are we using g(n+1) - g(1) instead of g(n+1) - g(n)

[clear pier]

Is anyone good with recurrence relations? I don’t rlly understand it ;-;;-;-

[grim tapir]

anyone got an idea on this question

its from a past paper

not sure exactly how to calculate the sequential fraction of the parallel mergesort

[modest swan]

is the only difference between "x" and "a" is that theyre simply two different elements of the set [a]? what is a set [a] or [b] exactly

[rapid mural]

equivalence class of a

x in [a] if x ~ a

for example left cosets of a subgroup constitute equivalence classes

[modest swan]

oh i see

thanks

[rapid mural]

i apologize for this rather terrible example

probably not meaningful if you haven't seen group theory

for example if we look at all the even numbers {n | n mod 2 = 0}

we could have like [2]

which is also [4]

[tawdry night]

Oh... I solved this question. Thanks

Hi, can anyone solve this question? If 25q^2 + 30q + 9, what step I need to do?

[tight hound]

25q²+30q+9 = 5(5q² + 6q + 1) + 4

[nocturne peak]

can anyone help me with this

[pine canopy]

write out their truth tables imo

then translate that into a CNF

https://i.imgur.com/V9HoYST.png

Can someone explain to me what it means to have "two distinct" isomorphisms from G to H?

I don't really get what they're saying

H is isomorphic to G
so for some Per(G)=H, I get that. Are they saying Per(G)=H for a different permutation?

[nocturne peak]

Needs to be solved by the rules of equivalences

[pine canopy]

What does a<->b mean?

[nocturne peak]

so like the first one I have A<->, (A->B)^(B->A) equivalence, (-AVB) ^ (-BVA) Implication

Which puts that into the CNF format

[pine canopy]

yeah

[nocturne peak]

the second one

is kicking my butt

I get to implication

and im confused on what to do there

[pine canopy]

same thing though

[nocturne peak]

I have the implication right

but the next step im confused

would it be possible to use Demorgans...

[coral latch]

Hey y'all, can I get a clarification on this Q:

[coral latch]

The recurrence in question is:

[coral latch]

I see how the proof breaks down: || T(n) <= (2c + 1)n is not equivalent to T(n) <= cn for n/2 >= n_0 || ...which means the proof of T(n) = O(n) (the statement we want to disprove) can't be established by this induction. How does the proof of T(n) != O(n) fail? Is it that the induction doesn't lead to a proper contradiction (since || T(n) could be between cn and (2c + 1)n or actually less than or equal to cn||) and therefore we can't contradict our assumption (i.e., not proving our assumption (T(n) = O(n)) does not imply contradicting this assumption)?

The solution seems to conclude something similar, but I don't understand how this squares with the first sentence in the question or what "the induction is simply not powerful enough" means, exactly...

[coral latch]

Is the idea that if this induction worked, we would have proved something that is definitely false (i.e., T(n) = O(n)) but because we couldn't make the induction work we couldn't disprove T(n) = O(n)??

[leaden jay]

Does anyone have any ideas as to how to approach this proof?

[analog hound]

Do there exist nontrivial symmetric, transitive relations which are not reflexive? No, right?

[haughty garden]

Consider the set X = {a, b} with relation {(a, a)}. This is symmetric and transitive but not reflexive since (b, b) isn’t included

[obtuse lance]

idk if this counts, "X is a relative of Y", since it's awkward to say you're related to yourself, but not hard to see being related to someone is transitive and sysmmetric.