discrete-math

[paper parrot]

~Ex ~(~B or A(x))
this part is right

Is this the same problem?

[opaque prawn]

which part is that

[paper parrot]

That's the correct way of switching it from a universal statement in step 2 into an existential statement

If that's what you're trying to do

[opaque prawn]

Ohhh, so that's the correct way

yes that's what i'm trying to do from step 2

[paper parrot]

And then you could change ~(~B or A(x)) into ~(B -> A(x))

idk what you're trying to do though

[opaque prawn]

wait

[paper parrot]

no idea what you're supposed to do

this just seems like an axiom tbh

[last timber]

Suppose RHS is false

that is B is true and exists x such that not A(x)

but then that gives that existxs x such that B is true and A(x) is false

this shows-> by contrapositive

converse is similar

[blissful zenith]

can someone please help me expand the left side

ive been asking in here for a few days

[lofty cloud]

From

#❓how-to-get-help

Rule 4

If your question has not been answered for a minimum of 15 minutes, you may use the Helpers tag once. Please do not try to bump your question using this ping unnecessarily. Do not abuse this ping. Do not individually ping users with the Helpers tag without their express permission.

[blissful zenith]

<@&286206848099549185>

can anyone please help me

[blissful zenith]

././.

bump

[errant bear]

you could try just applying the definition of n choose k, with the factorials

[blissful zenith]

i figured it out

[bright spire]

f

[nimble glade]

Does somebody know how to do 1b and 1c

[minor dagger]

use induction

show that the inductive step is divisible by 2

for b

[errant bear]

what

[zealous dirge]

can anyone help me with this question, cant figure out how to do it. thanks

[faint narwhal]

What have you thought about?

[prime parcel]

@zealous dirge put the values in n

[zealous dirge]

which values? 2, -3 and 1?

@prime parcel

[burnt nebula]

Hi everyone, Hope u all doing great 😊 i've got a small question: what is the number of symmetrical and antisymmetrical relations on a set of n elements?

[prime parcel]

Yes put them one by one

[zealous dirge]

im not sure what you mean by that

[last flicker]

I think sam wants you to write out each set for n=2, -3, 1, 0

[zealous dirge]

ohh right

how would i write them out tho,

@last flicker

could you give an example? that would help

something like this, right?

[prime parcel]

@zealous dirge yes

There are 2 elements in 1st

And 1 element in 3rd

[zealous dirge]

yup thanks

@prime parcel

[stray reef]

man

those curly braces

[pallid belfry]

Can someone explain to me what the difference is between a selfish set and a minimally selfish set?

I understand that a selfish set is a set that contains its own cardinality in it. So like if {1, 2, 3} would be selfish because it has 3 elements and there is the number 3 in there right? But I am not sure what a minimally selfish set is

[stray reef]

uh

i'm hearing about these terms for the first time

do you have the definitions for both? @pallid belfry

[pallid belfry]

I do not have definitions for the minimal selfish set @stray reef

This is what me professor emailed me about it but it doesn't help me at all

[stray reef]

you don't have the definitions???

[pallid belfry]

Nope

Looked everywhere in the textbook

[coral raven]

nothing on wikipedia

[stray reef]

then how the FUCK is anyone supposed to know what a selfish set or a minimally selfish set even IS?

did this come up in an assignment?

[pallid belfry]

I even looked it up online

but nothing

ues

yes

[stray reef]

does the assignment give any definitions for it?

i'm pretty sure it's an ad-hoc thing

[pallid belfry]

Here is the assignment

[stray reef]

SEE

[coral raven]

oh well there we go lmao

[stray reef]

SEEEEEEEE

and you said you didnt have definitions

when you very clearly do

clearly written there

[candid pier]

lol

[pallid belfry]

rip

im blind

[stray reef]

though i am tempted to say a statement is missing from the defn of a minimally-selfish set

maybe?

because it looks to me like minimally-selfish does not necessarily imply selfish.

[pallid belfry]

So for a proper subset. All elements of the proper subset must be in the original set right

[stray reef]

no, what you said is the definition of a subset

not a proper subset

a proper subset is a subset that isn't equal to the original set

``A is a proper subset of B'' is sometimes denoted as $A \subsetneqq B$

[vital dew]

Ann

[coral raven]

ew

[coral raven]

just remove the bottom line

[pallid belfry]

So this is not the definition of a proper subset?

[stray reef]

what you posted it

what you said earlier isnt

details matter

and youre omitting one

[pallid belfry]

So in the def I just posted. B is a proper subset of A because it is not equal to the set A?

[stray reef]

yes

[pallid belfry]

So what would be the difference between just a subset and a proper subset then?

They seem the same to me

[stray reef]

any set is a subset of itself

but not a proper subset of itself

thats the difference

a proper subset must always exclude something from the parent set

[pallid belfry]

ohh

okay

that makes sense

[stray reef]

i can immediately see if |A| = n and A contains an element less than n then A will not be minimally-selfish

[pallid belfry]

Could you give an example of that? I am having some trouble following that statement

[stray reef]

A = {5, 6, 12, 33, 52, 2342, 3456, 86325, 2394852395, 234234291891} is not minimally-selfish because it contains a selfish subset, for example {5, 2342, 3456, 2394852395, 234234291891}

n=10 here and the "element less than n" i'm using as an example is 5

i'm kind of giving away the idea behind the proof i came up with for the claim

okay there are two possibilities here: either i stumbled into a necessary & sufficient condition for minimal selfishness, or i've confused myself beyond recourse.

[pallid belfry]

lmaooo

What I am understanding is that a set with a selfish set cannot be minimally selfish

based on the example you gave

[stray reef]

"a set with a selfish set" what

[pallid belfry]

oh

hold on

[stray reef]

a set with a selfish SUBSET can't be minimally selfish because thats literally the defn of minimal selfishness

a minimally selfish set is a set for which all proper subsets are non-selfish.

(notably, it doesn't mention that a minimally selfish set necessarily has to be selfish. if it does, the story changes drastically.)

[pallid belfry]

Well then wouldn't every number for n have at least 1 selfish subset so then none of them can be minimally selfish

[stray reef]

what

what are you talking about

[pallid belfry]

If a set has a selfish subset, then it cannot be minimally selfish. But I cannot think of an example where a set would not have a selfish subset.

[stray reef]

a selfish proper subset, mind you.

for an easy example of a set like this though?

{100, 200}

its only proper subsets are ∅, {100} and {200}

none of which is selfish

[pallid belfry]

So then that would mean that {100, 200} is minimally selfish?

[candid pier]

I'm getting a fibonacci sequence

assuming "minimally selfish" also has the condition of selfishness

[stray reef]

yes

taking the definition given by your prof literally

[candid pier]

yeah that doesnt look right. i'd assume minimally selfish also means selfish

[stray reef]

it doesnt say

honestly at this rate i'd email the prof again

to ask whether they meant for the defn of a minimally-selfish set to require selfishness or not

[weary tiger]

i dont understand what this is saying

are a and b supposed to represent 2 elements from the set A

that a ∼1 b∧a ∼2 b is confusing me

[candid pier]

which part? the symbols themselves?

~1 and ~2 are two equivalence relations. and we're defining a third relation, ~, to mean the conjunction of both ~1 and ~2. is ~ also an equivalence relation?

[weary tiger]

okay putting it that makes it easier to understand

so im pretty sure its reflexive and symmetric, idk how to prove transitivity

does a~b if a ∼1 b ∧ a ∼2 b mean that as long as the intersection is not empty that a~b?

[candid pier]

i broke it down like this
a~b ∧ b~c -> (a~1b ∧ a~2b) ∧ (b~1c ∧ b~2c)

or equivalently
(a~1b ∧ b~1c) ∧ (a~2b ∧ b~2c)

from there you can derive transitivity from the equivalence relations ~1 and ~2, so you'll prove a~1c and a~2c

[candid pier]

did you want some more detail?

[weary tiger]

no that makes sense.thx

[quartz cedar]

Just have a quick question on A,
So im not sure I did this correctly but I got

∀xF(x)->Q(x,F(X))

I know this is incorrect, but my reasoning was like, for all footbal teams, if there is a football team, then theres a quarterback of the football team

[weary tiger]

you can say that for every footbal team there exists a person that is that team's quarterback

[quartz cedar]

thing is ive no idea how to write that

Cause I didnt know how to write "For every football team" originally

thats why i wrote it like that

∀yƎx(Q(x,y))
????

[fallow pawn]

anyone know how to proof this

[rotund frigate]

write them out as fractions and cancel out what you can

[proven shard]

Also you can think about this combinatorialy

The LHS counts the number of ways you can choose h objects from a collection of n, and then k objects from the n-h remaining.

The RHS counts the number of ways you can choose k objects from a collection of n, and then h objects from the n-k remaining.

[fallow pawn]

but how do i explain how they are equal

i thought about using a pascal trinagle to show but i want to use combinatorial explanation

[proven shard]

Make a bijection between the two sets

[weary tiger]

Would the answer for this question be E or C? I'm leaning on E but not so sure.

[fallow pawn]

sry but i dont see how i can use bijection to show equivalence

[rotund frigate]

if the simplified master theorem is anything like the regular master theorem, then it falls under none of those.

[weary tiger]

@rotund frigate so E?

[proven shard]

Let S be a collection of n objects.
Let X = the set of pairs (A,B) where A is a subset of S with h objects and B is a subset of S\A with k objects.

Is it clear why the cardinality of X is the LHS?

[rotund frigate]

yeah. Also none of the other answers have the correct big-O bound either, which is commonly known for insertion sort, so that's another way you could figure out the answer.

[weary tiger]

For this question, It would be A?

[fallow pawn]

i see where you are coming from but not the part for the cardinality of the LHS

[rotund frigate]

log_4(16) = 2, so ye

[proven shard]

It's just the definition of n choose k

N choose k counts the number of ways you can choose k elements from a set with N elements

[weary tiger]

Last question. This one is pretty challenging. I think it's D.

[proven shard]

All I did was rephrase this interms of sets

[fallow pawn]

ohhh ok

[rotund frigate]

log_2(7) > 2, so the master theorem states that it's Theta(n^log_2(7))

[proven shard]

Ok write down the analogous set Y for the RHS and form a bijection between X and Y

Then you have LHS = RHS

[weary tiger]

A matches that @rotund frigate

[rotund frigate]

yep

[zealous dirge]

S = {LaTeX: x\in x ∈Z+|LaTeX: 8< x< 138 < x < 13}

[last timber]

[stray reef]

$S = \{ x \in \mathbb{Z}^+ \mid 8 < x < 13 \}$

did you want this?

[vital dew]

Ann

[graceful spade]

I'm stuck at this exercise. I write an as a linear combination of caracteristic polynomial roots but i don't know how to write it just în terms of a0 an a1. Can somebody give me a clue?

[stray reef]

$a_n = \alpha_1 s_1^n + \alpha_2 s_2^n$

[vital dew]

Ann

[stray reef]

so $a_0 = \alpha_1 + \alpha_2$ and $a_1 = \alpha_1 s_1 + \alpha_2 s_2$

[vital dew]

Ann

[graceful spade]

Thanks, i've been thinking that i need to find other relations for a0 and a1. I understand

So i need to find alpha1 and Alpha 2 from this 2 relation and subtitute them in the firs?

[stray reef]

yes

[graceful spade]

Ok, thank you!

[sand cipher]

need help with this, i missed out on a class and i'm confused with all the problems, like i understand them how to do but also i don't know how to solve it, like if someone does it i understand it, but when i see the problem i'm confused

[prime parcel]

If a divides b it means a divides kb too where k is some integer

Awa a|b implies a|kb

For 2nd if u have two consecutive integers the one is odd and other is even fs

So see what form does it give u

[vagrant elm]

My book uses the ∪ symbol in regular expressions, but I have seen other places use the | symbol (which my book doesn't).
Do they mean the same thing?

[pale epoch]

yeah

$\cup$ is the union of languages

[vital dew]

Lochverstärker

[pale epoch]

but in regex you often use | to mean the same thing essentially

[vagrant elm]

alright thanks

[opaque chasm]

how do i go about proving this?

[weary tiger]

I have a question
if I have 2 function one function of k suppose f(k)=2k+1 and one function of n suppose f(n)=n
can we say that one is Big -Oh of the other ?

[faint narwhal]

Yes

[weary tiger]

@faint narwhal but they are 2 different variables

like we can't graph them on one plane

[candid pier]

maybe it would help if you called one function f, and the other g. then used the same variable name:

f(n) = 2n + 1
g(n) = n

[weary tiger]

but I don't have the same variables

[candid pier]

variable names are usually arbitrary. is there some relation between n and k?

[weary tiger]

I mean there might or might not be

that is the problem

if there is no relation

I do what you said

and if there was a relation

what do I do

[candid pier]

i dont think you'd have to do anything differently. in any event you shouldn't define f two different ways. the variable names don't matter but the function name does

[candid pier]

write out f(0), f(1) and f(2). you should be able to identify a recursive pattern

[opaque chasm]

i got if n= 0 then f(n) = a

and if n>= 1 f(n)=b*f(n-1)

does that seem right?

[fallow pawn]

Am I proving this correctly algebraically

[candid pier]

yes exactly

[obtuse lance]

looks like your n and h is confusingly similar or you wrote n where you should have put h

ah actually no you've done it wrong

$\binom{a}{b} = \frac{a!}{b! (a-b)!}$

[vital dew]

Merosity

[obtuse lance]

this (n-h)! should be k!

you know it's wrong because if this was the formula (n-h)! in the numerator would always cancel the (n-h)! in the denominator

[fallow pawn]

ohh i see. and assuming i have the b and a value in the right place, am i doing it right

[obtuse lance]

yeah the idea is correct

[fallow pawn]

Gotcha thanks

[grave moon]

it should be enough to say " according to transitive law if f(x) is a member in g(x) set, and g(x) is a member in h(x) set. therefore, f(x) is a member in h(x) set." right?

and by proving x belongs to big O of x .. we can simple say f(x) belongs to bigO x square since x belongs to O(x square), right?

[opaque chasm]

can i have help with this question? i'm totally lost in what to do

[rotund frigate]

well I think they're asking you to prove the transitive law here

[rotund frigate]

induction

[opaque chasm]

ok i know how to do induction but i dont understand how to apply it here

[rotund frigate]

first, do you have any idea what you use as your base case/inductive step?

[opaque chasm]

no lol im so lost for this one

[grave moon]

the (a,b) ^ (b,c) -> (a,c) ?

[rotund frigate]

well remember when you prove a property P holds for all naturals, you prove P(0) and prove that P(k) implies P(k + 1)

in this case that property is that 2^n is in the set

[rotund frigate]

yes. In this context, it would be if f(x) = O(g(x)) and g(x) = O(h(x)), then f(x) = O(h(x))

[opaque chasm]

so 2^n is my first function?

[rotund frigate]

uhhh

wdym first function?

[grave moon]

sure, thnx man

[opaque chasm]

so

i got

for An

but i’m not sure if that’s even right or where to go from here

[rotund frigate]

,rotate

[rotund frigate]

have you tried induction?

[opaque chasm]

what am i using with induction tho?

[rotund frigate]

well you need strong induction but show that if a_{n - 1} = f_{n} - 1 and a_{n - 2} = f_{n - 1} - 1 then a_n = a_{n - 1} + a_{n - 2} = f_{n + 1} - 1

that's the inductive step btw

base case is just showing that it holds for a_0 and a_1

[opaque chasm]

ok wait give me a second to write it out

so now do i just change out the n value for k+1?

[rotund frigate]

n value?

[opaque chasm]

like do i just leave it as is or do i have to go more into detail

[sand cipher]

need help with this, i missed out on a class and i'm confused with all the problems, like i understand them how to do but also i don't know how to solve it, like if someone does it i understand it, but when i see the problem i'm confused

[clever sage]

if a divides b and and a divides c, b and c can both be expressed as multiples of a

[jagged junco]

@sand cipher
let k, m be integers.
a|b => ak = b
a|c => am = c
5b + 3c = 5(ak) + 3(am) = a(5k + 3m)
a|(5b+3c) is true because if you do 5b+3c / a you get (5k+3m) which is sum of integers

[dense sapphire]

Hello everyone! Is there a way to prove that the product of a graph's incidence matrix and transpose is the sum of that same graph's diagonal and adjacency matrix?

[stray reef]

what's the diagonal matrix defined as

[dense sapphire]

let me rephrase

how would i prove that two graphs with identical Laplacian matrices are isomorphic

[dense sapphire]

could i say the adjacency matrices are by consequence equal

would that mandate isomorphism?

[fallow pawn]

is it right to say (n-2)!(n-1)(n) = n!

[fallow pawn]

is 2(n-1)! the same as (2n-2)! ?

[faint narwhal]

its ambigious

but probably no

[fallow pawn]

damnit

and ty

[fallow pawn]

is it wrong to simplify (2n-n)! into (2-1)!*n

[faint narwhal]

what do you think?

[wicked basin]

This is true due to simplification right ?

[fallow pawn]

i think it is wrong but im not exactly sure

[errant bear]

write it out

itl be clear if you do

[coral raven]

is that a 5

it feels fairly obvious, maybe better to be safe tho

could say 2 + 1/2n < 3 for all n

[fallow pawn]

anyone know how i can simplify (2(2n-1)!) / ((n-1)! n!) into 2n!/n!n! ?

[coral raven]

bruh multiply top and bottom by n

bc you want to make the (n-1)! into n!

[fallow pawn]

so i want to simplify the expression to 2n!/n!n! so i can proof (2(2n-1)!) / ((n-1)! n!) = 2n!/n!n!

if i multiply that by n wouldnt i have to multiply the 2n!/n!n! side by n as well

[coral raven]

no

top and bottom

a/b = ac/bc

[fallow pawn]

thought if i multiply one side i have to do it to the other to keep it balanced

and 2n(2n-1)! is just 2n! right?

[coral raven]

if you multiply top and bottom of a fraction by the same number, it stays the same

watch this

[fallow pawn]

youre right

my mind bugged out for a sec lol

[coral raven]

ok well multiply top and bottom by n and done

[fallow pawn]

gotcha

thanks

[gentle lichen]

in first order logic, can we return something other than true or false

say we had the following. could we define Married() so that it returns their names instead.

[proud tangle]

As far as I'm aware of, a predicate will always return a true or false

[gentle lichen]

is it possible to redefine how a function interprets true and false?

[naive gulch]

really confused on where they pulled the 4 from

[faint narwhal]

4 * 3?

[naive gulch]

yeah sorry

the coefficient

[abstract otter]

am i allowed to do this?

[faint narwhal]

yes

[abstract otter]

how do i treat the 2^-2?

[grand elm]

square of the multiplicative inverse of 2

[abstract otter]

the bezout coefficient i get is -104

it doens't give the right asnwer though

[grand elm]

it should

[abstract otter]

hmmm

i should get 9

[grand elm]

-104 is 105 btw

[abstract otter]

oh lemme try that

yeah it gives me 157

i should get 9

lemme go over hte math brb

yeah it should be correct

4**103 mod 209 gives 9

so somewhere below i made a mistake

[weary tiger]

Anyone know how to do this I think the symmetric and reflexive I have some idea but the transitive and putting it together is an issue

[faint narwhal]

what have you tried?

what exactly do you mean by that

Uh, you should probably look in your notes or textbook for your class where you're getting this from

[weary tiger]

ight just ignore my questions

does this look correct

Just feels weird to have that few 0s

[unreal stump]

Note (6,3)=1 and (3,1)=1

Which means the entry in (6,1) should be 1 for transitivity

Well,(3,i)=1 for all i in domain. (2,1)=(1,2)=(1,3)(3,2)=1*1=1.
Similarly,(1,6)=(6,1)=(6,3)(3,1)=1 and
(2,4)=(4,2)=(2,3)(3,2)=1

[unreal stump]

Everything should be 1

[weary tiger]

yes I got that just now

@unreal stump but that seems wrong

I must have messed up earlier

Maybe if I did a transitive check multiple times

like symmetric plus reflexive

then do the transitive check

if that makes sense

like add it to the original

then do a transative check

[unreal stump]

You don't have to do reflexive check more than once

You would mostly be doing transitive check,and whenever you add 1 to (i,j)th entry,you add 1 to (j,I)th entry to maintain symmetric nature

[weary tiger]

so the answer is all ones?

[unreal stump]

Yes

[weary tiger]

I just feel like I did something wrong

[unreal stump]

Assuming your reflexive and symmetric one is correct

[weary tiger]

I see

is there a calculator I can check it on\

I'm too lazy to code it myself

[unreal stump]

It takes like 3 minutes to code in python

[weary tiger]

Ight ima do it

ty

[unreal stump]

I mean,Go one more step and write a python program to find the closure

The contradiction statement is (p doesn't divide a, then gcd(p,a)!=1)

[wicked basin]

im not sure how to describe this in words

so strings will start with 1, but what about the stuff that are in the parantheses?

[last timber]

why you think they will start with 1

@wicked basin

[wicked basin]

o shit oops they dont start with 1 starts with 0

https://cdn.discordapp.com/attachments/811391852934725653/816336397530955856/unknown.png

so 1011 belongs in this regex but i dont understand how

[last timber]

a* means all possible strings over {a}

including empty string

(10U11)* means all possible strings over {10, 11}

[wicked basin]

ok so you just know by looking?

is there a way to like solve it or u just use ur judgement

[last timber]

i mean i gave you defns

1011 is just empty string + 10 + 11

[wicked basin]

ok thx :) i see it

[wicked basin]

is the string 00 accepted?

[glossy flume]

is there a way to visualize n set intersections?

[hidden yacht]

need help with labelling procedure

[slow jewel]

Any ideas

[earnest yew]

I have a difficult discrete mathematics problem Im struggling on if I send it can someone have a look and guide me as to what approach I can go to solving this

[weary tiger]

can i get help on this?

[errant bloom]

I think that the 3rd is wrong

[weary tiger]

@errant bloom would it only be the third one?

[errant bloom]

not fully sure, but let me explain

the first says: A\cupB = All Plants. then you do: All Plants U All Humans = All Life

since life here is made out of humans + plants

as there's no other set, right?

but if you assume that All life on earth is made out of 3 sets: All Humans, All Plants, All Animals then this is wrong. I just assume that all life ls exactly composed out of the 2 disjoint sets B and C

$A = B \dot{\cup} C$

[vital dew]

lyinch

[errant bloom]

if that's your assumption then I think that only the 3rd is wrong

[weary tiger]

okay thank you

[errant bloom]

but I find it a bit unclear, because the statement never tells you about the relation between the 3 sets

[slow jewel]

Does anyone know how to solve this difference equation

for the particular solution

[errant bloom]

you can use the master theorem I'd say

[earnest yew]

What is best approach to solve this

[pallid belfry]

Can someone give me some hints or tips on where to start with this problem?

I did the hint at the bottom and got to here

[lilac delta]

Why is this so hard

I can’t do it

[blissful zenith]

can some1 help me solve a recurrence relation

[coral raven]

https://dontasktoask.com/

[obtuse lance]

sure, try it out and see if it works

[slow jewel]

@obtuse lance

[obtuse lance]

@slow jewel

[slow jewel]

hi sexy

[obtuse lance]

https://tenor.com/view/austin-powers-i-am-sexy-and-i-know-it-spin-fat-bastard-gif-11615966

[hasty raptor]

is anyone able to assist with this strong induction?

i got to the F_(2(k+1)) = F_(2(k+1)+1) -1

im just not sure how to algebraically manipulate one of the sides to match the other

[last timber]

@hasty raptor still need help?

[hasty raptor]

i got that one, but i have some more from the same unit

[last timber]

well feel free to ask

[hasty raptor]

okay, so this one is a strong inductions example

i suppose im just having a difficult time starting working through my inductive step

[last timber]

(tbh i would just solve recurrence)

but ok

[hasty raptor]

i havent learned recurrence:( this unit is centered around proof by induction

[last timber]

so for n = 1 and n = 2 it is obviously true?

[hasty raptor]

yes

those are given, right?

[last timber]

well yes

if you want you can check also n = 3 manually

[hasty raptor]

but yes i see what u mean. they work for the base case and 3 works as well

[last timber]

ok, so now assume that it is true for 1,2,...,k-1

you have to show that this implies the truth for k

[hasty raptor]

why k-1?

[last timber]

because we are doing induction?

[hasty raptor]

oh sorry i see what u mean

i think i was skipping ahead to the k+1

in other words, it would be true for 1,2,...,k-1, k, k+1?

[last timber]

i mean it is just indexation

[hasty raptor]

yeah

[last timber]

i want to derive that truth for 1.,,,. k-1 implies truth for k

together with manually checked truth for 1.2.3 it will imply that statement holds for all n

@hasty raptor now, use formula for a_k but then replace a_{k-1} and a_{k-2} by (k-1)^2 and (k-2)^2

since by induction we assume that for them statement is already tru

[hasty raptor]

thats the strong induction step, correct?

[last timber]

yes

[hasty raptor]

okay, i understand that step. are we subbing in k-1 for k as the next step?

[last timber]

wym

which next step

and subbing what

[hasty raptor]

oh i thought we were supposed to sub in a k+1 for the k's

like in a weak induction you look for the k+1

[last timber]

reread this and two statements above

[last timber]

what is the difference between arriving to k from k-1 and to k+1 from k except for indexation?

[hasty raptor]

i gotcha. there is no difference form k-1 and k+1

[last timber]

both in weak and strong induction you need only one move, in strong induction you just assume that statement is true not only for previous number. but for all numbers below

[hasty raptor]

ok yes that makes sense

[hasty raptor]

i am just confused about this step is the root of my problem i believe

whoops the one above

they give us two different a_k's right?

[last timber]

[hasty raptor]

you used the second one that was given(the one we are trying to prove)

use formula for a_k but then replace a_{k-1} and a_{k-2} by (k-1)^2 and (k-2)^2

^this one

did you just bring the subscripts up from the other equation?

thank you for being patient btw induction has been a headache for me

[last timber]

i mean if you assume that you already proved that a_n = n^2 for all n < k how would you use this knowledge for a_k?

in here

[hasty raptor]

ok i understand

is that all there is then?

[last timber]

well once you arrive at a_n = n^2 you are done mainly

[hasty raptor]

one more thing, how come we dont need to do anything with the coefficients and other numbers like 6n -7 when we substituted the k-1 and k-2 in?

are we able to just ignore all of that and focus on the subscripts?

OH WAIT

i think i read what you said completely backwards

were u saying a_k = -(k-1)^2 + 2(k-2)^2 +6k -7?

and then we solve for that to equal (k-1)^2?

[last timber]

why (k-1)^2

we need to arrive to a_k = k^2 from here

[hasty raptor]

@last timber I finally got it. Thank you so much. I just made an incorrect substitution

[minor dagger]

for the first one, is union of both sets really empty?

[weary tiger]

No

[minor dagger]

I think your two answers contradict each other

[weary tiger]

Would it only be the third one?

[minor dagger]

looks like it

[weary tiger]

Could I also get help on this problem?

I think it shoould only be the last one but idk

[minor dagger]

well for the first one

thats the set containing the empty set

not the empty set itself

for #2 you should know that equal sets are subsets of each other

the third you could use similar logic to 1

and the last one also

[weary tiger]

For the second one isn't it that Proper subsets are subsets of each other?

[minor dagger]

yeah im sorry im tired

proper subset cant be a subset of itself

[weary tiger]

So is it only the last one that is true?

[minor dagger]

yeah

they both contain the set containing the empty set

[weary tiger]

okay thank you

[pastel mica]

hey guys, i just wanna double check something, for proving tautologies and logical equivalences we need to use truth tables but for whcih one do we need to show the column with all T's at the end

or am i mixing things up lol

[weary tiger]

A Tautologie would result in all T's at the end

@pastel mica

Does this have two minimums? if so then which is them minimum

Basically got that e and f are both minimums here

[unreal stump]

Yes

There are 2 different least elementz

@weary tiger

[weary tiger]

Isn’t minimum the first element

That would be the max

[unreal stump]

Does aRb here mean a>=b or a<=b?

[weary tiger]

not sure wasn't specified

ima go ahead and say no minimal

[unreal stump]

If you assume aRb means a<=b,you get c is a max element and {e,f} are min elements

[weary tiger]

can someone help me with the one i circled

[last timber]

what exactly confuses you

[candid pier]

Did you make any progress?

[weary tiger]

I couldn't find the answer

for A' ∩ C

[last timber]

find A', then apply defn of inersection

[weary tiger]

i did and i couldn't find any

it's empty or an error

but not sure if im wrong or right

[hasty raptor]

that seems correct

can anyone walk me through this proof by contradiction

[meager prairie]

is this just by definition

why do you need a contradiction

I guess it doesnt matter

OH, just saw, give me one sec

so

@hasty raptor

heres what i figure

[hasty raptor]

im here btw

[meager prairie]

oh shoot did i do this wrong

[hasty raptor]

heres where im at

[meager prairie]

aRRRGH hold on sorry

[hasty raptor]

u good

if u can read through my atrocious hand writing

though i think i may have done my proof by contra wrong

[meager prairie]

this is a complicated one im not sure why lol

[hasty raptor]

yeah that seems to be the case with alot of the problems in this textbook

[meager prairie]

my thought is like

going by cases and immediately focusing in on one possibility is that a_n+1 is 2

[hasty raptor]

hm

i mean

[meager prairie]

hmm

yea i hate this problem

[hasty raptor]

for me i just looked at it and thought if the equation is equal to 1, a_n = 2. so the contradiction would be if the equation is equal to 1, a_n is not 2

so then i just plugged in the base case of n=2 and the answer was 1, but the rules above imply that if it equals 1, then the answer is 2

so i feel like thats a contradiction?

[meager prairie]

okay

I'm gonna go slow so i dont make a mistake

[hasty raptor]

alright

[vital dew]

jan Niku

jan Niku

[meager prairie]

I'm sorry if this is exactly what you were saying, sometimes its easier to just start from scratch than wrap your head around someone elses logic

[hasty raptor]

this is much better

i have such a hard time thinking about these things on a conceptual level rather than a direct proof

[meager prairie]

I'm not sure if this is a contradiction or direct lol

I guess you could wrap it either way

this problem is a little bit of a brain speed bump in your credit, navigating the equals 1 when it doesnt equal 1 thing lmao

[hasty raptor]

yeah

alright well thank you!

[meager prairie]

[weary tiger]

[hasty raptor]

@meager prairie would u be interested in helping me with a strong induction?

[meager prairie]

I can try

lol

[hasty raptor]

haha

okay so base cases on both are true

as far as induction goes i am slightly lost. am i just trying to prove that F_n+1 <= (5/3)^(n+1)

[meager prairie]

so

thinking on the induction step

[hasty raptor]

i also have 1<=i<=k

[vital dew]

jan Niku

jan Niku

[meager prairie]

and that by induction we can make that replacement of F_n as well as F_n-1

[hasty raptor]

wow this was a very logical straightforward approach. idk if its my brain or what i just cant think about proofs well

[meager prairie]

the inductive step takes a lot of practice

[hasty raptor]

like after i see it it makes so much sense

[meager prairie]

also you have to aware of bounding factors

its important to note you wouldnt be able to do this if they were like

you know if 1 was between them or

there are considerations

[hasty raptor]

sure that makes sense

[meager prairie]

that i cant be sure matter without really turning on my brain

but here its pretty straightforward

youll start to see the patterns as you do more

[hasty raptor]

ok cool thank u

[meager prairie]

[hasty raptor]

could i like friend u if i need more help sometime?

[meager prairie]

you should ping me in this channel

[hasty raptor]

or dm

ok cool thats fine

[meager prairie]

not that i mind dm's

im just better at responding to pings than dm's haha

[hasty raptor]

yeah np i gotcha

[meager prairie]

also in school constantly

[hasty raptor]

same -_-

this class makes me question myself on whether im cut out for csci

i took data structures last semester and did pretty well, but then they hit us with this course and im lost

[meager prairie]

idk i hear a lot of csci ppl say that

[hasty raptor]

yeah

[meager prairie]

given that discrete is more or less intro proofs and intro proofs is about learning how to accept that youre dumb it makes sense lmao

[hasty raptor]

that is a fair point

i just want to pass and move on to linear algebra

[meager prairie]

linear is cooler than discrete 😄

[hasty raptor]

@meager prairie could i use the formula a_n-1 + 2?

for part ii

[candid pier]

did you intend to rewrite it as another recurrence? or did you want to prove a nonrecursive, equivalent formula

[hasty raptor]

honestly, thats part of the issue im having is identifying what kind of forumla im looking for. this is a proof by strong induction if that helps at all

the only one i could come up with is this one i gave above

[candid pier]

i'd write down the first several terms and see if any pattern jumps out at you. i think you've identified the pattern

[hasty raptor]

yup, it each interval increases by two

[candid pier]

and a_1 = 1, so the sequence is {1, 3, 5, 7, ...}

[hasty raptor]

1,3,5,7,9...

yes

which is why i have: a_n-1 + 2

[candid pier]

that's true, yes, but you're still left with a recurrence

[hasty raptor]

yes thats a good point

[candid pier]

these are odd numbers. can you think of a simple formula that will output the nth odd number, for n = 1, 2, 3, 4, ...

[hasty raptor]

i want to say 2k +1 but i dont think thats correct

[candid pier]

close

[hasty raptor]

2k -1

[candid pier]

yes, 2n - 1

[hasty raptor]

gotcha

so thats the forumla i should use for the induction process

[candid pier]

so your task is to prove that the recurrence relation is equivalent to 2n - 1

[hasty raptor]

in that case, i am trying to prove a_n+1 = 2(n+1)-1

[candid pier]

yes

[hasty raptor]

okay i will give that a try. thank you!

[gloomy hatch]

i need to solve the best big Oh for each of these expressions
so far I got:
(5/3)^2n = O((5/3)^2n )
10 ^8 = O(1)
2^(log{2}n) = O(2^(log{2}n))
2^n = O(2^n)

i was wondering if the ones i got so far are correct

before i move onto doing more of the log expressions

if anyone can help

🙂

[rotund frigate]

uhhhh

there's a lot of simplification that can be done

for example

2^{log_2(n)} = n

[fleet latch]

should this be 4?

[tight lotus]

{{{∅}}}, right?

or am I missing one

[faint narwhal]

4 is correct

[tight lotus]

would that look like this, then? {{{{∅}}}}

[faint narwhal]

P({}) = {∅} so that P({∅}) = {∅, {∅}}

[tight lotus]

Ohhh

this is becoming a pain to write out

[faint narwhal]

you can also just use the fact that for finite sets X, |P(X)| = 2^|X|

so 2^(2^(2^0)) = 4

[fleet latch]

awesome ty guys :))

[tight lotus]

that leads into my next question; if P returns the power set, at what point are we talking about sets and at what point numbers, or is there some defined isomorphism between these power sets and natural numbers (that we are implicitly using)?

[faint narwhal]

uh what

[tight lotus]

so P(a_set) is the power set of a_set

[faint narwhal]

For finite sets, there's kind of a "bijection" between sets and natural numbers

[tight lotus]

hmm
that makes sense to me if the sets only contain sets?

or can you ignore non set things

[faint narwhal]

Uh I mean

classically in ZFC, everything is a set so

[tight lotus]

oh. good to know

thanks btw

[coral raven]

call {} 0, call {{}} = {0} 1, call {{}, {{}}} = {0, 1} 2, call {{}, {{}}, {{}, {{}}} = {0, 1, 2} 3, etc.

i think that's how it goes?

you can define things so they act exactly the same way

[placid plover]

I have a question, not sure who to ask. My question is
"Prove by contradiction the following proposition:
Proposition: for every n ∈ ℤ, then n^2 + 2 is not divisible by 4."

I wrote the following, but I'm not sure if I am right. Can anyone clarify?

[meager prairie]

it sort of seems like you know what the answer is

to be honest its not communicated 100% as good as it probably could be

can you encapsulate your overall argument in a sentence or two?

[dreamy solar]

I have no clue how to go about proving this

I asked and I don't have to do an actual proof just explain why it is

[meager prairie]

do you have any intuition about like

the type of object this mapping is

focus in on the f : Z x Z -> Z

[dreamy solar]

thats the part that confuses me that means the domain is an ordered pair right?

[meager prairie]

yea, exactly

[dreamy solar]

and the codomain is all integers

i just dont get what that means

[meager prairie]

yup

[dreamy solar]

Like visually

[meager prairie]

i guess you could think of it like 3 dimensional space if you wanted, idk if thats misleading or not

a less visual example would be like a distance function

i suppose that pair wouldnt necessarily be ordered

but just some function that returns the integer distance between two other integers

there is a visual intuition for that but it probably makes less sense than just like

this thing obviously takes two inputs, and obviously gives one output, just intuitively

to me at least

[dreamy solar]

ok that makes sense now

[meager prairie]

idk maybe im getting side tracked

[dreamy solar]

thats where f(n,m) comes into play

right?

[meager prairie]

yea

[dreamy solar]

cause Z X Z means it takes two outputs

[meager prairie]

actually its the same case here as it is in the distance function

if you notice n^2+m^2

it doesnt matter which one we put in first

just like in the distance function

[dreamy solar]

so first I have to prove its injective and then surjective

to prove its bijective

[meager prairie]

yup

but before that

well i guess you dont have to do a formal proof

so the first step is the whole thing

does it seem reasonable that this mapping would be both things

[dreamy solar]

I don't think it would be one to one (injective) jsut from thinking about it

but idk

[meager prairie]

whys that?

i mean you dont have to know exactly

but what makes you think that

[dreamy solar]

I meant onto

not one to one

[meager prairie]

sure

[dreamy solar]

Oh wait two inputs are going to one output so by definition it cant one to one right

[meager prairie]

not quite

wait does it

idk thats a question for another day

theres no way that can be true

[dreamy solar]

I think iw as getting confused

I probably need a better definition of injective and surjection

[meager prairie]

i mean no you could have 2 inputs

well

were getting side tracked with that question but its fun

here use this picture

[dreamy solar]

The pictures help me visualize it, but if its like a function I get confused

[meager prairie]

all i mean when i ask about the uhh

if it makes sense that its both things is like

can you think of any numbers you could put into this thing to break it

so any ordered pairs that would be invalid

or can you think of any numbers itd be impossible to get out?

||specifically what do you know about the square of an integer||

[dreamy solar]

oh

I think I see

there are some numbers that won't get matched, because there is no integer for example such that integer^2 = 3

if that makes sense

am I right on that?

[meager prairie]

hmm no not quite

but wait

well yea

actually

[dreamy solar]

like the value 3

[meager prairie]

well youre half right

[dreamy solar]

which is B

can't be mapped

meaning it cant be surjective

[meager prairie]

i dont think you can find an ordered pair that gives you an output of 3

no a^2 + b^2 = 3

i was thinking more of the negative integers lmao

but this works too

[dreamy solar]

well there exists no integer such that a^2 + b^2 = 3

[meager prairie]

this thing has all the negative integers as part of its codomain

but there is no sum of squares that ever equals a negative integer

[dreamy solar]

ohh

that also

[meager prairie]

and yea probably infinitely many positive integers that are problematic

so tons of problems

which idk how much intuition you have about bijection

but means that like

[dreamy solar]

so basically thats all I need to disprove it because it isnt surjective

[meager prairie]

if we flip those arrows around

well be able to start somewhere but have nowhere to go

yea exactly

i mean any one example is good enough

but naming groups of them might be nice

you can never hit the negative integers, you can never hit n^2+m^2=c where c is an integer and n and m have no integer solutions

which is going to be a lot of places

as to your other question idk

i wonder about an infinite set that makes it work

its trivial to design a finite example that makes that mapping possible

im tired, it might be trivial to make an infinite set one too

[dreamy solar]

Dont worry about my other question

[meager prairie]

maybe just N x N -> N x N x N x N with f(x,y) = (x,y,x,y)

[dreamy solar]

tbh I didnt know hwat I was saying

[meager prairie]

something like that

[dreamy solar]

I was totally confused when I said that

[meager prairie]

lol ur good

its a fun question

[bronze cosmos]

hi i have question c:

$G_0=\frac23$, $G_1=\frac5{12}$, and $G_n=\frac23G_{n-1}-\frac1{36}G_{n-2}$ for $n\geq 2$

[vital dew]

danmarino900

[bronze cosmos]

i’m trying to show that G_n=/=0 for all n

anyone got any ideas on how i can do this without using the exponential closed form for G_n?

[slow jewel]

Is the exponential closed form the general solution

[tawdry edge]

Can you use the derivative to demonstrate equivalence?

[stray reef]

the derivative of what

equivalence of what

[bronze cosmos]

lol yeah I agree with Ann

[bronze cosmos]

yes it’s expressing G_n only in terms of n, instead of recursively

it’s well known that linear homogenous recurrence relations like this one (or the fibonacci sequence) have closed forms involving exponential functions

but I feel like that’s overkill for this problem, i just wanna show G_n is nonzero, nothing more general than that

[weary tiger]

how would the truth table for this look like.I have to find if P and Q are logically equivalent. I know how to do the P part but the Q is what is confusing me since it has a extra variable t.

this is the truth table for P. would that extra t in Q cause the truth table to have 24 rows now?

[bronze cosmos]

bruh seriously?

is there a better channel for my question? i has test tonight and this is a practice question :c

[weary tiger]

midterm on monday. feelsbadman

[eternal roost]

anyone know how to do this, having hard time 🙂

<@&286206848099549185>

[sly heart]

Use induction

[bronze cosmos]

i really don’t think induction helps

[plucky thunder]

hey I have a question regarding vocabulary in my discrete math question, does modulo and mod have the same meaning or do they have seperate meanings?

[coral raven]

mod is just short for modulo

[plucky thunder]

so they're the same?

[coral raven]

95% sure

[plucky thunder]

thank you, my prof has never mentioned anything about modular so i was confused af

[weary tiger]

Can i get help on this problem?

I think part a is that b is a proper subset of a and part b's answer is the same as part a

[coral raven]

not sure about 'proper'

[stray reef]

yeah B doesnt need to be a PROPER subset of A

$A \cap A = A = A \cup A$ after all

[vital dew]

Ann

[hardy yoke]

B→(C → B) Trying to understand the axioms of propositional logic

Does this mean if B implys C then C will always imply B?

[candid pier]

looks like a tautology

if you assume B is true, then anything (call it C) implies truth

[weary tiger]

For 3C is it possible to establish C = x

here's my reasoning

u can view xlogx as logx+logx+logx+logx+logx+.... (added x times) <--- this will always be less than x + x +x +x +x +x +x (added x times)
hence xlogx < x^2|(x*x)

[faint narwhal]

C is a constant, it cannot depend on x

[weary tiger]

oooh ok

[paper parrot]

It means:
If B, then (If C, then B)
When B is false, the whole conditional is vacuously true
When B is true, the bracketed conditional is always true, because a conditional is only false when the consequent (then B) is false, but its true. The whole conditional is true for the same reason (the consequent is true, as I just mentioned)

If you draw up the truth table, you'll see its a tautology

[paper parrot]

It's also a way of saying "A conditional is true if the consequent is true"

"If the consequent (B) is true, then a conditional with B as the consequent is true"

[autumn pebble]

I wanna make sure I’m getting the concepts of tracing algorithms, does anyone see any errors in the table or reasoning

I also need to find a recurrence relation for Xn, I’m assuming I’d use the initial values but I can’t find one, doesn’t seem like it’s arithmetic or geomatic

[lethal prawn]

Can I get some assistance understanding Logical Proofs?

I'm having trouble figuring them out.

[jagged dirge]

jesus christ, break that expression into multiple columns

[weary tiger]

what do i do about that Q=pVt part tho. do i make a independent truth table for that part?

[jagged dirge]

yes, but obviously you have to solve P first

or, after you solve P, you shoild just add Q as its own column next to P so you can easily compare the results

[weary tiger]

i know how to solve P. what i'm confused about is how the extra term 't' in Q=pVt factors into the truth table.

should make columns for p q r s t. this would cause it to have like 24 rows though

[jagged dirge]

ah, i see your issue. My guess would be yes?

I mean, you need a column for each term thats in play in the expression

so that's what I would imagine

does seem super cumbersome though

[weary tiger]

yea i was wondering if that was how you were actually supposed to approach it, or if there was an easier way

[jagged dirge]

or maybe it expects you to make a seperate truth table for Q

and you can just make it the same number of rows as P table to comapre results. Either way im pretty sure the results would be the same?

my best guess would be just to add t as a term to the original table

[weary tiger]

ok that's what i was thinking as well

[jagged dirge]

I really hope you dont have to hand-write this

[weary tiger]

oh, i do

[hybrid tendon]

I have a problem where there are r recipes that costs you x (x varies per recipe). There are i ingredients which are used to make a certain recipe r. You have find the max number of recipes that can be made with the least cost. Is there any algorithm to solve these kinda problems? I couldn't even phrase this and search in google. I know this comes under dynamic programming stuff, but still confused with what algorithm to use.

[weary tiger]

@remote cape hi

[remote cape]

hi

should i repost here?

i just put it in #probability-statistics

because that's what seemed most fitting to me

[stray reef]

@hybrid tendon this sounds like linear programming?

some variation thereof anyway

your notation is a bit odd

you also have constraints on how much of each ingredient is available tho, right

[hearty elbow]

Where can I ask about turing reduction and rices theorem questions?

[wooden acorn]

not sure where you'd ask about that@hearty elbow

I am trying to figure out how to apply the pigeon hole principle to this problem, and idk how. idk if the arbitrary members are considered the pigeon boxes or if the two spots of playing ping pong are the boxes. I get how the problem works visually in my head if there were a certain amount of family members playing ping pong. But here's the question: "At a family reunion, family members settle their differences on the back porch with a friendly game of ping pong. each ping pong game involves exactly 2 family members playing against each other. Show that, after the reunion is over, there are at least 2 family members who have played against the exact same number of different opponents." I don't know how to convert the image in my head of the distribution of games and opponents into a mathematical form

[mystic moss]

@wooden acorn what is the image in your head

[wooden acorn]

just like scenerios. Like if one person played someone, then they have equal amount of games. But if one person stayed, then the person that left and the new player would have the same amount of games because it's like an opportunity type trade off.

And if there was a larger amount of family members with the samething happening

or even if two completely new players played each time, then they will all have the same amount of games too

[mystic moss]

Okay nice

So in each of these scenarios how can you represent who has played who else by the end of the tournament

@wooden acorn

[wooden acorn]

I don't think you'd need to know who played who; just the number of times each person played. Maybe unless different opponents means it has to be a different opponent each game rather than counting the same opponent as a new match. I think it's a bit of a double entendre too. But answering your question there, maybe you could count the number of different match ups by multiplying the number of players by the number of players minus 1, so then you can use those as pigeon boxes.

so (players)(players - 1)(r-1)+1 = number of players

I think, let me double check that tho

wait

but then that doesn't tell me if players played the same number of games

[mystic moss]

Yeah so we only want the number of different players someone has played against

If I play against you, it doesn’t matter if we play again or not because that doesn’t increase the number of different players for either of us

And you’re right that we don’t need to know who has played against who else, but representing that helps you see where the pigeonhole comes in

And for this we don’t want to know like a total number, just a representation

[wooden acorn]

ok I was kinda confused about what is meant by different players; I guess it's exact language since it's math. There is no slang for saying something like different players

thanks

[weary tiger]

would the right step for this to be doing polynomial division?

[faint narwhal]

thats one way yes

[weary tiger]

would there be a more simpler way?

[faint narwhal]

This is as simple

[weary tiger]

alright

[naive gulch]

For this problem how does m|ab-1 and ab-1 = mc occur?

[faint narwhal]

That is the definition of divides

[hybrid tendon]

@stray reef Yes I have constraints on the number of recipes to be made, number of ingredients left, to minimize the cost, and certain ingredients are needed to make certain recipe. sorry for the odd notation I forgot LaTeX,
In short there are only 3 ingredients and 3 recipes. With each recipe having different cost and require certain number of ingredients to make them.

[weary tiger]

wtf is a tournament graph?

[stray reef]

@hybrid tendon do you have the exact problem specification? i can show you how to write it down as LP

[hybrid tendon]

,tex There are two ingredients $x, y$. To make recipe $r_1$ we need $2x$ ingredients (that would be an easy eqn). To make recipe $r_2$ we need $3y$ ingredients. To make recipe $r_3$ we need $x + y$ ingredients. $N$ recipes are to made to minimize the cost. Recipes $r_1$, $r_2$, $r_3$, cost $c_1$, $c_2$, $c_3$ respectively

[vital dew]

Radical Ninja

[stray reef]

uhhh okay wait

so we need one unit of x and one of y to make the third recipe?

[hybrid tendon]

yea

[stray reef]

okay

can we only make whole numbers of each recipe?

[hybrid tendon]

yea only whole numbers

[stray reef]

bc then this will be an ILP which is a lot more complicated to solve

oops lmao

[hybrid tendon]

what's a ILP?

[stray reef]

integer linear program

[hybrid tendon]

how complicated? Don't tell I need to deal with math with no numbers to solve

[stray reef]

i mean more complicated to solve

[hybrid tendon]

Any other method to solve? if not I have no other choice

[stray reef]

this is your optimization problem

[hybrid tendon]

that's it?

[stray reef]

i mean, i didn't solve anything yet

this is gonna be relatively tricky to solve in the general case

sorry i didn't respond immediately - i was busy with other shit

[stray reef]

i typo'd: the last constraint should be $n_1 + n_2 + n_3 = N$

[vital dew]

Ann

[stray reef]

not that it changes the optimum tho

[hybrid tendon]

Ahh, No problems. I was checking on methods to solve, looks like it is NP

Gomory-Chvatal Cuts
Branch-And-Bound
These two

[stray reef]

your problem is small enough that either method will work fine tbh

do you have concrete values for the parameters of the problem? (c_i, X, Y, N)

i can run matlab's intlinprog with those

[hybrid tendon]

,tex those values are provided during runtime;
$5$ - orders to be made $(N)$, $i_1 = 4$, $i_2 = 4$(quantity),
$r_1 = 2i_1$, $r_2 = 3i_2$, $r_3 = i_1 + i _2$

[stray reef]

uh

...

wait

hold on a minute

[vital dew]

Radical Ninja

[stray reef]

is this a programming problem?

can i have a link to the original, please?

[hybrid tendon]

you can but it not nice to discuss the full solution. Other than the algorithm
https://www.codechef.com/MARCH21C/problems/COLGLF4

[stray reef]

i want to make 100% sure we're on the same page regarding what needs to be done

[hybrid tendon]

yea no issues, thanks for the help(in-advance)

[stray reef]

alright

i mean, ok

this problem is small enough that it might be possible to just use something like... modified brute force to search through all the possibilities?

it's probably O(N^2) worst-case

[hybrid tendon]

They're smart enough, check the constraints?

[stray reef]

im thinking like

we could start by checking if ordering N of the cheapest dish is possible

and then if it's not, try replacing some of the cheapest dish with the second cheapest dish

iterate through the possible combinations of three dishes in increasing order of price somehow

[hybrid tendon]

replacing some of the
By what amount? it looks like a wild trial and error

[stray reef]

yeah, this is by no means a complete description of an algorithm

i'm just saying, maybe this idea can be made to work somehow

but if you think that's worthless then fine

[hybrid tendon]

No, any amount of help is nice

wait Is this problem reducible from ILP to LP?

[stray reef]

you can consider the LP relaxation of this problem but the optimum in that isnt guaranteed to be integer

and rounding off the LP optimal solution may not even be feasible for the original generally

[hybrid tendon]

should I reconsider my decision to solve this problem at all?

[stray reef]

dunno, up to you

i guess i just jumped at the chance to show off some heavy mathematical machinery

theres probably some clever way to do it that youll call me stupid for not seeing

[hybrid tendon]

The other problems are even confusing like number of topological sort on an undirected graph.

[hybrid tendon]

You SOOO humble, anyways thanks for the help

[weary tiger]

does an isomorphism of an undirected graph (V, E) onto itself essentially just result in a shuffling of vertex letters?

it is just a bijection onto itself so that would make sense? An isomorphism of a graph onto itself could result in the exact same graph, right?

[fluid remnant]

Can someone tell me what the subscript notation means for the two graphs represented as K?

[stray reef]

$K_n$ is the complete graph on $n$ nodes

[vital dew]

Ann

[stray reef]

$K_{m,n}$ is the complete bipartite graph on parts consisting of $m$ and $n$ nodes

[vital dew]

Ann

[stray reef]

@fluid remnant

[fluid remnant]

thank you 😄 I know what those words mean!

[naive gulch]

Kinda confused on decryption here D:

I know I'm solving for the inverse of 17 mod 52*60 now because (p-1)(q-1) but now I just EEA right to find GCD(17, 3120)?

[naive gulch]

nvm got it but now I have these numbers