discrete-math

[fossil mural]

the idea is that if you have a function from X to Y, and an element of X, you can then get an element of Y by applying the function

[spice warren]

so for these two sets, X = {1,2,3} and Y = {1,2,3} what is an example?

f(1) can equal any element from set Y?

[ember obsidian]

you may want to read an intro to functions here https://www.mathsisfun.com/sets/domain-range-codomain.html

[ebon berry]

hi

when doing mods

for example (-133 mod 23)

do you do - (133 mod23) or (-133) mod 23

bc they give different answers

and idk which is the proper way to write it

[coral parcel]

In programming languages, mod generally behave like a multiplicative operator, so it will parse as -(133 mod 23).
However many programming languages also define the operator such that a mod b is always either 0 or has the same sign as a, so (-a) mod b and -(a mod b) actually gives the same results in that case (unless the negation overflows).

This is relevant because mod as a binary operator is fairly rarely seen in mathematics. Mathematicians prefer to speak of the three-place relation a ≡ b (mod c). It is not completely unheard of for a binary mod to be seen in a mathematical context, but it is rare enough that there are no strong convention about its operator precedence.

[coral parcel]

In practice, write the parentheses no matter whether you mean one or the other. That way you won't risk any misunderstandings.

[ebon berry]

o.o i dont get wht you said

this is my problem

so im trying to do it in parts

bc if i do one part wrong

then the entire thing is wrong

i put it in a calculator but it shows me a different answer so idk if im doing it wrong

or if its being typed incorrectly online

i can show you my work so far?

[ebon berry]

excuse me?

[coral parcel]

This mostly seems to be a problem about knowing which convention the person who wrote the problem is using.

Your guess about that is as good as mine, I'm afraid.

[ebon berry]

hi

ok um

i have another question then

am i reading this correctly

like these numbers...

is she saying i have to multiple all of the exponents

from each set

.. like those are huge numbers

do i have to do tht?

[coral parcel]

You're probably supposed just to show the result as a product of prime powers, like the starting numbers are given to you.

So in the first one you would answer $3^5 5^3$ rather than $30375$.

[vital dew]

Troposphere

[ebon berry]

hi

srry

i dont understand wht you mean

can i show my work?

ill show it..

@coral parcel

[coral parcel]

Yeah, that's definitely not the way to go about it.

You should have been taught how gcd relates to prime factorizations.

[ebon berry]

omg i think i get it

ill show you wht i did

ryc told me about it

acutally i dont get it

ill just show wht it hv

@coral parcel

[coral parcel]

You have at least five 3's on each side.

[ebon berry]

yes

[coral parcel]

Then why are you only writing 3^3?

[ebon berry]

srry i wrote 3^3

i meant 3^5

so i have 3^5 and 5^3

in common

idk wht to do next

[coral parcel]

There's nothing more to do than write 3^5 · 5^3 down as the anser.

[ebon berry]

wait so i just do (3^5)(5^3) and whatever i get is my answer?

[coral parcel]

No, you literally write $3^5 5^3$ and call it a day.

[vital dew]

Troposphere

[ebon berry]

oh

wait so im stuck on the second one now

second bullet

can i just like

multiple the first set

the issue is like if i find the lcm, itll be the same numbers

[coral parcel]

Well, there is no prime that appears on both sides.

[ebon berry]

yeah

thts why i was confused

11,13,17 are prime

[coral parcel]

But you can also write the given numbers as $2^0 3^0 5^0 7^0 11^1 13^1 17^1$ and $2^9 3^7 5^5 7^3 11^0 13^0 17^0$.

[ebon berry]

how did you get those numbers

2^0

[vital dew]

Troposphere

[coral parcel]

2^0 is just 1.

[ebon berry]

well yeah but why did you do that

[coral parcel]

Because now you have the same primes for each number.

[ebon berry]

oh..

[coral parcel]

And you can just take the minimum exponent for each of the primes, like you did before.

[ebon berry]

ill try

wait

there is nothing in common though

[coral parcel]

Right.

[ebon berry]

so like

wht do i do then

do i just put none?

[coral parcel]

You should be getting $2^0 3^0 5^0 7^0 11^0 13^0 17^0$.

[vital dew]

Troposphere

[ebon berry]

ohhh

bc i should have started at 0

not 1

i see wht you mean now

tysm

wiat

how can tht be right

can i show you my work

bc i still dont get it..

@coral parcel

[coral parcel]

Well, first state clearly what you mean by "that" when you ask how "that" can be right...

[ebon berry]

?

[coral parcel]

I'm assuming that when you wrote "tht" you meant "that", but I still don't know what "that" is.

[ebon berry]

oh tht means tht for short

bc i like to type fast, i tend to shorten words even if its unnecessary

its a bad habit

[coral parcel]

Why do you have each prime appearing two times in the result?

[ebon berry]

?

they arent repeated bc 2^0 isnt the same as 2^1

[coral parcel]

2 is the same as 2, though.

[ebon berry]

.. wait so are you that

if we have 2^1

it is assumed tht you also have 2^0

?

[coral parcel]

Sorry, I'll bow out here. I seem to be unable to communicate.

[ebon berry]

:/ omg no please

im not trying to be dumb im srry im trying

[blissful path]

I really don't have the best idea of what is going on here, but it seems possible that what Troposphere was getting at is that in a prime factorization of any number, you decompose it into the primes that make it up (raised to whatever powers are necessary). For example 10 would be 2^1 * 5^1. Or 27 would be 3^3. What you wouldn't write is that 10 is 2^0 * 2^1 * 5^ 1, because although true it is unnecessary to include 2^0 which is just multiplication by 1, as you can add exponenets with common base to create

[vital dew]

AustinU

[ebon berry]

yeah i think i figured out wht he meant

ig he didnt understand wht i meant

[ebon berry]

referring to this

[ebon berry]

thts wht i meant ig

[blissful path]

well, that doesn't make much sense because 2^0 is just multiplication by 1. So if your goal was to write each of the primes uniquely with their own exponents it wouldn't make sense to write the two twice. Either you have a 2, and write 2^1 or you don't and write 2^0, not both.

[ebon berry]

wht is wht i mean

[blissful path]

I would help more but I am not sure how

[ebon berry]

for 4b

[ebon berry]

bc he said i should get this

which is wht i got

unless youre saying he's wrong

[blissful path]

I'm definitely not saying that, I don't know how to do your problem or help with it

[ebon berry]

oh crap i wrote the answer wrong

I meant this

[coral parcel]

And all that just multiplies out to ... 1!

[ebon berry]

ohhh

lol i see

did i do the other problems below right?

[coral parcel]

I hope the final 53 was not omitted in (d). A number's gcd with itself is always that number itself.

[ebon berry]

oh its not srry

the pic cut it off

i put 53^1

towards the end

[coral parcel]

(f) is a bit of a trick question, because 0 doesn't really have a prime factorization.

[ebon berry]

isnt it 1 and 0..?

[coral parcel]

I don't understand that question.

[ebon berry]

bc 11111^0 is 1

my question or the f's question?

[coral parcel]

Your question.

[ebon berry]

for f i put 1111^0 * 0^1

so i tried to simplify

1111^0 is 1

and 0^1 is 0

[coral parcel]

That doesn't give the right result, though because 0 is not a prime.

[ebon berry]

yeah its not

[coral parcel]

What I'm saying is you cannot use the same procedure that worked for the other cases, because 0 doesn't have a prime factorization.

[ebon berry]

oh

isnt it just 0

[coral parcel]

No.

[ebon berry]

no wait..

1111

bc thts the greatest

[coral parcel]

Yes, but why?

[ebon berry]

1111*0 is 0

and 0 * 1111 is 0

i can draw a tree to show my work?

[coral parcel]

I would much rather you used words. It is hard to understand the very brief posts you make.

[ebon berry]

i cant use my words bc im mentally slow, i dont know how to articulate my thoughts very well

[coral parcel]

Take more time, then.

[ebon berry]

nor do i do well with reading comprehension, thats why i'm a "visual learner"

[blissful path]

0 has no factors other than 0, and 1111 has no factor of 0, so they can't share any factors.

[ebon berry]

right..

[coral parcel]

I don't think that is right

[ebon berry]

honestly i dont want you to run away, so im going to pretend that i understood what you wrote and put zero

[coral parcel]

To the contrary, everything is a factor of 0.

[ebon berry]

i have 2 more questions but they're word problems

my hw is due in like 2 hours so

i cant retake this course or ill be kicked out of the major

[coral parcel]

And since everything is a factor of 0, the "common factors of 1111 and 0" is exactly the same as "the factors of 1111".

[ebon berry]

i see

austin seems to be supporting your words

[blissful path]

sorry for misleading, I didn't know that

[coral parcel]

And it shouldn't be hard to see what the largest factor of 1111 is.

[ebon berry]

its okay austin, at least trope came back to correct you

so this is my next problem

after tht i only have one more problem

i did mod questions before but i never did a word problem, i think i need help setting it up first

[coral parcel]

(Good luck with that. It's almost half past three in the morning for me, so I definitely won't be able to engage with that).

[ebon berry]

C: ? what do you mean

you're like..

leaving me?

[blissful path]

someone else may come and help you, you should thank him for spending his free time helping you already

[ebon berry]

you dont know if trope is a he

[blissful path]

he has his pronouns on his profile

[ebon berry]

.. so

well i hope someone comes

and helps

before its too late

[blissful path]

See if you can extrapolate from this

I was able to find online

[ebon berry]

wait

is this for my question

or a different one

bc this is due at 11:59pm and its 9:27pm rn

[blissful path]

for your question

good luck with your deadline

[ebon berry]

are you smart

i mean that to be a serious question srry

?

[ebon berry]

and ty

[ebon berry]

idk if trope is still here

even though i see youre online

i think it would be nice if you would please help me with number 5

..hm

[upper venture]

/imagine

/imagine propmpt

[hazy pine]

this is not an AI art server.

[near cobalt]

hi

[latent quarry]

lmao, also such a weird channel to do it in

[sacred fern]

Hello, I am working on generating functions, and the textbook did this, could someone explain what is happening in this?

[unreal stump]

Well which step confuses you exactly

@sacred fern

[sacred fern]

From first line to second

[little prism]

geometric series

in reverse

[sacred fern]

I see, thank you

[fervent raven]

this might be the best channel to ask this on? or number theory, im not sure which

i was recently stuck on a proof in abstract algebra and realized that i'm sorely underinformed concerning gcd and lcm, so are there any properties, both popularly and esoterically used, that i should know about?

recently just found out that two relatively prime integers m and n that divide some k also imply that mn divides k (did not know that)

also found out that we can write lcm(m,n) = mn/gcd(m,n)

but i wasnt sure if there are any other additional identities that are worthwhile to read

[ivory badge]

Look at prime factorization and consider gcd in that light

If $x = \prod_p p^{e_p(x)}$

gcd$(a,b)=\prod_p p^{\inf{e_p(a),e_p(b)}}$

[vital dew]

Sharp

[ivory badge]

And lcm is takes the max between e_p’s

[unreal stump]

That's very very important

Another important thing would be bezout

[ivory badge]

Yeah pretty much the two main bits

[fervent raven]

ah ive seen that yes

also bezout’s the linear combination right?

i.e $\gcd(a,b)=d\implies ax+by=d$ where $x,y\in\mathbb Z$

[vital dew]

blanket

[ivory badge]

That’s the important thing I’m thinking of anyway

I forget names

[past lynx]

For equations that do not have variables can you even do induction proofs on it

[brave rock]

Just show us the problem you're struggling with

Your question doesn't really make sense

[past lynx]

its a homework problem i dont think im suppose to share but its effectively trying to prove something like

1^2 = (1+2)/3

inductively

[brave rock]

Then just calculate it

[past lynx]

which i find kind of dumb cause cant you just.. solve it

[ivory badge]

well I mean you can kinda vacuously induct on a true statement

yep [true] is true for n = 1, and [true] -> [true]

but I feel like that's probably not what it's asking

[stray reef]

@past lynx why don't you think you are supposed to share the problem? does your school expressly forbid that?

[past lynx]

probably cause im technically suppose to do my homework myself

but its whatever i just turned it in already

ill just pray and cope]

[sacred fern]

For this, can we use pigeonhole principal to prove that it is not possible? Since there are (7x5) games that are within the groups but only (7 choose 5) “spots”

[coral parcel]

No, there must actually be 7·5/2 games within each pool because 7·5 would count each of those games twice.

Perhaps you can see a more fundamental problem than pigeonholes here ...

[sacred fern]

How can they be fractional games?

I mean the way I see it, there is no way to connect the nodes in a way that we don’t over flow the spots

[coral parcel]

Exactly!

[sacred fern]

7x5/2 is fractional

[coral parcel]

Yes.

[sacred fern]

So how can there be 7x5/2 games

[coral parcel]

There can't, that's the point.

[sacred fern]

Hmm I still don’t get it lol

[coral parcel]

You seem to agree with me that it is impossible for there to be 17.5 games in each pool.

What is it you don't get, then?

[sacred fern]

How you got 17.5 games in the first place

I am not over counting because I am just counting one pool

Why did you divide by 2?

[coral parcel]

If you just multiply 7 by 5 you're couting each game twice: once for the each team that competes in it.

It takes two teams to play a game.

[sacred fern]

But there are 14 teams

[coral parcel]

There are only 7 teams in one "pool".

[sacred fern]

I have misread the problem 💀

I am sorry

[coral parcel]

Np.

[sacred fern]

So since there are a total of 17.5 games this cannot happen

Thank you!

[regal gate]

How would you solve this without generating functions?

The answer is 2* 3^(n-1)

I think if you just make an explicit expansion of the generating function you get using the "bi"nomial theorem, you will get the coefficients as a sum of combinatorial things, so probably suggests a proof

[regal gate]

guess its fine, because its like proving $3^n=\sum_{k=0}^n 2^k\binom{n}{k}$

[vital dew]

Croqueta

[manic frigate]

Could you explain why this statement is true?

[lyric quartz]

,rotate

[lyric quartz]

B^c is the complement of B, it contains all elements not in B.

A \ D contains all elements in A that are not in D

So A \ B^c are all elements in A that are also in B

Which is what A ∩ B

[vital dew]

Boytjie

[lyric quartz]

Oh right 🙂

[regal gate]

answer is n!, which is straightforward from generating functions

Let h(n) be that number, then consider h(n-1) and add one person N. The person N will sit to the right of one of the 1,...,n-1 persons or either be alone in a table. So h{n}=(n-1)h{n-1}+h{n-1}=n*h{n-1}

I was gonna ask if there is a combinatorial and noninductive proof... but I guess this is already good enough?

like it is not at all obvious at first glance that the answer is n!, it would be cool if there was an explicit bijection or something

[brave rock]

Would you like a hint for this? There is a very nice explanation

[regal gate]

sure

[brave rock]

A circular table looks quite like a cycle...

;)

[regal gate]

This already a proof, but I was looking for something non-inductive

ah

[brave rock]

Nice huh?

[regal gate]

lol yeah

Thanks

[brave rock]

np, that's a cool question

[regal gate]

[zealous elbow]

can anyone help with a hill cipher

so i know how to encrypt if its a normal 3x3 matrix but this confused me

or do i just encrypt two letters at a time

[zealous elbow]

actually i think i just forgot how matrices work

[manic frigate]

But doesn't that mean that the entire A should be the answer, not the intersection of A n B?

As all elements of A not in B include the Set of A as well?

[lyric quartz]

B^c can contain elements of A

[lyric quartz]

,rotate

[lyric quartz]

B^c is the striped "cloud"

So everything except B

[lyric quartz]

You could also use the element relation and write it out

[royal holly]

could someone explain this

how is C subset of D
when i plug in numbers
c = {-23,-17,-11,-5,1,7,13,19}
d = {-8,-5,-2,1,7,10,13,16}
could someone explain?

[ivory badge]

Prove or disprove

But 6r-5 = 6r-6+1

=6(r-1)+1

[ivory badge]

How do you get these

Also notice subset just means anything in C is also in D, and they’re not equal to the sets you wrote there

[vivid gust]

does anyone understand discrete math at all and can like tutor me?

[royal holly]

i figured out what i did wrong

[royal holly]

could someone please explain this proving this with element arguments

Im so confused on the solution

[ivory badge]

when is x in the left side

[royal holly]

we suppose that x is in the set of AU*(B and C)

then we prove that (AUB) and (AUC)

i get that

[ivory badge]

when exactly is x in the left side though

[royal holly]

but i dont get the cases

[royal holly]

what

[ivory badge]

write a predicate for it

x is in A u (B n C) iff some condition

[royal holly]

im confuse

this is how we are supposed to do it

[royal holly]

wdym

[ivory badge]

well, if x is in A, then x is in the left side yes?

thats how the union works

[royal holly]

no?

if x is in A

or

x is in B and c

[ivory badge]

no

x in A implies x in A u (B n C)

not both ways here

if not iff

[royal holly]

wot

[ivory badge]

A is a subset of the left side

[royal holly]

yea

[ivory badge]

so what I said is right

x in A u (B n C) iff [x in A or x in (B n C)]

if we get an iff version

[royal holly]

ohh thats what u mean

[ivory badge]

so when is x in B n C

[royal holly]

x in B n C iff [x in A or x in (B n C)] ?

[ivory badge]

A isn't involved here

[royal holly]

what

where di i say that

[ivory badge]

there is an A term

x in B n C iff ???

[royal holly]

x isnt in A

[ivory badge]

no

if x in B and x in C

[royal holly]

oh

thats what u mean

[ivory badge]

yes

you can do something similar for the right hand side

So if you get two expressions and show they're equivalent, then you should get the same set yes?

[royal holly]

so

x is in the set of A Or B And x is in the set of A or C

[ivory badge]

that is pretty much the right hand side

[royal holly]

ok

[ivory badge]

so now show the left & right side are the same

[royal holly]

thats the part i wanted help on

💀

im confused on they get this

like if x is in the set of A

then idk

how

[ivory badge]

what do you not get

[royal holly]

how does x in the set of A make x in the set of A or B and x in the set of A or C true

[ivory badge]

A is a subset of both

A u B contains A, A u C contains A

[royal holly]

oh

[ivory badge]

therefore the intersection contains A

[royal holly]

then wb case 2

how does that make it true

b and c

are not in the subset

of each other

[ivory badge]

$x\in A\cup(B\cap C) \iff x\in A\lor (x\in B\land x\in C)$

$x \in (A\cup B) \cap (A\cup C) \iff (x\in A \lor x\in B)\land (x\in A\lor x\in C)$

[vital dew]

Sharp

[ivory badge]

B n C is a subset of B and C both

[royal holly]

ok what about a?

[ivory badge]

why do we care about A

[royal holly]

how do they come up with their cases?

x in the set of A

x in the set of B AND C

[ivory badge]

they split it across that U operation

because you're in the set iff you're in A or you're in C n B

that's literally how they split the cases

[royal holly]

if ur in a or ur in a and b?

[ivory badge]

typo

[royal holly]

oh

ok then

how about this

why didnt they do

B or C

for case 2:

A or (B AND C)

x in the set of A

x in the set of B AND C

where do they get x not in the set of A from

[ivory badge]

if you're not in A you're in B n C

[royal holly]

then why not just say

x in hte set of B AND C

is it same thing?

[ivory badge]

no

because A n B n C may not be empty

so there's overlap

[royal holly]

where did u get this from

[ivory badge]

(but it ends up being the same because you have to be in that B n C anyway)

[ivory badge]

because it's not said to be empty?

[royal holly]

oh

for case 2 I could say

x in B AND C then

[ivory badge]

they're not quite distinct cases since you could have overlap

[royal holly]

what does that even mean

how does that make

a or b and a or c true

[ivory badge]

Parenthesis matter

But
Just look a bit above to see that they say let x be in the set

[royal holly]

ik but

i dont get

how it makes a U B and A U C true

idk this really confusing to me

[ivory badge]

That’s the assumption

x is in (A or B) and (A or C)

But x is not in A

It’s in there by definition

[royal holly]

so x is in b and c?

[ivory badge]

That’s what they want to prove

That’s what they figure out under that heading

[royal holly]

what about part 2

here

i get the fisrt part

when we need to prove (A-b)or(c-b) is subset of (AorC)-b

will case 1 in this case be x is in AUC

and case 2: x is not in B

[lyric quartz]

• is defined as a conjuction, not a disjunction

What about you actually try to write down the proof?

---

What kind of teachers do people have these days? I see multiple people that have multiple choice and fill-in the blanks kind of questions. What about using pen and paper?

[spiral aspen]

can someone tell me if my proof for the below question is good?
Write down a formal proof of Theorem 4.8: If a, b, c are positive integer numbers,
then diophantine equation ax + by = c has an integer solution (x, y) if and only if
gcd(a, b)|c

my proof:
LHS:
ax+by = c (given)
let d = gcd(a, b) then d|a and d|b
assume d does not divide c, then c=dq+r 0<r<d
then ax+by = dq+r
but d cant divide dq+r unless r=0, thus for an integer solution to exist gdc(a,b)|c

i still need to prove the other way around but is this one good?

other way around would be
gcd(a, b) | c (given)
then (ax+by) | c => c = (ax+by)*m = a(xm) + b(ym)
so there exists an integer solution.

since the gcd | c, gcd | a and gcd | b

[severe edge]

Hello,
aren't questions 1 and 3 equivalent?

[coral parcel]

Yes, pretty much.

[severe edge]

So in the first one:
Let G(V, E,f) be a graph, let V be a set of vertices V={1,2,3} and E set of edges E={a,b,c}, and a function f: E to V (f assign element from E to two elements in V)
f(a)={1,2}, f(b)={1,3}, f(c)={2,3}
Let V'={1,3} (subset of V) and E'={a,c} (subset of E)
f' is the restriction of f with respect E and V, thus, f'(a)={1,2}, and f'(c)={2,3}
however, G'(V',E',f') is not grap because 2 isn't in V'

is this correct?

[indigo rapids]

can someone tell me how i would go about writing this in closed form?

cuz i think there might be a type cuz ive no idea haha

[elder berry]

u're summing 2 n times, rather $\underbrace{2+2+\ldots+2}_{\text{$n$ times}}$

[vital dew]

peaceGiant

[indigo rapids]

ahhh that makes sence that youuu

[indigo rapids]

Let j
be even. Evaluate 2+4+6+⋯+j=

how do i evalute j?

i thought it would be like j(j+1) but its not

[coral parcel]

You're supposed to write an expression that receives j as input and gives the sum as output.

So "evaluate j" is not something you're supposed to do -- you can assume someone already know how to do that, but what should they do then?

[vivid gust]

does anyone understand modular arithmetic and can help me out

[little prism]

ask an actual question and someone might come in and help you

[spiral aspen]

Let k be a fixed positive integer and let G = (V, E) be
a loop-free undirected graph, where deg(v) 2: k for all v E V.
Prove that G contains a path of length k.

is this correct?
start at v1, you have k incident edges that you can use for a walk, then for v2, v3, ..., vk you have k-1 incident edges that can be used (except the first), thus a path of k exists.

[ivory badge]

what does 2: mean

[spiral aspen]

sry the copy pastng was bad

ill take a screenshot instead

[ivory badge]

Unless I'm mixing some wires up here that should work?

this question feels very weird to me though

[spiral aspen]

thanks! what about this one? i am kind of stuck on how to approach this

should i split it to cases?

case 1: all have even degree

case 2: there are some with odd degree?

[ivory badge]

couldn't you get a k path just from deg(v)>=2?

[spiral aspen]

that depends on the value of k

if k <= nr of vertices yeah that would work

[ivory badge]

well how do you draw a loop-free graph with deg(v)>=2

do you know that |V| is finite? I forget graph conventions

[spiral aspen]

if its exactly 2 then sth like this right? and i think it assumes V is finite

[daring pawn]

can anyone explain to me how you go about decrypting a hill cipher generally?
(for mod26 a-z, n block length (unsure if size matters for this), and a plaintext (unsure if size matters for this, either)

very new to the field and did not understand the given explanation
how do you go about obtaining a key, and how do you apply said key to encrypted characters?

[spiral aspen]

so if k <= nr of vertices this would work if deg(v) = 2

[ivory badge]

but that ain't loop free yeah?

[spiral aspen]

it is. its a cycle but its loop free

loop free just means a vertex doesnt loop to itself

[ivory badge]

I hate graph terminology

ok |V| is finite and it's connected

deg(v)>=1

and clearly deg(v)<|V|

I'd say <= but no immediate loops

Is this a sufficient hint?

[spiral aspen]

im assuming this is for the second question i sent right?

[ivory badge]

yes

[ivory badge]

If I make a bad reading of bad graph language lemme know but I'm pretty sure 1 <= deg(v) < |V|

[spiral aspen]

yes thats true

ill attempt it from here

[ivory badge]

it should be 1 step from there

*size of step may vary

[spiral aspen]

ohh

pigeonhole principle?

[ivory badge]

ye

[spiral aspen]

ahhh i see

[ivory badge]

|V|-1 holes at most

L

[spiral aspen]

yeah and since we have V vertices one of them will have the same degree

makes sense thanks!

[ivory badge]

I hate that loopfree is not acyclic tho

[spiral aspen]

yeah i agree, this terminology was confusing for me as well

[indigo rapids]

would j(j+1) not be right then?

well, it says it isnt but idk why its not

oh wait

times 2

no divided by two

bro ive no idea

hahaha

j = 2n

and to get the sum from 2+4+6+...+2n = n(n+1)

so

[coral parcel]

That looks righter.

[manic frigate]

What would be the minimum and maximum of No. 2

[indigo rapids]

^^ can someone tag me if they have the answer to avaj also please

[wicked furnace]

pls help me this #help-0 message

[spiral aspen]

can someone verify my proof:
Let T1, T2 be 2 spanning trees with (V1,E1) and (V2, E2) respectively and there exists an edge ei in E that is in E1 but not E2. Since both are spanning trees, an edge ei' must also exist in E2 but not E1.
All edges have distinct weights meaning that either ei or ei' have higher weight. A minimum spanning tree will always include the lower weight thus there can only be 1 minimum spanning tree.

[ivory badge]

Mind reminding me what a spanning tree is before I start thinking it means something in line with normal interpretations

[spiral aspen]

each vertex is connected and there is no cycle

[ivory badge]

Well the argument you make seems to be insufficient for if you have multiple changes in edge between them?

[spiral aspen]

what do u mean?

im only replacing the higher edge with the lower edge

[spiral aspen]

what?? dont these 2 contradict each other?

corollary 13.3 why is it <= ? shouldnt it be instantly equal?

maximum flow = minimum cut

[cloud dirge]

Five cards are dealt off of a standard 52-card deck and lined up in a row. How many such lineups are there in which all the cards are of the same suit?

What do they mean by suits

[vale cairn]

The suits are the like classes of cards (clubs, spades, hearts, diamonds)

[outer kayak]

would anyone be willing to tutor me in discrete? ive been having trouble with this class for a while.

[floral forge]

Can anyone help me w this

[ivory badge]

When is the original statement true

[floral forge]

if u do one or the other

[meager mural]

"The difference of the squares of any two consecutive inte-
gers is odd." If I'm to prove this universal statement, do I use the direct proof method?

[vale cairn]

Sure yes

[meager mural]

ok see thats what i dont understand about the direct proof method, since this is a universal statement, if i prove it to be true for lets say (a = 24 and b = 25) how can i prove it for to be true for all the integers? do i just assume it's true if one part is true?

[vale cairn]

You can't prove something is true by taking a single example

But you can do things like "Let n be an arbitrary integer. Then ..."

[meager mural]

but the directions say to take 1 particular but arbitrarily element and prove it for both P(X) and Q(X) (consecutivity and a^2-b^2 = odd)

[vale cairn]

Yes, that isn't just taking a single example if the number is arbitrary

This proves it for all x, whereas what you said was proving it for some x

[meager mural]

ur saying my example where a =24 and b =25 is proving it for some x?

[vale cairn]

yes

well

Obviously necessary changes must be made since you're talking about two things but ygm

[meager mural]

ok i don't understand. i followed the steps. i supposed a = 24 and b = 25 which is true for P(x) (consecutivity) and then i proved it for Q(x) which equals -51 which equals odd since 2(-24)+1 is odd.

is that not a proof of the statement? what else would i need?

[vale cairn]

Note that this document says arbitrarily chosen

Perhaps you're misunderstanding what is meant by that - it doesn't mean you can arbitrarily choose them, it means you can take any consecutive integers a and b and then show the statement holds for them

Otherwise you can prove that every integer is less than 10 by saynig 9 < 10, for example

[ivory badge]

Basically you need to prove it in a way that doesn’t rely on the specific value of x

[meager mural]

so ur saying i have to prove a^2-b^2 = 2(k)+1 without plugging in any numbers?

[ivory badge]

You know f(x)=mx+b? You substitute in 2 for x and get 2m+b

Similar principle, you want to be able to substitute in any value and still get a proof

[meager mural]

but i can though like 54 and 55 works as well

[ivory badge]

It works for all of them but you have to prove it

You gotta basically have a function that sends x to a proof that (x+1)^2-x^2 = 2k+1

[meager mural]

hmm i get it now. since its consecutive its even and odd and vice versa, so i should just substitute the definitions of even and odd into the a^2-b^2 right?

[ivory badge]

It’s consecutive so a=b+1

You don’t even need even odd there

Just evaluate that

[meager mural]

wow ur right. but i can use even and odd right. it just takes more work

[ivory badge]

Since you have no idea which is even or odd, you’re better off just running (b+1)^2 - b^2

So calculate that out

[meager mural]

ok thx. also say i get a universal statement and i need it to find out if it's true or false. do i begin with finding the proof or finding the counterexample?

[ivory badge]

If you can recognize something that makes it false that’s a counter example

But it’s hard to say how to do it in general

[meager mural]

yea but what about equations that is complex so it's know if it's true or not. do i just start with proof?

[ivory badge]

Just look at it and see if you can find a way

[toxic hollow]

Determine whether ∀x(P(x) ↔ Q(x)) and ∀xP(x) ↔ Q(x) are logically
equivalent. Justify your answer.can anyone help me with this problem?

[lyric quartz]

In the second, is the right x a free variable?

[toxic hollow]

yeah

[coral parcel]

So the truth value of the second one can vary according to what x is.

Is that also the case for the first formula?

[tight latch]

I need help on my Discrete, will anyone help me?

I don't quite get it...

[coral parcel]

Those pictures are quite hard to read. Do you have them in a better resolution?
But just as importantly, can you give a more specific description of what confuses you than just two text heavy images where readers have to guess what you're stuck on?

[tight latch]

Is it necessary for me to dry run these algorithm?

here you go @coral parcel

[coarse crane]

hi all i got a problem

we are given the inequality x1>x2<x3>x4<x5>..... upto kth variable xk, my question is how many ways can this inequality be written correctly in the form a<b<c<d<....

[coral parcel]

If it's not immediately clear to you how the algorithms work, dry-running could be a good way to try to build some intuition.

[tight latch]

what do you mean?

[livid minnow]

Does anyone know what is meant by the use of both : and |

Do they both mean “such that” in this case?

[coral parcel]

This looks hard. Do you have evidence that there should be a simple answer?

[coral parcel]

The colon here seems to belong to the ∀x; it serves to delimit the set x ranges over, from the property all x should have.

[livid minnow]

oh I see, that would make sense in this context

thank you

[coarse crane]

i got for some inital values

say we have x1>x2<x3 then we get 2 combinations like x1<X2<x3 and x3<x2<X1

for x1>x2<x3>x4 we have 5 combinations

for uptil x5 we have 16 combinations

so i wanna generalise for x_k

[coral parcel]

If you can compute 4-5 nontrivial results by brute force you can try typing them into OEIS and see if anything pops up there.

[coarse crane]

WHATS oeis sorry i dont know

[coral parcel]

Ah, 2, 5, 16 was enough to find https://oeis.org/A000111 as the first hit!

[coarse crane]

for x6 i did get 61

!!!!!

[coarse crane]

hey the site seems complicated may i know where the exact formula is written?

[coral parcel]

The OEIS entry doesn't look like any nice closed formula is known.

The best it has to offer seems to be some recursive formulas that are not themselves particularly nice.

[coarse crane]

https://www.geeksforgeeks.org/euler-zigzag-numbers-alternating-permutation/

[coarse crane]

does this seem right?

[coral parcel]

Ah yes, that hid in the wall of text from OEIS too:

2*a(n+1) = Sum_{k=0..n} binomial(n, k)*a(k)*a(n-k).

[coarse crane]

thanks a lot sir

[coarse crane]

got to know about this incredible site !!

[vocal pendant]

I understand fourier tranformations in continuous time very well, but now im taking a discrete class where the discrete fourier transformation appears, and I am very confused. Does anyone have helpful resources to understand DFT, DFS, DTFT? Also exercises if possible

[worn cipher]

Can power sets have their own subsets?

I understand the power set is the set of all subsets but those subsets are considered elements

[brave rock]

Yes

You can take the power set of a power set

You can even take the power set of a power set of a power set

[novel ore]

does an equivalence relation always partition a set into equivalence classes of equal cardinality?

[vale cairn]

No

There's actually like

A bijective correspondence between partitions of a set and equivalence relations on a set

So you can get any partition you want

[novel ore]

hm, so in the proof of lagrange's theorem (sorry i know this shoudl be in abstract algebra but regardless) don't we have to assume that a given equivalence relation partitions a group G into cosets of equal size? and how would we prove that?

[vale cairn]

(Just take your partition of the set and say x ~ y iff they're int he same subset)

[novel ore]

oh okay

[vale cairn]

In Lagrange's theorem you can just show that all the cosets are the same size

H is the same size as gH - can you see a bijection H -> gH ?

It should be clear if you think about the definition of gH

[novel ore]

sorry i'm struggling to see how that shows that all cosets are the same size, doesn't that only show that a subgroup H of G and its coset are the same size?

[vale cairn]

well all cosets are of the form gH for some g in G

So if all the cosets are the same size as H, then all are the same size

@novel ore

[coral parcel]

"A subgroup and its coset" sounds like that's the root of your misunderstanding.
There's not one coset associated with each subgroup, but many. And all the cosets of each particular subgroup have the same size.

In Lagrange's theorem, you fix one particular subgroup H, and all the various cosets of that subgroup then partition G. These cosets have the same size, because each of them has the same size as H.

[vale cairn]

Good catch Tropo

[novel ore]

ohhhh, okay that makes a lot more sense, thank you!

[novel ore]

oh ok gotcha

thanks guys!

[gloomy pelican]

Hi ! Can anyone explain to me why this is true?

Thanks.

[manic frigate]

Can someone explain how you get the right from the left?

[brave rock]

If you know certain values of cos and sin, you can simply use the fact that e^i*x = cos(x) + i*sin(x).

[lucid charm]

i'm currently doing set theory and i have to prove or disprove using counterexample

how would i go about doing that

[lyric quartz]

Have you drawn a diagram?

[lucid charm]

yes

and i know that its false from it

but i just dont know how to use counterexample to prove it

[lyric quartz]

Pick an element that is either on the left or right, but not in the other

Can you show the diagrams?

[wise nexus]

the diagram, if correct, should be a counterexample, no?

just say "consider these subsets of R^2" or some shit lel

[rain mauve]

Let $f: \mathbb{R}^n \setminus {0} \rightarrow R$ be a continuously differentiable function that is homogeneous of degree $\alpha$. Show that $f$ can be expanded to a continuously differentiable function on $\mathbb{R}^n$ if $\alpha > 1$.

In a previous question I showed that the ith derivative $D_{i}f$ of $f$ is homogeneous of degree $\alpha - 1$, and there is a theorem in the syllabus I was provided that says $f$ can be expanded to a continuous function on $\mathbb{R}^n$ for $\alpha > 0$. But I'm still having trouble formulating a proof.

I assume it has something to do with the homogeneity of the derivative of f, could someone please help?

[vital dew]

O2daP

[slender crest]

How do you describe this RE: baba ?
I know what it allows but cannot figure out how to explain

[coral parcel]

Do you have a bad explanation?

[worn cipher]

If one of the elements of a Power set of A (P(A)) is for example, {a}, would {{a}} be a valid subset of this power set?

[brave rock]

Yes

[worn cipher]

Would the pattern also continue for a subset of {{a}}?

Like the subset would be {{{a}}}

[brave rock]

No

Let's simplify what you're saying

if x is an element of a set X, then {x} is a subset of X

you specific example sets X = P(A) and x = {a}.

{{x}} is not a subset of {x} since {x} is not an element of {x}.

[worn cipher]

Oh alright I see

Also for a question like this, ( ) and { } aren't interchangeable for Cartesian products right?

(a,b) != {a,b}?

[vale cairn]

Uhhh this is probably gonna have to be a mistake

[brave rock]

Without more context it's hard to say whether or not it's a mistake

It could be a trick question

But indeed, () and {} are not interchangeable.

[vale cairn]

maybe if this is like a specific construction of cartesian products lol

but i doubt that

can we see the context

[worn cipher]

My bad only saw this now

@vale cairn @brave rock

I put down false

[brave rock]

Well then it was indeed a trick question :)

[worn cipher]

Yep

[vale cairn]

Ah okay lol

This is a good question actually imo

:)

[fathom lark]

{2023} ⊆ {{2023}}

Would this be true?

[ivory badge]

Is every element of the left an element of the right?

[fathom lark]

i mean

kinda

on the right its a nested array

containing the same element

[ivory badge]

I don’t care about kinda here

[fathom lark]

alrights thanks man

[ivory badge]

Is 2023 an element of the left?

And is 2023 an element on the right

If not, it’s not

[idle wave]

Let $P_{2,1}$ be the set of lattice paths with two types of steps: 2 units up or 1 unit right. Find the number of paths in $P_{2,1}$ from $(0,0)$ to $(2n,2n)$ that are never below the line $y=x$.

I realize that when we're dealing with regular lattice paths it's just the Catalan Numbers, no idea how to approach this one though. Tried to create a recurrence relation and it became ugly very quickly.

[vital dew]

TheUnTamed

[leaden ibex]

Hey guys, I'm really struggling with my school's discrete math and proof class, so I'm just wondering if you guys can recommend a question bank with solutions for discrete math and proofs. While the textbook my class is using has questions and solutions, they just aren't hard enough for the exam...

[north cargo]

could some1 help me? im not sure how to tackle these problems

[idle wave]

Remember that $f(x) \in O(g(x)) \iff \exists x_0 > 0,C \text{ s.t. } \forall x \ge x_0,, f(x) \le C \cdot g(x)$.

[vital dew]

TheUnTamed

[spiral aspen]

can i get some help with this?

so im trying to prove the first part so proving that f(e) = c(e) while assuming the before is true

will this be of any use?

[hearty elk]

Solve the recurrence relation subject to the basis step. Wondering if this looks correct. TIA. ❤️

[spiral aspen]

Its same question so hope tagging <@&286206848099549185> is fine.

Can someone verify if my proof is correct?

Part (1)

Part (2)

[meager mural]

can someone help explain this case to me. This is to prove -|r| <= r <= |r|. I understand the absolute value definition and how |r| = -r if r < 0. But I don't understand where we get -1 from and what he is multiplying

[rancid relic]

I think theyre just multiplying both sides of the equation by -1 to prove the fact?

[meager mural]

by the equation u mean -|r| <= r <= |r|?

[rancid relic]

no

-1 * |r| = -r * -1

The equation they were talking about in the previous sentence

[meager mural]

so u mean the one i wrote. i don't see any |r| anywhere else

[rancid relic]

Wait where's the question and where's what you wrote 😭

[meager mural]

this is a proof within the textbook. the question i asked up there

[rancid relic]

They give the equation: |r| = -r
They multiply both sides by a scalar, -1, keeping it consistent to get the equation: -|r| = r

they got the equation from the fact that r being negative, taking the absolute value of it is the same as negative-ing it

sorry i may not be understand the question 😬

[meager mural]

oh i get what u mean now.

[obtuse lance]

it might help (or be confusing) to pick a number like r=-2

|-2|=-(-2)

[ionic tulip]

Any applications for a graph with any number of vertices but no edges?

[brave rock]

So a set? Yeah I can think of a few places where sets are useful lol

[vale cairn]

Like what

[indigo rapids]

what is a quick way of donig (15C2)+(15C3)+15C4)+(15C5)+........+(15C14)+(15C15)?

[obtuse lance]

(1+1)^15-(15C0)-(15C1)

[indigo rapids]

where are you getting (1+1)^15 from?

[indigo rapids]

the answer to this is 7^12, but im not sure how

this is the explanation it gives, but im still not understandding it

could someone explain it for me please in different words

[coral parcel]

If you expand (1+1)^15 with the binomial theorem, you get exactly all the terms in your sum, plus just a few extra.

[indigo rapids]

ahh ok hahaha thank you XD

that was straight forward actually now that you say haha

[coral parcel]

A "way" can be described with a list of 12 numbers between 1 and 7, saying which envelope each of the 12 cards go in. Each such list describes a "way", and two different lists count as different "ways", so you're really just counting those lists.

[indigo rapids]

ohhhhh so you need to use up all the cards

so fill the envelopes such that you have no cards left in the end

and they could potentially all go into on envelope?

[coral parcel]

Yeah, that would be my immediate interpretation.

[indigo rapids]

ahhhhh that makes sense now

legend

thank you so much hahaha

[indigo rapids]

given the following:, how would i compute lets say $f^3$?

[vital dew]

MildCurry

[last sigil]

What is f^3(1)

This is 3 iterations of f

[indigo rapids]

if we wrote it in disjoint cycle notation, then we'd have:

f = (128)(35)(79)

so f^2 would be:

f^2 = (128)(35)(79) (128)(25)(79)
??

which would simplify to:

(97)(53)(28)(12)?

but then theres two 2's

uhhhh idk

[regal ice]

if there are 100 cities between city A abd city B,
In how many ways can you travel from city A to city B without visiting any city twice?

[wicked bolt]

very confused, what is a "way"?

[open meadow]

find shortest path in the given graph using dijkstra shortest path algorithm but they haven't given the destination vertex ?

its a university question

or do i just draw the shortest path tree for all vertices at the end

[obtuse lance]

if I had to pick one to do, I'd probably find the shortest path from 1 to 5, since those are source/sinks

[vocal pendant]

Could someone verify if I calculated the DFT correctfully?

Would appreciate it alot

[vocal pendant]

@ me if u respond 😄

[hexed shore]

I would i proceed to find a RR of a_n = n^2

[nimble pond]

Let G = (V,E) be a graph. A subset C ⊆ V is called a vertex cover C of G if every edge in G has atleast one endpoint in C. Consider the following 2 problems.

MinCover:

Input: A graph G = (V,E)

Output: A vertex cover of G of minimum cardinality, i.e., a Vertex cover C of G such that |C| is minimum among all vertex covers of G.

VCover:

Input: A Graph G = (V,E) and an integer k.

Question: Does G have a vertex cover of size less than or equal to k?

Prove that VCover is in P iff (if and only if) MinCover is solvable in polynomial time

Guys help with this proof please.

Im quite stumped

[agile magnet]

have you ever seen a proof like this?

like have you ever seen an NP-reduction proof or something along those lines?

[light ginkgo]

^^

[agile magnet]

cause if you have NEVER seen one, I can give some resources and such, but if you have then I can maybe help you with this

[nimble pond]

I have seen one proof which was done in class

I went along the lines of proving one problem as a instance of another

an*

[agile magnet]

for this vertex cover question?

[nimble pond]

no

[agile magnet]

ok all good

[nimble pond]

for a different one

[agile magnet]

so I can help you with one direction

and then you can try the other one your own

[nimble pond]

yes please

[agile magnet]

so the idea is we are going to use one problem as a polynomial time blackbox to solve the other problem

[nimble pond]

what is a pt blackbox

[agile magnet]

so like a polynomial time blackbox for MinCover will take in an input graph G = (V,E) and output the minimum cover

it'll do it polynomial time

and it's a blackbox meaning you have no idea how it does it

but just that it does

[nimble pond]

yes got it

[agile magnet]

so lets pretend you have a pt blackbox for MinCover. Can you come up with a polynomial time algorithm to solve VCover given a graph G = (V, E) and an integer k?

[nimble pond]

find all possible covers

[agile magnet]

that's not poly time

there could be exponentially many covers

[nimble pond]

aah

[agile magnet]

so your algorithm should be poly time, assuming you have access to this black box

[nimble pond]

hmm

[agile magnet]

which you do for this direction of the proof (we're proving MinCover is solvable in polynomial time implies VCover is in P)

[nimble pond]

okay

ok let me come up with a pt algo

[agile magnet]

use the blackbox, your algorithm won't be pt if you don't use the blackbox

[nimble pond]

a few mins please

[agile magnet]

ya take your time

[nimble pond]

How does this look

[agile magnet]

kinda confused here

Ok can you give me a high level english explanation of what your algorithm does

[nimble pond]

Yes

[agile magnet]

I want to solve VCover

I give you a graph G = (V, E) and an integer k

what does your algorithm do, in english

[nimble pond]

Ok so I make an array of all zeroes on the size of V

[agile magnet]

what does this array represent?

[nimble pond]

Initialize all of it as 0s

[agile magnet]

no no but what are you going to use it to track

like what is it's purpose?

[nimble pond]

To track the vvertices not in the vertex cover

[agile magnet]

ok

[nimble pond]

so i'm using the blackbox algo now and if it is a vertex cover i'm swapping out the 0s in V with 1

then i'm incrementing a counter c for every 1 in V

[agile magnet]

if what's a vertex cover?

[nimble pond]

Yes

[agile magnet]

that was not a yes or no question

so i'm using the blackbox algo now and if it is a vertex cover i'm swapping out the 0s in V with 1
what is "it" in this sentence?

[nimble pond]

if the Vertex is not a vertex cover>

[agile magnet]

if that lone vertex is a vertex cover?

[nimble pond]

yes

[agile magnet]

that doesn't work

[nimble pond]

why so?

[agile magnet]

a single vertex may be part of the vertex cover

but not make up the whole vertex cover

[nimble pond]

aah

[agile magnet]

so you'll never increment

ok ok what does the black box we have give us?

[nimble pond]

it returns a subset C with contains the vertex cover of G

[agile magnet]

not just contains, it is the vertex cover

[nimble pond]

Yes

[agile magnet]

ok so we can get a vertex cover

how can we use that to solve VCover?

[nimble pond]

how about setting a lower bound and upper bound and doing a binary search on the possible values?

[agile magnet]

we don't really need that

VCover is asking "does a vertex cover exist of size <= k" right?

[nimble pond]

yes

[agile magnet]

and you have a way of finding the minimum cover right?

via the black box?

it's black box for MinCover

[nimble pond]

no but we dont have it right?

ok nvm

[agile magnet]

what?

you do have the blackbox

[nimble pond]

MinCover is the blackbox

[agile magnet]

that's what we're assuming for this direction

yes

[nimble pond]

yes got it

[agile magnet]

so you can find the smallest cover

got it? give me a new algorithm then

[nimble pond]

wait

if

smallest cover is greater than k

then we dont have one

[agile magnet]

and if the smallest cover is <= k?

[nimble pond]

we have what we want

[agile magnet]

perfect

see how that's an algorithm to solve mincover?

[nimble pond]

VCover?

[agile magnet]

right

vcover my bad

[nimble pond]

yes

[agile magnet]

ok so now try the other (admittedly harder) direction on your own

you have a black box for vcover

try to find the mincover

[nimble pond]

yes

hold on

I can brute force again but it wont be in poly time

[agile magnet]

yea so you gotta use the black box

[nimble pond]

Yes

I cant think of a way similar to how we find VCover with MinCover

[agile magnet]

well we want to build it a vertex at a time

since we want the actual cover itself

so try to think of way to tell if some given v in V is in the cover or not

[nimble pond]

ok so i'm doing this again but a binary search on 0 to |V|

Will that work here?

[agile magnet]

not quite you want to actually build the cover

not just find the size

[nimble pond]

Ok I cant really think of a way

any tips on how I can proceed

[agile magnet]

what happens if you remove a vertex from the graph?

[nimble pond]

It depends on the vertex right

If it only has 2 edges it dis joins the graph?

Might*

@agile magnet

[agile magnet]

Hint 1: First find the size of the minimum vertex cover (this is where your binary search idea would come in handy, or just linear scan doesn't matter)
HInt 2: Using this, pick a vertex and remove it. What do you now know if the remaining graph now has a smaller minimum cover size or the same minimum cover size?

[nimble pond]

If it has the same min cover, then its the part of the vertex cover. Else its not.

[agile magnet]

why?

also what's it?

[nimble pond]

It is still VCover right

[agile magnet]

also I think you have something slightly off?

draw some examples out yourself

examples are good, drawing is good

[nimble pond]

okay

Wait just tell me this, If i keep removing vertices until I reach the size I found in Hint 1 using the search, will that be MinCover using Vcover?

[agile magnet]

no

[nimble pond]

okay

Hey sorry but I'm still not getting it

@agile magnet

[kindred sand]

Assume VCover is in P. Then you can find mincover in O(n) iterations of Vcover by checking from 1 -> n and finding the first yes.

Assume mincover is in P. Then you can answer Vcover in O(1) iterations of mincover by comparing k and size of mincover

[nimble pond]

Like iterationg from 0 to |V| and using mincover?

[kindred sand]

no here you're proving mincover is in P if Vcover is in P. So you're using Vcover a polynomial number of times to find the answer for mincover

repeating a polynomial time algorithm a polynomial number of times is still a polynomial time algorithm

[nimble pond]

Yes I understand that, but we have MinCover as an algorithm, meaning it will give me a result.

But VCover is given as a question

[kindred sand]

Vcover is a decision problem where the result is true or false

[nimble pond]

Yes

And I need MinCover to get that result

[kindred sand]

yeah. if the min cover is k then vcover is true for all n>=k

otherwise false

[nimble pond]

Yes

[kindred sand]

So what's the confusion?

[nimble pond]

how will calling VCover a number of times give me MinCover

[kindred sand]

it has to be at least 0. so start with 0 and keep increasing by 1 until you find the first true. that number is your mincover answer

[nimble pond]

aah that makes sense

but let me get one mroe thing clear as well

VCover inherently uses MinCover

to get its answer right

So will that be a valid approach

[kindred sand]

not necessarily. If you know mincover it's trivial to know vcover. That doesn't mean the actual algorithm involves finding mincover first then evaluating vcover

[nimble pond]

So I assume I know mincover

[kindred sand]

The question simply asks you to prove that these two problems fall in the same class if one of them belongs to P

[nimble pond]

Yes

[kindred sand]

if P was replaced by constant time it would not be true

[nimble pond]

because they cant be solved in constant time

[kindred sand]

not for that reason

[nimble pond]

then?

[kindred sand]

there is no known solution for polynomial time as well actually

but if vcover were constant time, there is no proof that mincover is constant time because it takes a polynomial number of iterations of vcover

the other way around works

Ig that's what you were asking

[nimble pond]

no no i wasnt asking that

its fine

ok let me get this

I can prove MinCover is solvable in poly time by writing a poly time algorithm for it

[kindred sand]

that would be proof but no such algorithm has been found

[nimble pond]

so how else do we prove it then

sorry

I really dont get this stuff

[kindred sand]

Basically this is the P=NP question. They are complexity classes

[nimble pond]

but they cant be proved right

[kindred sand]

If you have a P algorithm and you use it a polynomial number of times to get the answer for another algorithm, the other algorithm is also in P

[nimble pond]

Yes

that makes sense