discrete-math

[modern arrow]

where can i ask a question about polynomials?

grade 7?

[minor dagger]

probably #prealg-and-algebra

[distant bobcat]

found this from a chapter on algorithms : Show the useful rule that if $f_1(n) << g_1(n)$ and $f_2(n) << g_2(n),$ then $f_1(n)f_2(n) << g_1(n)g_2(n)$ holds as well.
Doesn't this just hold from the properties of limits?

[vital dew]

Fredrikpiano:

[distant bobcat]

What exactly would I have to prove?

[stray reef]

what's the double-less-than sign here

[distant bobcat]

Its referring to the rate of growth for the function (asymptotic growth) from best I can understand.

I.E $logn << n^c$ for example

[vital dew]

Fredrikpiano:

[stray reef]

so $f(n) \ll g(n)$ whenever $\lim \frac{f(n)}{g(n)} = 0$, yes?

[vital dew]

Ann:

[distant bobcat]

yes, what I was thinking)

and, so you would get $0 \cdot 0 = 0$.

[vital dew]

Fredrikpiano:

[finite wren]

are there any graph theory thms and such related to this:

w() is weight

[pale epoch]

"this"?

this just looks like christofides algorithm

[finite wren]

o perfect! lol i just forgot the name of it ty

[grizzled laurel]

is this as easy as it looks?

can I just use one of the properties of symmetric difference?

But is that sufficient?

[static ivy]

clueless on where to start with this problem

then gcd(x,y) = 1```

[unreal stump]

Just reduce it to mx+ny=1 gcd(m,n)=1, and then use gcd(x,y) divides 1

[proven shard]

@static ivy divide both sides by gcd(a,b)

[static ivy]

im trying to make something up of what u both said

but im confused haha

[proven shard]

gcd(a,b) = ax + by
=> 1 = a'x + b'y where a' = a/gcd(a,b) and b' = b/gcd(a,b)
=> gcd(x,y) =1

[static ivy]

doesnt gcd definition require the form a'x + b'y to be > 0 and minimal?

i undestand what u suggested but why is it true that its the mininal equation that satisfies this

[proven shard]

Because 1 is the smallest positive integer

[static ivy]

OH

dudeee

[proven shard]

If you can Represent 1 you're Gcd 1

[static ivy]

Awesomeeee

Thank you so much man

[rugged pebble]

can someone help me prove this

[stray reef]

hint: 100 is divisible by 4.

[rugged pebble]

isnt it saying

like the last two digits of n

mod 4

is equal to n

[stray reef]

no

it says that the REMAINDER of n mod 4 is the same as that of the two last digits

[rugged pebble]

ok so how would i even start this

its so confusign

[stray reef]

think about my hint

think about some small but not too small numbers like 653 or 1432

[rugged pebble]

i still dont get it

like i am just confused on the whole thing still

[stray reef]

would you like me to take you through some examples or specifically a pointer towards the proof

[rugged pebble]

more towards the proof

[stray reef]

use the definition of modular congruence: $a \equiv b \pmod{m}$ iff $a - b$ is divisible by $m$ (or is a multiple of $m$, if you're more familiar with that term)

[vital dew]

Ann:

[rugged pebble]

oh

so lets say

n is

21343

then i can say

they are congruent if

21343 - 43 is divisible by m

[stray reef]

divisible by what?

[rugged pebble]

4

[stray reef]

21343 - 43 is divisible by m
hmmmmmmmmmmm

[rugged pebble]

no?

[stray reef]

the thonk was at your use of m specifically

[rugged pebble]

oh

[stray reef]

which i tried to hint at, but too obscurely

whatever

you've rephrased "21343 = 43 mod 4" into "21343-43 is divisible by 4"

[rugged pebble]

by the definition

thats what i thought

[stray reef]

i mean ok we're going through an example anyway

so what's 21343 - 43

[rugged pebble]

21300

[stray reef]

and is this divisible by 4?

[rugged pebble]

yes

[stray reef]

ok great

this will not be exactly how the proof goes but whatever

[rugged pebble]

so

i was wrong when i said that ?

[stray reef]

if i wanted to say you were wrong, i would've either said you were wrong explicitly or pointed out exactly where you went wrong with some remark like "how'd this happen now"

but i did not

you did not say anything wrong, you just went down a path of reasoning which bears little resemblance to the proof you're asked for

i humored you because i thought it'd help you get some ideas for the general proof

[rugged pebble]

oh

sorry i am just still learning everything

so its hard for me to understnad stuff

[stray reef]

ah great. we have an interruption don't we

[steady kernel]

Oh, sorry, haha

[rugged pebble]

ok so how is 41343 congrunet to 43(mod4)

because

41343 - 43 is divisible by 4?

[steady kernel]

,w 41340 / 4

[vital dew]

Results provided by WolframAlpha

Click here to refine your query online
Upgrade to WolframAlpha Pro!

Requested by Enigsis#2491

[steady kernel]

Yes

[stray reef]

41343 - 43 is not 41340

[rugged pebble]

ok so then

[steady kernel]

haha, sorry

,w 41300/4

[vital dew]

Results provided by WolframAlpha

Click here to refine your query online
Upgrade to WolframAlpha Pro!

Requested by Enigsis#2491

[rugged pebble]

n is congruent to a1a0(mod4)

because

[stray reef]

@steady kernel no spoilers here please

just in case

[rugged pebble]

im thinking

[stray reef]

i want anthonyvid to come to this on their own

[steady kernel]

I don't know how to prove it hahaha

I'm thinking too

[rugged pebble]

like

i cant just say n - a1a0

or can i

hm

[stray reef]

i mean, you can say anything you want

you can say "DFJHLSGJKL JSDFKLHe()^())wT306924306 V2490562#($^)#$^()90Y940Y + +$^+#^+%$+^ #+$^43^" for example

whether or not it'lll make sense is another question

whether or not it'll help you complete the proof is another question still

you can certainly talk about the number $n - a_1a_0$ --- there is no higher force forbidding you from writing down this string of symbols in particular --- and you can, for instance, notice how it's either just 0 (when $n \leq 99$) or ends in 00 (otherwise)...

[rugged pebble]

that is so confusing to me

what you just wrote

[vital dew]

Ann:

[rugged pebble]

ok so if i assume n is some positive integer with decimal expansion am,am-1 ... a2a1a0

then cant i just say

n = a1a0(mod4) iff n - a1a0 is divisible by 4

wait

did i just restate the question

[stray reef]

yeah, you can say that. i thought we went over this.

[rugged pebble]

ok

[stray reef]

you did restate the question.

in a manner which is hopefully easier to deal with.

[rugged pebble]

ok i understand everything i just said

but doesnt that show

its true

[stray reef]

maybe it does

but it's your job to make that clear to the reader

if you want i'll put on my hard-to-convince hat and have you arrive at your proof through a dialogue with me, where i think the statement you're proving is false and you're trying to convince me otherwise

[rugged pebble]

ok sure

anything i guess

so

[stray reef]

ok. i'll prefix my in-character replies with a thonk emoji to disambiguate

like this

[rugged pebble]

omg what does that mean

good or bad

[stray reef]

neither, it means i'm playing a role here and i want to make clear when i am speaking in character and when i'm speaking out of character

[rugged pebble]

ok

lol sounds good

so i need to convice you why its true?

[stray reef]

well, you can try

[rugged pebble]

ok

well its true because

n = a1a0(mod4) is true

because

[stray reef]

because what?

[rugged pebble]

by the definition of modular congruence

n - a1a0 is divisible by 4 for every value of n

[stray reef]

and why should n - a1a0 always be divisible by 4 no matter what n is?

[rugged pebble]

because

uh

hm

[stray reef]

i don't believe you when you say that. how do you know there isn't a value of n where this fails?

[rugged pebble]

ok ill prove it

[stray reef]

maybe it's something big like somewhere in the millions.

[rugged pebble]

to you

[stray reef]

go ahead, i'm listening.

[rugged pebble]

because when you subtract n by a1a0 (last two digits of n)

OH

Because

ok

actually

a number is divisible by 4 if the last two digis of it is divisible by 4, so a1a0 has to be divisible by 4, and n - a1a0 will always make n last two digits result in 0, and 0 is divisible by every number

so the last two digits(always 0) is divisible by 4, which means the number is divisible by 4

[stray reef]

a number is divisible by 4 if the last two digis of it is divisible by 4
isn't that what we're proving here, in some sense

so you're being kinda circular right now

[rugged pebble]

so are you saying you dont think its true

what im saying

[stray reef]

i am saying exactly what i intend to say and no more.

i do believe you when you say n - a1a0 will end in 00 no matter the value of n (at least for n greater than ninety-nine!)

how does that mean n - a1a0 will always be divisible by 4?

[rugged pebble]

because if n is less then 99

it will just be

0

and 0 is divisible by 4

and then

if its greater

[stray reef]

if n ≤ 99 it is equal to its last two digits

and any number's congruent to itself mod anything

so the point is kind of moot

[rugged pebble]

ok true

ok but

n - a1a0 will alwyas be divisible by 4

because

[stray reef]

my doubt has now been reduced to: why's a number ending in 00 always divisible by 4?

[rugged pebble]

ok

well

its just

common sense

[stray reef]

[rugged pebble]

ok

[stray reef]

common sense, you say

[rugged pebble]

lol

[stray reef]

that's not exactly a proof technique in math

nor is it enough to convince me

[rugged pebble]

ok then let me finish

[stray reef]

you haven't really started here.

why's a number ending in 00 always divisible by 4?

[rugged pebble]

because 4(0) = 0

0 | 4 = 4(0)

[stray reef]

that string of symbols is kind of nonsensical

you told me 0 is divisible by 4, but that doesn't really convince me.

[rugged pebble]

ok but

[stray reef]

why are numbers like 600 or 34500 or 293385204203500 divisible by 4?

[rugged pebble]

ahhhh

[minor dagger]

cus 100 divides them and 4 and 25 divide 100

[stray reef]

star

please

you spoiled it

[minor dagger]

i am too smart for my own good dang

[stray reef]

i wanted anthonyvid to come to the realization of "numbers ending in 00 are divisible by 100" by themself.

[rugged pebble]

ok but

why does that matter

[stray reef]

and this all ties in to my hint that i gave at the very beginning:

100 is divisible by 4.

[rugged pebble]

so since n - a1a0 will end in 00

100 is divisible by all numbers ending in 00

and 4 is divisible by 100

[stray reef]

no

4 is not divisible by 100

divisibility isnt a symmetric relation

[coral raven]

4 divides 100? i think it is

[rugged pebble]

omg i am so confused now

[stray reef]

'is divisible by' and 'divides' are inverse relations to each other but they arent the same

[coral raven]

and 100 divides by 4

yeah, divides is the opposite of divides by/divisible by

i think

[stray reef]

just because you have a name for the inverse of a relation doesnt make the original relation symmetric all of a sudden

[coral raven]

ofc

[stray reef]

anyway, how about we cut the nonsense

[rugged pebble]

😦

n = a1a0(mod4) iff n - a1a0 is divisible by 4

[stray reef]

n - a1a0 will always end in 00, and hence be divisible by 100.
100 is divisible by 4.
therefore n - a1a0 will always be divisible by 4.

[rugged pebble]

so since n - a1a0 is divisible by 100

and 100 is divisible by 4

then n - a1a0 is divisible by 4

[stray reef]

you repeated what i just said.

but yes

[rugged pebble]

i know

i wanted you to say yes

ok and since its always divisible by 4

that means

n = a1a0(mod4) is true

because n = a1a0(mod4) iff n - a1a0 is divisible by 4

i think

actually

i know

thats hard

[stray reef]

now you're going in circles.

you're done.

the proof is complete.

our little exercise with me playing hard to convince has paid off.

[rugged pebble]

yes it was actually fun

@stray reef

what is the last 2 digits of 99

[stray reef]

99

[rugged pebble]

ok so

99 - 99 = 0

righty

[urban olive]

Any idea on how to convert this argument into a expression? I already did the first one

[errant bear]

well considering they dont know the difference between rotate and revolve

[urban olive]

Revolve and rotate is the same according to the teacher

I know, it's weird

But how can I make that expression?

[errant bear]

let y be an arbitrary satellite

[urban olive]

Alright

This is what I got so far

But don't know if I'm good

[errant bear]

can you explain why you are using there exists

[urban olive]

I think I got confused

Since there's no planet

Let me fix it

[errant bear]

think of it as

since there does not exist a planet that satisfies

every planet must not satisfy

um i forgot the name of the law lol

[urban olive]

I get the idea, the thing is I don't know how to express it in functions and quantifiers

[burnt herald]

using characteristic equation, is the second equation:

An-1= An-2 + 2n-1 + 1?

or do I leave the 2n as it is?

[naive saffron]

Yes like what you wrote

But with

[hasty iris]

Is anyone good with logarithms ?

I need help

[minor dagger]

post your question

and not here

this is discrete math

[lusty pelican]

Hi, which axioms formula this statement uses: n+k=0 , it's AA6?

[pale epoch]

what

[stray reef]

what's the dimension of a graph?

@iron crescent

no

what's the definition of "dimension" in the context of graphs?

what

wait ok so you're dealing with partial orders here

what's the dim of a partial order

10 is not comp to 3

anyway yeah no definitions no go

and she never gives a defn of dimension?

and what's a linear extension again

uh huh

okay

i'm not sure i'm following your prof's line of reasoning as you explained it

i mean, now you have me briefed on the defns at least

that means 2,3,5 and 5,3,2 have to show up in this order.
why so

i'm not yet convinced

yeah but why does 3 have to show up between 5 and 2

or does she mean that 2, 3 and 5 have to appear together in both linear extensions with nothing inbetween?

ah wait

i think i see her point

yeah, cause any other two permutations would result in two among 2, 3 and 5 being positioned the same under both linear extensions

which we can't have

and 10 will have to come after 2 and 5 since 2 < 10 and 5 < 10 under R

so we have 2 < 3 < 5 < 10 in one linear order and 5 < 3 < 2 < 10 in the other

thus 3 < 10 in both, thus 3 < 10 under R, contradiction.

if a pair of elements is incomparable in your partial order, then they have to not appear the same way in all LEs

[stray reef]

what's your order

ok yeah b2 is incomp to a1

so that up there is wrong

[spring aspen]

what does R^(-1) mean?

does it have the same meaning with the one in linear algebra?

[stray reef]

no

R^-1 is the relation defined by (x,y) in R^-1 iff (y,x) in R

[spring aspen]

okay thanks 🙂

[burnt herald]

can someone explain what it is asking for?

[stray reef]

does there exist a graph on 5 vertices in which there are no triangles nor trios of unconnected vertices?

@burnt herald

[burnt herald]

yes

drawing a 5 sided polygon and labelling them from a to e

but a can never be connected to c

but the question writes {a,c}

[stray reef]

in the question, a, b and c are under a universal quantifier

for every three pairwise-distinct vertices...

but i mean yeah, there you have it: draw a pentagon

[burnt herald]

Thanks @stray reef

[stray reef]

@iron crescent yes

[last timber]

as ann would say all terms after 5-th are 19 identically

but looks like numerator of i-th term is i^2 and denumerator is 2^i

[near prawn]

https://media.discordapp.net/attachments/359052604149465088/615491471684009984/unknown-143.png?width=400&height=59

[stray reef]

thank you @near prawn

[deft dock]

guys

why is the distribution of prime numbers significant?

nvm

[pale epoch]

lol

[round geyser]

Is Graph Theory a good area of research

or is it kind of a dead field?

[rugged pebble]

How do I find the sum of minterms if the function F(x,y,z) = 1 iff yz = 1

[pale epoch]

@round geyser there is a lot of research on algorithmic graph theory, but that is more CS than math

in general a lot of interesting questions about graphs are algorithmic in nature (at least in my opinion)

there is also some overlap with combinatorics

[round geyser]

oh nice

Is there any research going in graph Thoery itself

without any CS applications

?

[pale epoch]

no idea

i just know a single phd student in math-related graph theory

but that doesn't say much

[proven shard]

why is the distribution of prime numbers significant?
@deft dock
Its not. Ita only of interest as a fundamental basic question to be interested in just as a question that can be asked. What's interesting about it is that the way we approach answering the question involve many tools and methods from other branches of math, and also motivates those tools and methods.

[lilac gazelle]

If I choose 5 cards from a deck of 52 cards, what would be the probability that the first card is a heart?

My reasoning was, there are (13 choose 1) ways of choosing the first card as heart, and there are (51 choose 4) ways of choosing the rest, so

13(51 choose 4) / (52 choose 5)

but this resulted in a probability over 1, what went wrong in my logic up there?

[coral raven]

??

surely it's just 1/4?

the other cards don't matter, the first one is first

[stiff bloom]

B ?

[mystic moss]

order matters :)

[lilac gazelle]

...ah, yes, that makes sense

Ty

[errant bear]

i mean you could also just do #hearts/#total = 13/52 = 1/4

[weary tiger]

Unsure about this question. Would "B" be the correct answer?

[rugged pebble]

f(x, y) = 2x - 4y how do i check if this is onto or one to one

[burnt herald]

how does one tackle this

[burnt herald]

Thanks!!

[peak heron]

There are $n$ students in a school who are preparing for a party to be held. Some pairs of students of the opposite gender have some degree of attraction to each other; there is no pair of students of the same gender that are attracted to each other. The principal of the school, Shourya, hates parties and plans to sabotage their attempt at a good time.
The students have to come up with a natural number $k$. Then, the principal assigns a set $X_e$ of code-words to a pair of students $e = {s_1, s_2}$ attracted to each other, where $|X_e|=k$.
Each such pair of students who like each other now has to choose one of the $k$ code-words from the set assigned to the pair. The main condition, called the Law of Non-interference, is that no student should have the same code-word with two different people that student is attracted to.

Abhay, the Don Juan of the school, is preferred by the highest number of people in the school; Exactly $\Delta$ girls in the school are attracted to him.

Find the least integer $k$, in terms of $n$ and $\Delta$, which guarantees that no matter what sets of code-word sets the principal assigns, the students can agree upon a coding scheme so as to not violate the Law of Non-interference.
Note; that attraction is mutual in this school. Unfortunately, that's not true in real life...

[vital dew]

TwilightWings_52

[near prawn]

check the definitions

[peak heron]

Anyone please give me its solution

[rich oasis]

The domain of relation P is {2, 4, 6, 8}
For x, y in the domain, xPy if ⌊𝑥/𝑦⌋ ≥ 1

anyone able to help me figure out how to build the relation set for this I dont understand what I need to do in order to get outputs.

I can't figure out how to make this into something like R = { (1, 1), (1, 3), (2, 1), (3, 2), (3, 3), (4, 1), (4, 4)} so that I can make a arrow diagram and do the matrix representation

[pale epoch]

you take all the elements $(x, y) \in P \times P$ and check if $\floor{\frac{x}{y}} \geq 1$

[vital dew]

Lochverstärker

[weary tiger]

can someone please explain how that sum has changed

how did they turn 2^(n-k-1) into 2^k

[pale epoch]

its basically summing up the other way

so change of variables to n-1-k

@weary tiger

[deft dock]

@proven shard so there is no practical use of finding the distribution of prime numbers using reimann's hypothesis? its only a matter of just finding it?

[proven shard]

yep

it may be the case that the journey towards an answer leads us through lots on interesting mathematics which may have a practical application, but I wouldn't say that the distribution of prime numbers is of practical importance. Its just a really fundamental, basic human question, so we investigate it.

[weary tiger]

@pale epoch yeah i just dont understand how they did this change of variables

[peak heron]

There are $n$ students in a school who are preparing for a party to be held. Some pairs of students of the opposite gender have some degree of attraction to each other; there is no pair of students of the same gender that are attracted to each other. The principal of the school, Shourya, hates parties and plans to sabotage their attempt at a good time.
The students have to come up with a natural number $k$. Then, the principal assigns a set $X_e$ of code-words to a pair of students $e = {s_1, s_2}$ attracted to each other, where $|X_e|=k$.
Each such pair of students who like each other now has to choose one of the $k$ code-words from the set assigned to the pair. The main condition, called the Law of Non-interference, is that no student should have the same code-word with two different people that student is attracted to.

Abhay, the Don Juan of the school, is preferred by the highest number of people in the school; Exactly $\Delta$ girls in the school are attracted to him.

Find the least integer $k$, in terms of $n$ and $\Delta$, which guarantees that no matter what sets of code-word sets the principal assigns, the students can agree upon a coding scheme so as to not violate the Law of Non-interference.
Note; that attraction is mutual in this school. Unfortunately, that's not true in real life... [Please anyone solve this problem]

[vital dew]

TwilightWings_52

[opaque fern]

Need help with this

[opaque fern]

<@&286206848099549185>

[last timber]

7310=72*101+38

[vital dew]

The Duke of Ankh

[last timber]

wait somehow this is stupid

51^72 would be still hard

[opaque fern]

Hmmmm

What do you mean

[last timber]

oh wait nvm

@opaque fern i mean

https://media.discordapp.net/attachments/496785905474994186/782809544479735818/694042020100046990.png?width=960&height=224

[vital dew]

The Duke of Ankh

[peak heron]

Why anyone is not answering my problem?

[errant bear]

why do you keep posting problems demanding answers when you havent said what you've tried etc

[shut jacinth]

hi @errant bear

can u help me c:

[opaque fern]

This is what I got

[opaque fern]

Is it correct ?

[shut jacinth]

to explain the range of this

in set roster notation

[opaque fern]

Hey bud kinda occupied ^

[shut jacinth]

{x | 2 <= x <= 5}

o

sorry

[last timber]

why mod 100

[opaque fern]

101-1

Sorry for the penmanship

It’s bad 😂

[last timber]

sorry igtg, but you kinda unreasonably got 100

as for me

but i may be wrong

oh wait i got your idea

wait a couple of mins

[opaque fern]

Okay

[last timber]

oh ye

you get to 51^10 mod 101 by both appoaches it is alright

,w 51^10 mod 101

[vital dew]

Results provided by WolframAlpha

Click here to refine your query online
Upgrade to WolframAlpha Pro!

Requested by Commander Vimes#7532

[last timber]

@opaque fern

somehow

[opaque fern]

Hmmm

[last timber]

why

why

[opaque fern]

Did that to know which remainders to multiply at the end

[last timber]

why tf you need 16 power

if you are to find 10

[opaque fern]

Oh wow

Noob mistake 😭😭

Sorryyyyy

I see where I went wrong

I have the correct computation tho

Just need do 58*76

Those 2 remainders

And whatever the result from that is divide by 101 and the result of that multiply with 101 then subtract it with the result of 58*76

Haha sorrry if it don’t make sense just a chain of thoughts @last timber

[pale epoch]

what do you mean how? they just did
as i said this is equivalent to doing the sum the other way, just think about what the first and last term of the original and the new sum are

[gleaming zephyr]

hi

can i send some1 some graph theory

questions and check with him/her

the answers?

in dms

[stray reef]

him/her

[brittle inlet]

😌

[topaz tendon]

B'C' + A'B'D + AB'D' + A'BCD' + ABCD

B'C'+A'B'D+AB'D'+BC(A'D'+AD)
B'C+A'B'D+AB'D'+BC(AxD)
B'C+B'(AxD)+BC(AxD)

what

should I do with

A'B'D+AB'D'

[fast temple]

I haven't checked the rest of the function but the one you put in the code block is as simplified as it can get

if you use a k-map you can see the two squares are not adjacent

[topaz tendon]

but you can't simplify

A'B'D+AB'D'

Shouldn't it be xor?

[fast temple]

sure it can be made $B'(A \oplus D)$

[vital dew]

bitter

[topaz tendon]

how come

oh

yeah

im stupid

ofcourse

thank you

[fast temple]

The reason I didn't bring it up is because in the context of digital design XOR is not simpler than A'D + AD' and factoring out the B only means you're going to use more gate-levels which increases propagation time

[topaz tendon]

B'C' + A'B'D + AB'D' + A'BCD' + ABCD

B'C'+A'B'D+AB'D'+BC(A'D'+AD)
B'C'+A'B'D+AB'D'+BC(AxD)
B'C'+B'(AxD)+BC(AxD)

this is the simpliest we will get

[fast temple]

are you using x here to refer to XOR?

[topaz tendon]

yeyeyyee

[fast temple]

oh I see

then yeah I'd say that's as simple as it gets depending on how you define simple

[topaz tendon]

but why isn't xor simple?

[fast temple]

because when implemented in hardware it's not one gate IIRC, you need 3 gates and 2 inverters.

and factoring out the B' in the first place means you're increasing your gate-levels by one which is usually avoided

and judging by the notation you're using I'm guessing you're doing digital design?

[topaz tendon]

yes

[fast temple]

how far in are you?

[topaz tendon]

idk, this is my first course, but we have talked about state machine, AD, VHDL

[fast temple]

this is what I was talking about

[topaz tendon]

but we

got

IC

xor

chip

[fast temple]

I think there are logic families that have XOR gates but I'm not entirely sure

I'm also a beginner in this

[topaz tendon]

I think it is incorrect
because when I did truth table it didn't match up with the original form

[fast temple]

can you give me the original function

I can try to simplify it

I'm actually studying for my digital design midterm right now :D

[topaz tendon]

B'C' + A'B'D + AB'D' + A'BCD' + ABCD

[fast temple]

I got $B'C' + C(B \oplus D)$

[vital dew]

bitter

[fast temple]

@topaz tendon

[topaz tendon]

I think it is wrong because the truth table is now shorter 😦

[fast temple]

Yes because A is no longer in it

[fast temple]

if you look back at the original function you can see that A is irrelevant

[topaz tendon]

what about this function

[fast temple]

do you know k-maps

[topaz tendon]

yes

[fast temple]

start with that

it makes things a lot easier

[topaz tendon]

the thing is

[fast temple]

I just did the k-map for it

it's the same one as above

[topaz tendon]

00, 11, 10, 01, 00, 11 ...
01, 00, 01, 10, 11, 00, 01 ...
10 ,11, 10, 01, 11, 10

we have a counter,

when the code is 00 then it should count 11, 10, 01, 00, 11
when the code is 01, 00, 01, 10, 11, 00, 01
when the code is 10, 11, 10, 01, 11, 10

It removed that

[fast temple]

you mean greycode?

[topaz tendon]

yes

[fast temple]

1,2,4,3

that's the pattern to it

[topaz tendon]

yeah

[fast temple]

once you get that down you get really quick at kmaps

(more correctly 0 1 3 2)

[topaz tendon]

but kmap is not the problem

but

as you can see

[topaz tendon]

this truth table does not represent the counter anymore

[fast temple]

It's just the upper half of it

but I now see I made a mistake

it should be $B'C' + C(A \oplus B \oplus D)$

[vital dew]

bitter

[fast temple]

I should have caught that my bad

I gotta say though I find it odd they're making you simplify functions with XORs

[topaz tendon]

correct

well my teacher said, that We can only use two OR grind

but why is it odd ?

oh you exlpained it already

[fast temple]

the pun with "odd" and "XOR" is not intentional :D

[topaz tendon]

lol

thanks again

😄

[fast temple]

np

sorry for the mistake

I should have been able to see that it's A xor B xor D from the checkerboard pattern on the k-map

wait let me draw it for you

[topaz tendon]

np everyone makes mistakes

how would you do that

lol

[distant sentinel]

man idk which channel to go to

I need help with this two

:/

[fast temple]

this looks like an algebra problem

[distant sentinel]

which channel do i go to?

[topaz tendon]

btw

why did you get

C(AxBxD

[fast temple]

This is the K-map

On the left half we have B'C', I think that part is clear

on the left side we have a checkerboard pattern

when you have that it means you either have an odd function (XOR) or an even function (equivalence)

We can verify that it's an odd function by inspecting one of the squares

at that point it's as easy as seeing that C is the only constant

so you get $C(A \oplus B \oplus D)$

[vital dew]

bitter

[fast temple]

I hope that makes it clear

XOR and equivalence gates are the hardest to implement in hardware because of this checkerboard pattern, there are no adjacent squares.

[topaz tendon]

but I dont understand

what is it that it makes difficult

that you need more grinds or ?

[fast temple]

the logic is just more complex

compare it to an AND gate or an OR gate

for an AND gate there is only one combination of inputs that gives 1

and for OR gates there is only one combination of inputs that gives 0

for odd or even functions there is an equal amount of input combinations that give 0 or 1

[topaz tendon]

what do you mean by combinatino

[fast temple]

00 01 10 11

those are the four combinations of 2 inputs

for $n$ inputs there are $2^n$ combinations

[vital dew]

bitter

[topaz tendon]

yeah

true

[fast temple]

so this is especially true as your scale up your inputs

[topaz tendon]

how many combination if you have xor grinds?

[fast temple]

I'm guessing by grind you mean gate?

the number of combinations is dependent on the number of inputs, not the operation

but this is what I meant

take the case of 2 inputs, 00 01 10 11

For AND, only 11 gives output 1, others give 0

for OR, only 00 gives output 0, the rest give 1

for XOR, 01 and 10 give 1, that's twice as many

and it only becomes worse as you increase the inputs

[topaz tendon]

ye

gate

but You can't fault your self if you get xor

while simplifying

it

[rugged pebble]

is this symmetric or anti symmetric

x^n = y

from Z+ to Z+, for some positive int n

[versed summit]

Alright I'm sorta losing it on this problem

Specifically part e

I'm not sure what to even do, I could do the other ones fairly easily but n4^n is like blowing my mind and not in a nice way

[coral raven]

just try it

[versed summit]

Yeaaaaah so I got

[coral raven]

and consider that 4^n = 4(4^n-1)

[versed summit]

32n^(n-1)-32^(n-1)-64n^(n-2)-128^(n-2)

And I know that is so very wrong

But every time I would attempt it I would circle back to that somehow

[coral raven]

okay

stupid question, why are there 4 terms

shouldn't it just be 2

[versed summit]

I distributed

The 8(n-1)4^(n-1)

[fast temple]

$8(n - 1)4^{n - 1} - 16(n - 2)4^{n-2}$

[vital dew]

bitter

[fast temple]

Now we distribute

$8n4^{n - 1} - 8 \cdot 4^{n - 1} - 16n4^{n - 2} + 32 \cdot 4^{n - 2}$

[vital dew]

bitter

[fast temple]

Now we recognize that 8 = 4 * 2; 16 = 4^2; and 32 = 2 * 4^2

$= 2n4^n - 2\cdot 4^n - n4^n + 2\cdot 4^n$

[vital dew]

bitter

[fast temple]

cancel cancel

$n4^n$

[vital dew]

bitter

[versed summit]

Oh wow I was way off on the process

Ahhhh I see it now

[rotund swallow]

how would i do part b?

[sweet sleet]

Does anyone have a source that provides a full proof for the integer partition identity that the number of partitions of $n$ into parts of the form $5k + 1$ and $5k + 4$ equals the number of partitions of $n$ whose consecutive parts differ by at least 2.

I believe that this is one of the Rogers-Ramanujan identities.

I have reduced the problem down to $\prod_{n \geq 0}\frac{1}{(1 - x^{5n + 1})(1 - x^{5n + 4})} = {{\sum_{k \geq 0}} \frac{x^{k^2}}{(1 - x)(1 - x^2) \dots (1 - x^k)}}$, so if you provide a proof of this sum to product identity that would also be very helpful.

Additionally, if there is a combinatorial interpretation of the above identity that would again be very helpful.

Thank you very much in advance!

[vital dew]

hendrix

[sweet sleet]

please ping me if do you, thanks

[mystic moss]

@agile lava what about this exactly?

[agile lava]

writing an algorithm for the graph problem

proof for NP I guess..

[mystic moss]

which one?

[karmic nymph]

are there multiple different possible DFA equivalents ?

i have got one, but its not the same as the model solution

[last timber]

hm

[agile lava]

6 is algorithm

3-5 is proof

[last timber]

@karmic nymph is epsilon empty string?

[karmic nymph]

its a jump

ive found another method of finding the DFA equivalent but they look different

so just wandering if its fine

[last timber]

what is "a jump"

[karmic nymph]

ummmm

like

[mystic moss]

yeah i think it's the same as empty string

[karmic nymph]

if the input is empty then you can make that transition

[last timber]

so basically empty string

[karmic nymph]

yeah my bad lol

[mystic moss]

@agile lava can't we reduce vertex cover to the first problem?

[last timber]

@karmic nymph

you probably had 4 states

one {s,p}

but if you look

it is the same as {s} actually

indistinguishable

[agile lava]

wdym

[mystic moss]

like for (6) they just defined the problem, but are you actually supposed to find an algorithm?

[karmic nymph]

i see

[karmic nymph]

which program did u use to make that? i can show u mine

[last timber]

jflap

[karmic nymph]

ok

@last timber

[last timber]

what is this

[karmic nymph]

lol

DFA from NFA in question

https://media.discordapp.net/attachments/496785905474994186/783329497997901864/unknown.png

[last timber]

how the fuck

establish original one

[karmic nymph]

wot happend

[last timber]

convert

[karmic nymph]

doesnt it need to a transition at q1 to null

when input is b

[last timber]

wym

[karmic nymph]

okay yeah im confused

[dreamy tusk]

Can I ask a basic algebra 2 question

[last timber]

not in here

[dreamy tusk]

Im really lost and need help

[last timber]

use algebra or q channel

[dreamy tusk]

where do I find that?

[karmic nymph]

its not a DFA if theres no option for b at q1

[last timber]

oh wait i got em

ye they just added trap state

otherwise it is the same as jflap's

[karmic nymph]

i see

can there be multiple equivalent DFA's for an NFA ?

[last timber]

only up to configuration of trap states afaik

and labeling states

[karmic nymph]

https://cdn.discordapp.com/attachments/496785905474994186/783342957184942082/unknown.png

this works too tho?

[last timber]

why the fuck you need these three states

they all collapse to one easily

[karmic nymph]

i guess so

i just followed an algorithm i found online

[dreamy tusk]

How would you factor this?

[minor dagger]

this isnt discrete math this is a question for #prealg-and-algebra

[dreamy tusk]

what is descrete math anyways?

[minor dagger]

its math in discrete quanitity

[errant bear]

its secret math

[amber prism]

di-secret math?

[errant bear]

booo

[mint bane]

in proving a) and b) here, my solution is to rewrite bc/a as (b sub 1 + b sub 2 + ... + b sub c)/a and then separate that into individual fractions, then use contradiction saying if a doesnt divide bc then that implies it a doesnt divide b, so it must divide bc

is this a valid proof

b) being a variation of that ofc

[agile lava]

oh...yeah, just misunderstood the problem

just definition is ok

[mystic moss]

wdym? they defined it for you. what does the problem say, exactly?

[agile lava]

the definition of the optimization algorithm

[fluid tendon]

Number 3 for Hamilton cycle and graph iso

[fast temple]

is the statement $f(x)$ is $O(g(x))$ different from the statement $g(x)$ is $\Omega(f(x))$?

[vital dew]

bitter

[fast temple]

If not then why does the big omega notation exist?

From what I can tell it seems like it's there to set up big theta but we can describe the idea "f(x) and g(x) are of the same order" using only the big-O notation.

[sterile otter]

Idk if this counts as discrete math or calculus. Anyways, in this discrete math book, it said some definition of the derivative which I didn't understand it said something like

$f(x+\epsilon) = f(x) + M\epsilon + o(\epsilon)$

[vital dew]

Neophiliatic

[pale epoch]

@fast temple depends on your definition of big omega

if you come from algorithmic complexity, what you said is correct

and i think Knuth defined big omega that way

see https://www.phil.uu.nl/datastructuren/10-11/knuth_big_omicron.pdf

the tl;dr is that hardy and littlewood defined it differently (in terms of limsup) and that is (slightly) weaker than what knuth did

in fact landau introduced two more symbols

landau, hardy and littlewood didn't care about complexity of algorithms though

they did this to describe bounds in analytic number theory

[fast temple]

I see, I'm studying it in the context of complexity of algorithms

I guess I'll take it as a more convenient way of expressing that g(x) is the best case for f(x)

[pale epoch]

then your observation is (probably) correct

i have never used big omega

other than in some exam

in fact i rarely use big theta now, so there is that

@sterile otter what part do you not understand?

[sterile otter]

The o part.

[fast temple]

thank you for the help!

[sterile otter]

So like I know what it is.

[pale epoch]

it is some term that is asymptotically bounded by epsilon

[sterile otter]

But I don't understand it completely.

[pale epoch]

(strictly)

[sterile otter]

So can I compute a derivative using that definition?

[pale epoch]

what is M?

[sterile otter]

f'(x):

[pale epoch]

this implies that you already have the derivative

but in theory, yes

if M is a linear function

so the idea here is

that close to x, f(x) is "almost linear"

[sterile otter]

Yeah.

[pale epoch]

and the o(epsilon) makes sure that the error is not too big

[sterile otter]

Oh. I think I'm starting to get it now.

[pale epoch]

i.e you need

the error has to converge faster than epsilon to 0

[sterile otter]

Okay.

[pale epoch]

weird that this is in a discrete math book though

you would need this in analysis in more dimension

because this is the correct way to define the derivative in higher dimensions

[sterile otter]

Oh okay.

[pale epoch]

in the single variable case, M will be some number

i.e. f'(x)

in multivariable case it's some matrix

which then plays the role of the derivative

[sterile otter]

How can I work out o(h) if its even possible?

[pale epoch]

it's the error you make when approximating the function close to x by it's derivative

[sterile otter]

So you can only work it out knowing the derivative?

[pale epoch]

yes

you can define it by r(epsilon) = f(x+epsilon) - (f(x) + M*epsilon)

where now r(epsilon) is the error you make when you approximate the function at x+epsilon by it's derivative

and the o(epsilon) part means

$\lim_{\varepsilon\to 0}\frac{r(\varepsilon)}{\varepsilon} = 0$

[vital dew]

Lochverstärker

[pale epoch]

or in words: the error converges to 0 faster than linear

[sterile otter]

Ok.

[normal dragon]

Can anyone please help me with this question?

<@&286206848099549185>

[versed summit]

So for part d, I got to 14^(n-1) - n + 28^(n-2) + 8, is that right so far?

[versed summit]

Yeah I've hit a wall. I can't do anything with that equation

[mystic moss]

yeah but what does it ask you to find

[fluid tendon]

Number 3 for hamiltonian or graph iso

[crystal dove]

Is there an easy way to find the hamiltonian path through the cayley diagram of a symmetric group?

Given two generators, such as an n-cycle and a transposition.

[daring beacon]

for 9 take away 6. The answer key is saying it is 84, but I keep getting 168. Can someone help?

[turbid nacelle]

Alternatively,
9C6 = 9!/(6!x(9-6)!) = 9x8x7/3! = 504/6 = 84

[daring beacon]

Ohh shit I get it now I feel so stupid

[turbid nacelle]

@versed summit I don’t think you are supposed to get 14 or 28

[versed summit]

what

i am confusion

[turbid nacelle]

u cant combine 7 * 2^n-1

[worthy sky]

Hello

May I have help with this question please?

I was thinking to utilise even parity on part a), but that only detects errors.

[fast temple]

You only need 2 bits to code the four directions

[radiant trail]

Hey, does anyone know how to calculate how many relations that are both antisymmetric and symmetric exist on a finite set with n-elements.

[pale epoch]

what have you tried

[radiant trail]

well in my head the only relations that can both be symmetric and antisymmetric are ones were both elements of the relation are the same so the number of relations that are both antisymmetric and symmetric would be equal to the number of elements in the set.

I'm not sure if this is the right way to think about, the only relation i can think of that is both symmetric and antisymmetric is = and that's where my thinking is coming from.

[pale epoch]

seems to be mostly correct thinking

in a relation that is both symmetric and antisymmetric, each element will be of the form (a, a)

but then for every element a in the set you have a choice of whether or not to include (a, a) in the relation

so your conclusion is not quite right

like, for example on the set {1, 2} the relations that satisfy that are {}, {(1, 1)}, {(2, 2)} and {(1, 1), (2, 2)}, right?

maybe you can generalize that

[radiant trail]

the set of relations seems similar to a power set

[pale epoch]

indeed

notice that for every element in the set you have exactly two choices

include or not include (a, a)

[radiant trail]

i think i understand it now, thanks a lot!

[weary tiger]

um nobody answered in the question channel and i was told that i could try posting here!

[signal rampart]

Modulo question:

If we're solving for x and we are given the values of all other variables (A B), how do we deal with the 2 in an equation such as: 5x + 2 ≡ A(mod B)??

Ive searched online and everything and theres just examples without an addition.

[urban scroll]

hey guys I have a question related to graph theory how would I go about solving this?

[coral raven]

dijkstra's algorithm?

[urban scroll]

yeah are you familiar with it by any chance?@coral raven

[pale epoch]

dijkstras algorithm is literally instructions on what to do

[hoary dock]

how can i show it

[coral raven]

i think you can combine the nCk and the (-1)^k/(z+k) after using the factorial definition

[hoary dock]

how

[coral raven]

what's the factorial definition of nCk

[hoary dock]

((n)(n-1)...*(n-k+1))/k!

i was afk

[coral raven]

okay

uhhh what was my argument again lol

okay nvm what i was saying

[hoary dock]

i tried with induktion but

couldnt do it somehow

[coral raven]

okay imo

try expanding the sum so you can see it more easily

and try to put everything over the common denominator (z+n)!

[hoary dock]

yes i will try again

[onyx osprey]

Any help?😅

[coral raven]

... this one is #calculus lol

[onyx osprey]

Imma try to simplify but eleminating n! But cant do it

Oh😂

[coral raven]

i think

[onyx osprey]

New in the server

[coral raven]

np lol

same

i'm just good at sounding authoritative i think

involuntarily

[hoary dock]

i said that n!/z*...z+n = 1/z*(z+n)Cn

[coral raven]

i can't read that

i don't understand

[hoary dock]

n!/(z*...(z+n)) = 1/(z((z+n)Cn))

[coral raven]

no, i didn't mean for you to collapse the RHS

i think you should expand the sum on the left hand side, write out the first few terms

[hoary dock]

to understand how it goes or

?

[coral raven]

yeah

and also to try and have common denominator

(z+n)!

[hoary dock]

something like (z+n)! on the left hand site

should i find you are saying

[coral raven]

the LHS won't directly be (z+n)!

but you can combine all the fractions into one with (z+n)! denominator

and i think that should simplify

[hoary dock]

idk how can i do that simple

lel 🙂

[signal rampart]

Modulo question:

If we're solving for x and we are given the values of all other variables (A B), how do we deal with the 2 in an equation such as: 5x + 2 ≡ A(mod B)??

[hoary dock]

i stuck

again

[coral raven]

what's the problem

what do you have now

[hoary dock]

idk how can i add the left side

[coral raven]

what do you have now

[hoary dock]

1/x - n/(x+1)+ n*(n-1)/2(x+2)-....+(-1)^k/x+k

when i add this

bottom side is x+k!

[coral raven]

okay

[hoary dock]

but i said x to z

and k to n

[coral raven]

so now you can multiply each fraction's tops and bottoms so that the bottoms are (z+n)! i think

[hoary dock]

it fits perfekt but the upper side its suck

[coral raven]

okay right

[hoary dock]

yea

[coral raven]

that's expected

gods i hate sigmas

[hoary dock]

i have did this before too

but i couldnt move when i try to add upper side

[coral raven]

lemme try

i don't actually know if this is the way to go lol

[hoary dock]

haha 😄

i think it can be with induktion

but i tried but stuck again

[coral raven]

oh wait

it goes + - + - + -

so try method of differences

consider each pair of the things

?

[hoary dock]

method of differences

?

[hoary dock]

aah

okay

[coral raven]

i'm trying it rn, there's a little cancelling going on, unclear whether it's enough

@hoary dock okay i was trying the induction

so if it works then z = 1 should work

so inducting over n:

for n = 0, we get 1 = 1 and it works

but assuming n

and z = 1

i get the sum is n!(z-1)!/(z+n)!, just a different way of writing it

so n!/(n+1)! = 1/(n+1) when z is 1

now firstly if n+1 is even, then sum from 0 to n+1 = sum from 0 to n + the n+1 case, by the LHS

so 1/(n+1) + 1/(n+1) = 2/(n+1) =/= 1/(n+2)

so it doesn't work? idk what i've done wrong

[hoary dock]

it should work 🙂

[coral raven]

no but when i did it it doesn't work for z = 1

what did i do wrong

[hoary dock]

idk

[coral raven]

can you try it for z = 1

try to do induction on n

[hoary dock]

ok i will try

but its that

i mean it's a known equality

or nvm idk

[coral raven]

ohhhhh

okay it's probs right lol

i'm not actually good at maths btw

[hoary dock]

hahaha 😄

[coral raven]

wait

wait

[hoary dock]

what are u studying

[coral raven]

it says z =/= 0, 1, 2... n

so that would have been helpful >:I

[hoary dock]

but

in my Homework

it doesnt say that

[coral raven]

your homework sucks

teacher is bad

i'm annoyed

[hoary dock]

haha 😄

[coral raven]

i was trying induction for z = 1

okay z = -1 then and let's go down ig

and then i'll also have to do z = n+1 and go upwards??

[hoary dock]

ya probably :

[hoary dock]

?

[coral raven]

maths

i'm just not actually that good at it lol

[hoary dock]

hahaha 😄

[coral raven]

okay let's try this again

wait

okay well i'm not doing (-2)!

that's not a thing

so just need to do z = n+1

[hoary dock]

what 😄

[coral raven]

i'll explain if it works

[hoary dock]

yea i tried with n --> n+1

but couldnt figure it out

[coral raven]

i'm just trying z = n+1 rn

inducting over n

and then i'll do z -> z+1

maybe

[hoary dock]

okey

[coral raven]

hopefully

ok i can not be bothered and at this rate i will run out of paper

it does not want to work for me

try googling how other ppl have done it

[hoary dock]

ok nope

i want to ask another question

if its absolutly convergent, so too converges absolutly

it says an is convergent than a^2n convergent too

when its absolutly convergent i know its true but for this is it true or false