discrete-math

[mint bane]

by definition it has one divisor besides 1

[weary tiger]

can two numbers smaller than a prime multiplied be multiple of it?

[mint bane]

no

unless ur cheesing with 1*1

oh wait

[mint bane]

this is like 90% of the forwards direction isnt it

[weary tiger]

maybe

[mint bane]

👀

[vital dew]

nitezba

[mint bane]

that's forward direction i think

[weary tiger]

yea x=0 mod n iff x is multiple of n

[mint bane]

but im never using that hint it provided

and i feel like the backwards direction is a regurgitation of the forwards direction

wait backwards is much easier by contrapositive

[stray reef]

that + the associative law

you want to be hyper-formal about it?

cause then youll also need the commutative law

brb in 5 min

here

8 lines of pointless bureaucratic mumbo jumbo to prove your equality with 5 applications of the associative law and 1 each of commutative and idempotent laws

& = intersection, ' = complement

[weary tiger]

Pretty cool problem, show: $$\sum_{k=0}^{n} k \binom{n}{k} D_{n-k} = n! = \sum_{k=0}^{n} \binom{n}{k} D_{n-k} $$ Where $D_n$ is number of derangements of a set of size $n$.

[vital dew]

Godel

[civic horizon]

You probably want your sum to index with k instead of i

[weary tiger]

Of course, thanks.

[vital dew]

Godel

[civic horizon]

Is this true

[weary tiger]

Surprisingly yes

[civic horizon]

The leftmost expression has an extra k

Compared to the rightmost

[weary tiger]

That's why I found it interesting, seems false at first.

[civic horizon]

But the number of derangements is nonnegative

So the LHS is necessarily greater than the RHS

[weary tiger]

But because k can be 0, there is no first term on the LHS.

[civic horizon]

Hmm

[civic horizon]

Showing that the RHS is equal to n! seems simple

Every term on the RHS counts the number of permutations which hold k elements fixed

As k runs from 0 to n we find that it counts every permutation once

[weary tiger]

Yes

LHS isn't that much harder.

[weary tiger]

Hello there

I have hard time finding secure asymmetric encryption
some people recommend ECC but there are a lot lot of them
threat level is very big
and needs to safe for around 5-10y time

the encryption should be fast preferably(but not needed)

[weary tiger]

💀

[pallid belfry]

Hello. I am doing a project on finite state machines and I need to know some back ground about it ie. what math topics do you need to know before you get into learning FSMs?

[obtuse lance]

nothing really

can't hurt to know a little modular arithmetic or graph theory but definitely not a prereq

if anything it might be better if you've programmed a little, FSMs are equivalent to regex, so you can think of it as motivation for learning to understand regex

[pallid belfry]

@obtuse lance How about like set theory or something like that? I have seen a few videos and they talk about sets and subsets

[obtuse lance]

yeah I guess so, but you won't need too much probably past the basics, union and intersection etc

[fallen vigil]

can someone explain this to me? it's under bernuolli trials

I can hardly wrap my head around it

[stray reef]

@fallen vigil are you still here and do you still need help w/ this?

[urban sluice]

@stray reef I know this comes as rude, but do you mind helping me?

[stray reef]

ungh

is it that stuff youve posted in #geometry-and-trigonometry

[fallen vigil]

Yessir, if possible

[stray reef]

i'm not a sir

don't call me sir

anyway

[fallen vigil]

my bad, it’s a local thing where I live

[stray reef]

do you agree that the probability of getting the sequence HHHHTTT is (2/3)^4 * (1/3)^3?

you call everyone sir where you're from? even women?

[fallen vigil]

yea pretty much

[stray reef]

mkay

[fallen vigil]

lol, also I’m a little confused on that

I get where the numbers come from ofc

[stray reef]

the flips are independent

the probability of heads is 2/3 and that of tails is 1/3

therefore, to get heads on the first flip, heads on the second, heads on the third, heads on the fourth, tails on the fifth, tails on the sixth and tails on the seventh,

you would have

2/3 * 2/3 * 2/3 * 2/3 * 1/3 * 1/3 * 1/3

[fallen vigil]

hmmm should I have an intuition on this? It looks similar to counting but it doesn’t make sense to me to multiply probabilities

[stray reef]

okay sorry for the delay on my end

but how familiar are you with the concept of independent events? @fallen vigil

[fallen vigil]

if I remember the definition correctly, knowing the outcome of one event doesn't change the probability of future events

so basically the probabilities of each event have nothing to do with eachother

[stray reef]

so you understand it in terms of conditional probability

yeah, that's equivalent to $P(A \cap B) = P(A)P(B)$

[vital dew]

Ann

[stray reef]

as in, $P(A|B) = P(A)$ is equivalent to $P(A \cap B) = P(A)P(B)$ as long as $P(B)>0$

[vital dew]

Ann

[fallen vigil]

right, so that means (2/3)^4+(1/3)^3 is the probability of the outcome we're looking for?

[stray reef]

no

not plus

[fallen vigil]

oh right sorry

was typo

[stray reef]

(2/3)^4 * (1/3)^3 is the probability of the specific outcome HHHHTTT

i.e. that not only do we get exactly four heads but we get them in the first four flips specifically

[fallen vigil]

alright that part makes a lot more sense now

so C(7,4) is the number of every outcome with 4 heads right? when we multiply it by the probability of HHHHTTT it vaguely makes sense but not quite

[stray reef]

yes

C(7,4) is the number of ways we could get four heads

each arrangement of heads has the same probability of (2/3)^4 * (1/3)^3 and is mutually exclusive with all the others

so to find the probability of getting one of these arrangements we add them all up

we are adding (2/3)^4 * (1/3)^3 + (2/3)^4 * (1/3)^3 + (2/3)^4 * (1/3)^3 + (2/3)^4 * (1/3)^3 + (2/3)^4 * (1/3)^3 +...

C(7,4) copies of (2/3)^4 * (1/3)^3

[fallen vigil]

ok so that makes a lot of sense, dumb question would that come out as less than one though?

I could just do that math on that tbh

kk it all checks out and makes sense to me now lol

@stray reef thanks for da help

[stray reef]

yes it would come out as less than 1

[uncut matrix]

A basic counting problem, but if I were trying to design a password between 7 to 9 characters and at least one character would have to be a letter, with the remaining ones being alphanumeric, how many different combinations are there?

I'm not sure if I have it right, but I'm thinking I could represent alphanumeric letters as 10 + 26 = 36, letters as 26, and digits as 10. Then, I could let P7 = 26 * 36^6, P8 = 26 * 36^7, and P9 = 26 * 36^8 and then just sum up P7, P8 and P9. Would this be correct or not? The book seems to imply that the method is to sum up (36^7 - 26^7 + 36^8 - 26^8 + 36^9 - 26^9)

[stray reef]

your method places the obligatory letter as the first character in the password

[lost axle]

8 plus 2???

[weary tiger]

over what ring?

[surreal surge]

does anyone know how to implement this function:
f(1,2,1) = 3
f(1,2,2) = 5
f(1,2,3) = 8
f(1,2,4) = 13

f(2,6,1) = 8
f(2,6,2) = 14
f(2,6,3) = 22
f(2,6,4) = 36

[pale epoch]

implement?

also you just gave a finite set of values. are those all? if yes, where is the problem? if no, you need a full description of your function

[weary tiger]

powersets dont have co-domains. The function has one

B is probably a subset of {a,b,c}

So f takes a subset of that as input and outputs a number @spark silo

[weary tiger]

Do you know what injective and surjective mean?

tell me what it means to be injective

[quick folio]

not surjective

[weary tiger]

tf

i told you to tell me what injective means

not alternative names for it

[quick folio]

i mean they did thooo

but reword ur definition

also learn the formal definition

look it up

[weary tiger]

do you know what domain and codomain mean

a function only has 1 domain and 1 codomain

[quick folio]

lol

[weary tiger]

a function is injective if whenever f(x)=f(y) then x=y

[vale shell]

https://youtu.be/4IWXam0xHC8

[weary tiger]

the simplest math proof is proving something that is an axiom

[weary tiger]

Uhhhhhhhh I guess one can try to prove ZFC

Not sure how far he'll get

no

[quick folio]

zfc

Lol

[weary tiger]

well if you find some x, y that have same image

then its not injective

equivalently if for all x, y s.t x =/= y you have f(x) =/= f(y)

to prove injectivity

[surreal surge]

progress:

f(2,2,1) = 4 * 2 - 2
f(2,2,2) = 6 * 2 - 2
f(2,2,3) = 10 * 2 - 4
f(2,2,4) = 16 * 2 - (4 * 2 - 2)
f(2,2,5) = 26 * 2 - (6 * 2 - 2)
f(2,2,6) = 42 * 2 - (10 * 2 - 4)
f(2,2,7) = 68 * 2 - (16 * 2 - (4 * 2 - 2))
f(2,2,8) = 110 * 2 - (26 * 2 - (6 * 2 - 2))
f(2,2,9) = 168 * 2 - (42 * 2 - (10 * 2 - 4))
f(2,2,10) = 278 * 2 - (68 * 2 - (16 * 2 - (4 * 2 - 2)))
f(2,2,11) = 446 * 2 - (110 * 2 - (26 * 2 - (6 * 2 - 2)))

[weary tiger]

i suggest you learn what a function is, LiTHiuM

[surreal surge]

((6+10) / 2) / (10 / 2) / 10 = 6+10+16

[civic horizon]

please just give some context or stop spamming

[stray reef]

no no you don't get it, math is all about writing out long complicated equations full of numbers

(/s)

[uncut matrix]

Thanks, I realized the problem.

But then, I'm curious ... would the answer to this problem not be summing up P7, P8, and P9 for:

P7 = 36^6 - 10^6, P8 = 36^7 - 10^7, P8 = 36^8 - 10^8?

36^6 would represent a 6 character long password represented by alphanumeric digits, while 10^6 would be a 6 character long password represented by strictly digits
by subtracting the two, I would get a 6 character long password that has at least 1 alphabetic character, correct?

36^6 - 26^6 would give me a 6 character long password that has at least one digit on the other hand

[stray reef]

But then, I'm curious ... would the answer to this problem not be summing up P7, P8, and P9 for:

P7 = 36^6 - 10^6, P8 = 36^7 - 10^7, P8 = 36^8 - 10^8?

it would

i think the question author miswrote either the question or their intended answer

[uncut matrix]

thank you!

yeah I guess he mixed it up or something

[paper coyote]

can anyone help me with first order logic?

[languid cradle]

@paper coyote maybe

hey guys I just finished an exam but I kinda wanna know how i did beforehand cus im really anxious lol

Find the number of ways to arrange the six numbers 1, 2, 3, 4, 5, 6 such
that either in the arrangement, 1 is immediately followed by 2 or 3 is immediately
followed by 4 or 5 is immediately followed by 6.

so for this

I did inclusion exclusion

$3 \choose 1$ $* 5! -$ $3 \choose 2$ $4! +$ $3 \choose 3$ $ 3!$

[vital dew]

therealjoshua

[languid cradle]

does this look right?

[weary tiger]

Can you explain what your sets are?

[languid cradle]

so Ai is for 12 together, 34 together, or 56 together

Ai intersect AJ for two of those

AI intersect AJ intersect AK for all 3

there are 3 choose 1 ways to choose Ai

etc

and then since 12 is 1 letter, we have 5 letters

12 and 34 for example, we have 4 letters (12, 34, 5, 6)

so 4!

etc

[weary tiger]

Looks fine tbh

I would've certainly used inclusion-exclusion

[stray reef]

bad latex

[languid cradle]

sorry lol

for some reason when I use choose it takes like everything

I guess maybe brackets would work?

[stray reef]

you can use \binom{}{}

$\binom{3}{1}$

[vital dew]

Ann

[languid cradle]

oh ok, thank u I appreciate it

[stray reef]

if you insist on \choose you can wrap it in braces

[languid cradle]

and I have one more question if anyone's up to it

[stray reef]

${n \choose k} + m$

[vital dew]

Ann

[languid cradle]

yeah no binom seems much more straight forward

I was told to find $x^7$ in $(1+x^4)^{2000} * (1+x)^{2021}$

[vital dew]

therealjoshua

[languid cradle]

so I was thinking

you could either take x exclusively from the latter

and get $\binom{2021}{7}$

[vital dew]

therealjoshua

[languid cradle]

or take $x^4$ from $(1+x^4)^{2000}$ and $x^3$ from $(1+x)^{2021}$ to get $\binom{2000}{1} * \binom{2021}{3}$

[vital dew]

therealjoshua

[languid cradle]

so the coefficient would be the summation of these two results

I could go into more detail if needed

[weary tiger]

did you use the binomial theorem?

[languid cradle]

Yep.

since $(1+x^4)^{2000}$ has the $x^4$ it produces only multiples of 4 hence a $\binom{2000}{1}$ coefficient for $x^4$

[vital dew]

therealjoshua

[languid cradle]

banking on an A from this exam cause I got B in topology

[stray reef]

hm?

can you show the exact problem youre doing

[stray reef]

okay

use the defn, show that for every number between 0 and 3 inclusive there exists a subset of S with that many elements

[viscid nacelle]

hey, first time asking q here! how do you show this graph doesn't have a Hamiltonian cycle?

[cinder mantle]

I think i should just ask here, is this true? : ∅ ≠{1,2}*∅?

[weary tiger]

is * cartesian product?

[cinder mantle]

im sorry what

[weary tiger]

What is *?

[cinder mantle]

oh multiply sorry

[weary tiger]

what multiply?

[cinder mantle]

{1,2} x ∅

[weary tiger]

notation looks like a cartesian product but you "are sorry what"

[cinder mantle]

okay here is the question basically

is ∅ not equal to, {1,2} x ∅

[weary tiger]

Can you tell me what x means?

[cinder mantle]

multiply

[weary tiger]

i asked you what it means, not its name

[cinder mantle]

isnt it asking if ∅ basically the same as that set times ∅?

[weary tiger]

Does it matter what it is asking if you don't know what set multiplication means?

[cinder mantle]

you are right, sorry i do not

we just started this topic in class i am really confused on it

[weary tiger]

if you have two sets A and B

then their cartesian product AxB is the set of all ordered pairs (a,b) where a is in A and b is in B

[cinder mantle]

oh ok

[weary tiger]

for example {0,1}x{a,b} = {(0,a), (0,b), (1,a), (1,b)}

[cinder mantle]

oh yeah

i remember reading that

okay gotcha

so in this case, {1,2} x∅ means: {(1,∅),(2,∅)}?

[weary tiger]

no

if you said {1,2}x{∅} then what you said would be true

but {1,2}x∅ does not mean that

[cinder mantle]

hmm

[weary tiger]

Remember what i said

if you have two sets A and B
then their cartesian product AxB is the set of all ordered pairs (a,b) where a is in A and b is in B

so let's see for this case

you have {1,2} x∅

[cinder mantle]

yeah

[weary tiger]

it's elements will be ordered pairs (x,y) where x in {1,2} and y in ∅

[cinder mantle]

yeah

[cinder mantle]

okay but going back here, u knew ur a and b

actually wait

[weary tiger]

does using different variable names clear the confusion?

[cinder mantle]

i see where {1,2} would go in that but I dont see what would a and b mean in sense of my question

[cinder mantle]

I just dont understand how my question applies to this

[weary tiger]

that's just an example

you want to do a similar thing but for

{1,2}x∅

[cinder mantle]

{1,2} x {?,?}

[weary tiger]

do you know what ∅ means?

[cinder mantle]

{1,2} x {∅,∅}?

no not really

empty set?

[weary tiger]

well, next time, before trying to answer a question you should at least find out what the things in it mean

yes it's the empty set

it's the set that has no elements

[cinder mantle]

ohhh okay i actually got it now

{1,2} x { , } since its an empty set

[weary tiger]

uh

[cinder mantle]

no?

[weary tiger]

idk what you mean by { , }

[cinder mantle]

{∅,∅}

[weary tiger]

that is not the empty set

that is a set with 1 element which is the empty set

you should definitively read some book about basic set theory

[cinder mantle]

today was my first time ever even seeing this at all

and now I dont know what to do cuz our stupid prof assigned hw on it due tonight

I came here to get help but ig I got nothing

[weary tiger]

does your course have notes, or a book to follow?

[cinder mantle]

we have a book, his notes are extremely useless

[weary tiger]

maybe the book has these stuff? or you could always try to find some other book online

[cinder mantle]

Its not that I dont want to learn in this class, I am trying my hardest too its just that I dont think I would have time before tonight to do all of that and figure out what these mean

[weary tiger]

i don't have time to tell you everything from ground up either, maybe you could ask in #book-recommendations someone could recomend something for your level

how much time do you have?

[cinder mantle]

6 hours approx

im reading the book as we speak rn

[keen girder]

I am not sure but couldn't you use Dirac's theorem here?

Someone else should probably confirm this however.

[weary tiger]

you should be able to learn the basics in that time

[weary tiger]

idk what dirac theorem is, but i think it follows since there is more than one vertice with odd edges?

[viscid nacelle]

didn't learn that yet 😅

[cinder mantle]

i know, im trying, can u just tell me if its true or false for just that question so I can get it over with, thats all I really need

[keen girder]

hmmm

So what dirac's theorem states is that for a graph with n vertices, for it to have hamilton circuit, every vertex must have degree greater-equal to n/2.

But I wasn't sure if we can apply this here.

[errant bear]

are u rly trying ur hardest if ur just now reading the book

[keen girder]

Hmm @viscid nacelle how did your prof or textbook describe on the process of finding hamilton cycle?

[viscid nacelle]

forget my prof, textbook does most of the teaching lol. we learned two methods: Suppose that we could eliminate edges from the graph, leaving just a Hamiltonian cycle (be careful not to eliminate the same edge more than once). If the remaining number of edges are less than the number of vertices, then there is no Ham cycle

2nd method kinda hard to explain but is shown pretty well in this example

[keen girder]

I think you can just use the first method here?

For your question that is.

[viscid nacelle]

sure I'll give it another go, though the first method doesn't work if you eliminate the same edge twice by accident

[keen girder]

yeah

let me know what you get, I am curious as well.

[viscid nacelle]

my handwriting is messy so i'll just briefly type out my answer here: total 16 vertices & 27 edges so to get Ham cycle we can only remove 11 edges. c,j,m all non adjacent and have degree 5, so we can safely remove 3 edges from each one (3x3). Now look for vertices not adjacent to c,j,m. 4 such vertices b,f,p,i each degree 3 and not adjacent to each other, so we can safely remove 1 edge from each one (4x1). That means we're removing 3x3 + 4x1= 13 edges. Contradiction -> no Ham cycle

[surreal surge]

can anyone derive function f?

[obtuse lance]

there are infinitely many possibilities

if you know it's some kind of polynomial or has certain properties that might allow you to uniquely determine it

like if I say f(0)=0 and f(1)=1 my functon could be tons of things, x, x^2, x^3, sin(pi*x/2), etc...

[unreal stump]

By Ann's Theorem,The answer is f(x,y,z)=19 for x,y,z not in that list

[stray reef]

[keen ingot]

Hi guys, if an identity exists for a set, then ae =ea= a right?

It has to work both ways which makes sense

I just wanna check

Sorry I should say e*a

Where * is a binary operation

[grim charm]

there must be some condition about e i guess

[keen ingot]

But just for any generic set with rational numbers

For e to be the identity element a* e= e* a=a

[carmine ivy]

Yes , if we are saying that e is an identity of any set then it has to be both left and right identity...

[viscid nacelle]

f(2,2,n) = f(2,2,n-1) * 2 - f(2,2,n-3) where f(2,2,1) = 6, f(2,2,2) = 10, f(2,2,3) = 16

[surreal surge]

f(10,8,0) = 10, f(10,8,1) = 10+8, f(10,8,2) = 10+8+10, f(10,8,3) = 10+8+10+8

[weary tiger]

Am trying to do the part that says write down Var(X)

so I split it up into events A,B where A and B are the event where a specific K2,2 subgraph is there

and split this up into cases of when they share and edge,3 edges or all the edges but I'm not sure if my solution is correct

[mint bane]

this should be 1/i^2 right

[gritty crescent]

Induction?

[weary tiger]

ye it should be i^2

[mint bane]

yeah

[weary tiger]

but its true anyway ofc

<@&286206848099549185> any1 know for my Q?

[mint bane]

i mean yeah but doin induction on it with 1/n^2 seems wack

even though it's clearly induction

[civic horizon]

you dont need to induct

also the original version with 1/n is easier to show

[weary tiger]

ye ofc but its meant to be i

[civic horizon]

?

oh yeah the index

mb

[mint bane]

what would u do to avoid inductioon

[civic horizon]

try to directly bound the LHS

[weary tiger]

hey

Suppose that n is an even integer such that n>8 and that n is not divisible by 4. 
Use the Euclidean Algorithm to find gcd(n,5n2+8)

how exactly would you use the euc. algorithm to find this?

[late topaz]

could anyone show the thought process behind this ? Spent some time on it and gave up

[civic horizon]

what is H_k

the k:th harmonic number?

and what is to be done

[late topaz]

yes harmonic number. Simplify in terms of H_n

[forest lodge]

can someone explain how it went from the summation to that fraction after the second equal sign?

[blissful wadi]

looks like that -5-1=-6 was just scooched over below the 7 and the (-) was consumed by the (-5)^3. Algebra!

[forest lodge]

I meant how left turned to the right

[blissful wadi]

sorry, miss read your question. Hopefully this is what you meant 🙂

[uncut matrix]

I have a question regarding a certain proof

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

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

For the step where it goes from "by the inductive hypothesis" to "because there are 2^k terms each greater or equal to 1/2^(k+1)"

I don't understand how you can sub
1/(2^k + 1) + ... + 1/(2^k+1) to (2^k)(1/2^k+1)

I understand that 1/(2^k + 1) + ... + 1/(2^k+1) is comprised of 2^k terms in total

[last timber]

(1/(1/2^k+1)) he does not have this term

anyway

if a+b is such that a>=c and b>=c then a+b >= c+c >= 2c

and you can extend this

[uncut matrix]

what I'm wondering here is how he proved 1/(2^k + 1) + ... + 1/(2^k+1) >= 1/2

I mean, it's pretty obvious it is the case when you look at it intuitively

but the way the textbook tries to prove it by using its strange substitution of values is not very comprehensible for me

[uncut matrix]

yeah, that part

[vital dew]

Commander Vimes

[uncut matrix]

yes

[vital dew]

Commander Vimes

Commander Vimes

[last timber]

is it clear?

[uncut matrix]

one sec, still thinking about that last one

2^k terms in the sum I get

[vital dew]

Commander Vimes

[last timber]

and what is used here is generalization of this to an arbitrary finite number of terms in sum

[vital dew]

Commander Vimes

[uncut matrix]

so if I let a = H2^k, b = 1/(2^k + 1) + ... + 1/(2^k+1), c = (1 + k/2), and d = 1/2

a + b >= c + d
so then, a + b >= c + b
and then, c + b >= c + d?

[last timber]

sorry what

this is not how it is done man

[last timber]

you have 2^k terms satisfying this

[last timber]

you have this

[last timber]

as generalization of this

connecting these all together should give result

[uncut matrix]

thanks for trying to help me, but it really isn't clicking
I'll just sleep on this and give it another tomorrow I guess

oh

god im so stupid

I think I sorta get it

https://i.imgur.com/7RY7xHc.png

like you said, each term here is >= 1/(2^(k+1))

so this sequence of terms is simply larger than if you were to multiply 1/(2^(k+1)) by the number of terms in the sequence, 2^k

then you just simplify to 1/2 which completes the proof

[last timber]

yes

[uncut matrix]

thank you so much

im just dumb and it didn't felt intuitive to me at all

thanks for being so patient when trying to explain it

[last timber]

yw

[civic horizon]

i think summation by parts will work

my calculations give me something pretty ugly but still in terms of H_n

[hybrid tendon]

is there any sequence that looks something like this?

$(n + 1^{2}) + (n + 2^{2}) + (n + 2^{3}) \dots$ n is a natural number

[vital dew]

Radical Ninja

[civic horizon]

what is the next term of the sum

is it n+2^4 or

[hybrid tendon]

ohh shit wait I made a dumb mistake, its a series not sequence

let me correct it

$(n + 1^{2}), (n + 2^{2}), (n + 3^{2}) \dots$
$\ A_i = n + i^{2}$

[vital dew]

Radical Ninja

[civic horizon]

and what do you want to do with these A_i

[hybrid tendon]

$\sum_{i=0}^{2n} gcd(A_i, A_{i + 1})$

[vital dew]

Radical Ninja

[hybrid tendon]

this is what I wanna do

Just give me some leads, that would be enough

[civic horizon]

are you sure this will have a nice closed form

because $\mathrm{gcd}(A_i, A_{i+1}) = \mathrm{gcd}(n+i^2, 2i+1)$, which doesnt look too nice

[vital dew]

Pappa

[hybrid tendon]

how did you arrive to this?

[civic horizon]

just use the fact that $\mathrm{gcd}(a, b) = \mathrm{gcd}(a-b, b)$

[vital dew]

Pappa

[hybrid tendon]

I don't know what you mean be nice closed form, but yes this is exactly what I wanna do

[civic horizon]

i mean why do you expect this some to result to something nice or easy to compute

[hybrid tendon]

There should be an easier way to solve this because I can't solve this in O(N) complexity, should be better than that

[obtuse minnow]

I'm confused. Do you want a function of n as the answer?

[hybrid tendon]

Yes, a function of n, is the only input

[obtuse minnow]

It would be so much easier if it was (n+1)^2, (n+2)^2 hehe.

[hybrid tendon]

sorry this is how the GCD's look

I can't find any closed form like pappa said to compute

[obtuse minnow]

I see you like computation, but I'd suggest starting with n = prime first. It actually pans out nicely for primes. The difference in (i+1)^2 and (i)^2 is 2i + 1. Pappa's suggestion is also seemingly helpful. He said gcd(a, b) = gcd(b - a, a). 🙂

I'm not saying I have the answer. I'm suggesting things to try that may or may not get you there. Even if it doesn't get you to where you're needing/wanting to go, you'll learn and discover things along the way.

[hybrid tendon]

yea, Thanks

[obtuse minnow]

Is this homework for your Discrete Math class?

[hybrid tendon]

Nah

I'm in uni and not a math major, and I don't ask for complete answers usually

[obtuse minnow]

I was wondering. It doesn't seem particularly easy. What brings you to the math temple 😛 :)?

I suggest looking at odd primes other than 5?

[hybrid tendon]

7?

[obtuse minnow]

Yeah, primes (in general not always) have simpler patterns but more exceptions happen with 2 (the only even prime).

okay give me 15 minutes to jot some things down. What is this for anyway?

[hybrid tendon]

Well you can't give me the answer, I only want some leads, this is question is part of competition

[obtuse minnow]

Er, can I ask which competition?

[hybrid tendon]

yea, its not a math competition btw,
https://www.codechef.com/MAY21B/problems/ISS

[obtuse minnow]

Ah, well there's a lot to say here. There's a super cool pattern for some of those numbers, but I don't think I should tell you much. When math people look at data, we're usually more impressed with things that are all the same or only have one exception.

I wish you good luck. Come back or DM me AFTER the competition if you want to see something I saw.

[hybrid tendon]

So there's a way to solve this in better way than O(N)?

[obtuse minnow]

I'm sorry but I'm no CS major.

[keen girder]

Whats the question?

[hybrid tendon]

Can I compute this in one step? like one formula?

[obtuse minnow]

I once took the O class but I have forgotten about many things there. But to answer your question, there are definnitely n such that the calculation is immediate 🙂

[hybrid tendon]

see the link just above

[obtuse minnow]

I dunno for all the numbers but for some yes 🙂

[keen girder]

Whats the time constraints?

[obtuse minnow]

I really shouldn't post more. It's a public forum.

And other competitors might see this.

[hybrid tendon]

1.5 seconds

[keen girder]

You can generally guess the intended time complexity by just looking at time constraints

input size?

[hybrid tendon]

wait everything is there in the link

[obtuse minnow]

Radical. You're messing up the competition for you and others. I'd ask you to stop asking 🙂

[hybrid tendon]

Yea, I know. That's why I clearly said I don't want the answer

I came to ask is there a name for this sequence or something like that remember?

[obtuse minnow]

Perhaps. I must hush now. 🙂

[hybrid tendon]

anyways, I should also stop btw. Thanks for the help till now

[obtuse minnow]

again, good luck! 🙂

[lilac breach]

I need some feedback on whether I'm on the right track or not:

Here's what I got so far

But I don't seem to account for the case when the degree of a vertex > 2. As in: we discard all edges for vertices with degree > 2

[weary tiger]

@lilac breach you here?

[lilac breach]

Yeah

[weary tiger]

so if we look at a vertex

we want to maximise the expected number of edges adjacent to it

by linearity of expectation we know maximising it for one vertex will maximise it for the sum

Let X be the number of edges adjacent to a random vertex

E(X) = 3*p*(1-p)^2 + 2*3*p^2 *(1-p)

so you are just trying to find the p that maximises that

[lilac breach]

I haven't thought about looking at the individual vertices

[weary tiger]

it makes sense to look at individual vertices because that is what the algorithm is acting on

like its just deleting vertices when there are 3 adjacents

i realise that might be slightly wrong actually 🤔 but can use the same idea

[lilac breach]

I have also tried to look at it in another way. Since we are going from a 3-regular graph to a subgraph of max degree 2, then the optimal solution is a 2-regular graph. Number of edges for regular graphs can be expressed as |E|=nr/2. Our original graph has n*3/2 edges and the optimal subgraph has n*2/2=n edges. Then to generate that graph it's simply p^n*(1-p)^(n*3/2-n) = p^n*(1-p)^(n/2)

Got that definition from the Erdős–Rényi model but I don't think I'm "allowed" to use that

$p^n (1 - p)^{n/2}$

[vital dew]

Steverman

[lilac breach]

And the general formula: $P(G)=p^m(1-p)^{M-m}$, where m are all the edges we want and M are all possible edges

[vital dew]

Steverman

[lilac breach]

Huh, that's almost the binomial distribution

[forest lodge]

Thank you! Just saw the message ✨

[civic horizon]

Damn

Thats schurs theorem

Im pretty sure it relates to ramsey theory but im not quite sure how

[weary tiger]

yeh i probs shoulda said its in a graph theory Q

[civic horizon]

Thonk

[weary tiger]

I think I can see why roughly

[civic horizon]

hint: ||rephrase in terms of colorings, and then draw a graph with a lot of vertices and label the vertices from 1 to VERY LARGE NUMBER. Now for two vertices a, b, the edge ab is colored according to the colour of |a-b|. ||

[weary tiger]

I have no idea how to approach exercise 2.8 & 2.9. I know the definition of a discrete random variable, but it can't seem to get the answer.

[lilac breach]

Alright, I asked my professor and he said in order to compute P[X_e]: p times the probability that at most one more edge adjacent to each endpoint of e is accepted.

What's that? p*(1-p)^{2*(|V|-2)}?

[weary tiger]

@civic horizon ok yeh got it thanks

[civic horizon]

cool

[weary tiger]

I think the very large number needs to be R(3,3,....,3) where there is k 3s right

[civic horizon]

yeah

[weary tiger]

where we take a k-colouring

nice

[civic horizon]

cool theorem

[weary tiger]

ok that was kinda hard to wrap my head around

[civic horizon]

another cool theorem in ramsey theory is van der waerden

[valid wave]

is there a way to determine the amount of faces in a planar graph?

[obtuse lance]

there's a well known formula due to Euler

F-E+V=2

number of faces, edges, and vertices respectively

so if you know the edges and vertices you know the faces

keep in mind this counts "outside" as a face too

if you don't want to count that for whatever reason, just subtract 1

[valid wave]

I tried that but im so lost

I had

|10 + k| - |30 + (5k/2)| + |F| = 2

ohh got it

induction

😄

[quick folio]

uhh

no

[vital dew]

Meliodas

[quick folio]

@valid wave

[valid wave]

Wait huh

I’m kinda lost

Isn’t this the same as plugging in 22 as a base case for Euler’s formula

Then k + 1

I did that

Plugged in 5k/ 2 + 35 and 10 + k

To find F

Then plugged in F back into it

Then used induction for base case of 22

[quick folio]

i mean it kinda is but ur taking more steps for a simple problem

?

[weary tiger]

how would you find all equivalence classes?

I already proved equivalence relation

[unreal stump]

That's same as saying a~b iff 3a-3b is divisible by 7

Which is same as saying a~b iff a-b is divisible by 7

Which is just your usual Z_7

[weary tiger]

where did you get 3a-3b?

[unreal stump]

If 7|3a+4b then 7|(3a+4b-7b)

[weary tiger]

ohhh

thank you

[hybrid tendon]

The congruence notation confuses me $a \cong b (mod n)$ \ means $(a-b)$ divisible by $n$?

[stray reef]

\means

[hybrid tendon]

how to break line?

[stray reef]

\\

[vital dew]

Radical Ninja

[stray reef]

yes, though usually you see $\equiv$ instead of $\cong$ at least in my experience

[vital dew]

Ann

[hybrid tendon]

ohh okay but how do I write $a \mod b = c$ in terms of mathematical notation?

[vital dew]

Radical Ninja

[hybrid tendon]

like $a \equiv c (\mod b)$ this?

[vital dew]

Radical Ninja

[stray reef]

$a \equiv c \pmod{b}$

[vital dew]

Ann

[stray reef]

also notice that mod as an operation and mod as a relation are somewhat different

[hybrid tendon]

yea, that's why I'm confused is correct if I right? \
$A \equiv (A % b) (\pmod c)$

[stray reef]

uh

[hybrid tendon]

how do I put %?

[stray reef]

okay so if you want a percentage symbol you need \%

[hybrid tendon]

thanks

[weary tiger]

How would you establish a 1-1 correspondence for f: Q -> Q defined by f(n) = n - 1

[stray reef]

wym

[hybrid tendon]

yea, that's why I'm confused is correct if I right? \
$A \equiv (A % b) \pmod{c}$

[weary tiger]

so i'm trying to prove that this set is countably infinite

[stray reef]

@hybrid tendon no need for the extra parentheses but yes you are right

[hybrid tendon]

sorry for editing it several times, I forgot tex

[stray reef]

@weary tiger yeah you can just send each point in S to its x coordinate lol

that's a bijection between S and Q

and presumably, Q is already known countable

[hybrid tendon]

so I can say that\
$ A - (A% b)$ is divisible by $c$?

[vital dew]

Radical Ninja

[stray reef]

by b, you mean?

wait

god ok

you had mod c all this time

the bad tex kept getting in the way

[hybrid tendon]

yea, sorry for that

[vital dew]

Radical Ninja

[stray reef]

mod b.

[hybrid tendon]

[weary tiger]

Ryt

[hybrid tendon]

$A$ divided by $c$ will give the same remainder as $A % b$ divided by $c$ \
if $A \equiv (A% B) \pmod{c}$ \
is it correct now?

[vital dew]

Radical Ninja

[stray reef]

unless you tell me what the relationship between b and c is, this is not necessarily true.

[hybrid tendon]

b > c

[stray reef]

b=11, c=10, A = 300

300%11 = 3, but 300 and 3 are not congruent mod 10

[hybrid tendon]

yes, I'm not stating a theorem. I want to solve this problem/equation

to find all permissible values

I want to find (c, b)

[stray reef]

so you want to find all triples (a,b,c) such that a is equivalent to (a%b) mod c...?

oh.

[hybrid tendon]

No, I already have A should only find c, b

[stray reef]

sounds like this will happen iff b is a multiple of c

[hybrid tendon]

that's not the case, that's what I'm trying to figure it out

[stray reef]

?? can you give a counterexample

[hybrid tendon]

yes pls. wait give me some time to tex

[stray reef]

give me a pair of positive integers (b,c) such that exactly one of the following is true:
(1) for all a in Z, a == (a%b) mod c
(2) b is a multiple of c

just a pair of positive integers nothing else

[hybrid tendon]

$M % a = (M % b) %a$, where $a<b$\
So I'm rewriting this as $M \equiv (M % b) \pmod{a}$\
if the above statement is correct then I can say $M - (M % b)$ is divisible by $a$

[vital dew]

Radical Ninja

[stray reef]

give me a pair of positive integers (b,c) such that exactly one of the following is true:
(1) for all a in Z, a == (a%b) mod c
(2) b is a multiple of c

[hybrid tendon]

yes, take a look at this

[stray reef]

do you not understand what i am asking you

give me a single pair of b and c

just one

[hybrid tendon]

(3, 8) where both in the pair should not be greater than 15 and M=29

[stray reef]

b=3, c=8?

or is it the other way around?

[hybrid tendon]

other way around

[stray reef]

so b=8, c=3

[hybrid tendon]

I got confused because I use a, b

[stray reef]

so you claim that for all integers a, you have a == (a%8) mod 3?

yes or no

[hybrid tendon]

not for all integers? just for a given integer a

[stray reef]

.......

god

[hybrid tendon]

I'm very slow at texing.... that's why I asked to give me some time

[quaint star]

What you are trying to do is very unclear. Do you have a specific a for which you need to find b and c? Or what is the exact problem statement.

[hybrid tendon]

I just need to know whether what I have did in this picture is right?

If so is there any way to simplify
$M - (M% b)$ which is divisible by $a$ and provided that $a<b$

[vital dew]

Radical Ninja

[hybrid tendon]

I apologize for making it confusing because of my bad texing

[hybrid tendon]

This is the case where I already have A with me

[stray reef]

... hrrgh

you can write M - (M%b) as b * floor(M/b) i guess...

[hybrid tendon]

Ohh okay thanks, I think this is the way to calculate mod in general

[unreal stump]

did I skip any steps here?

[weary tiger]

Notation is a bit sloppy no?

so if i make a graph with degree sequence 2,2,2,2,2 how do i show it can't be bipartite

In the first case you show (a,a) is in S but were you meaning to write aSa? (ie a related to itself by S)

[unreal stump]

yea,was kinda tired that day

shouldn't change anything tho

[weary tiger]

Ok cool

No that's all good

[weary tiger]

Does it contain an odd cycle?

Or show that you can't get a proper 2-colouring

[weary tiger]

yeah i think i'll take this approach

[stray reef]

a graph with this degree seq is either a 5-cycle or a triangle + lone edge, is it not?

[weary tiger]

not sure about triangle and lone edge

[stray reef]

er wait no

double edge

that'd be a multigraph

so just a 5-cycle then

[weary tiger]

yeah

That's even easier to prove!

5-cycle is an odd cycle so can't be bipartite

gotcha thanks!

so the only time you can't make a graph from a degree sequence is if the sum is odd?

wait no

Ah you're referring to the handshaking lemma

Sum of the degrees must be even

As it's twice the number of edges 🙂

and if there is a triangle in the graph it can't be bipartite right?

Uh yes it's a 3-cycle which is odd

It sorta forces you to use 3 colours right

gotcha

[weary tiger]

so if found all 6 hamiltonian cycles

but how do i prove that the list is complete?

oh maybe i have to prove this graph has exactly 6 hamiltonian cycles

wait apparently the formula is (n-1)!/2

where n is number of vertices

but that's obviously not 6

[sweet bough]

can someone help me with Recusive data types and structural induction? (Sorry, I am new here, thought this will be the channel)

[weary tiger]

so i know this is eulerian since each vertex has even degree

but i'm having a hard time visualizing the circuit path

nvm

It's ABCDHGFEHAED right?

or ABCDHEADEFGHA

it can't be the first one since it doesn't start and end at the same vertex

[stray reef]

do you want just one eulerian path or to enumerate them all

[weary tiger]

the question is obscurely phrased

it just asks for "the" Eulerian circuit

whatever that means

But i'm pretty sure it's ABCDHEADEFGHA

[stray reef]

well that's an eulerian circuit but not the only one

[weary tiger]

Hm. Do you know Euler's theorem?

If a graph is connected and all of its vertices have even degree, then it has an Euler circuit

(Actually it's an iff statement but yeah)

[weary tiger]

yeah that makes sense

thanks!

[ashen dock]

any help would be appreciated

[weary tiger]

why are you stuck?

[ashen dock]

im just confused on wher eto start

😦

[gritty crescent]

What can you say about the number of words in L?

[ashen dock]

infinitely countable

but basically sigma* - L is just 2 countably infinite sets subtracting each other

so im not sure if the compliment would be uncountable or countable

[stray reef]

actually no L is not infinite at all

it only contains (C+1)^2 words

[ashen dock]

oh

wait so L is finite?!

[stray reef]

yes

it's large but it's finite

[ashen dock]

oh ok

TRUE

so that makes the compliment of L countably infinite correct?

[hearty perch]

could anyone explain why this is countably infinite and also how it is one-to-one

[stray reef]

how it is one-to-one
how what is one-to-one?

[stray reef]

late response but yes

[viscid meteor]

anyone know where i can learn discrete math over the summer. looking at this math.. I am going to need time to figure it out.

[weary tiger]

in a book maybe?

[errant bear]

i learned from browsing #discrete-math 🙂

[gritty crescent]

MIT OCW's Mathematics for Computer Science might be worth looking into. They have recorded lectures, complete set of notes and problem sets.

[distant bobcat]

Is reducibilities in relation to showing NP-completeness involve graph isomorphism? Like when proving a Hamiltonian path is NP complete using a known NP problem (i. e Hamiltonian cycle) in which we for a positive instance of X as input, it produces a positive instance of Y as output.
and for a positive instance of Y as output, it must have been given a positive instance of X as input. This sounds a lot like an equivalence relation on graphs to me.

[delicate ridge]

one-to-one just means injective

a set is countable if there exists an injection from it to the natural numbers

(and countably infinite if there are infinitely many elements in the set, and the set is countable)

clearly the set is infinite, since it contains the subset (2, 1), (3, 2), (4, 3), ...

you now need to come up with a mapping from S to N

[weary tiger]

im tryna do the last part

[weary tiger]

<@&286206848099549185> any ideas

[wooden acorn]

I asked a graph theory/combinatorics problem in help 7

Trying to figure it out for my grandma’s favorite puzzle

Questions 7***

Also don’t forget about the dudes problem above me

[opal cedar]

Is there a simple way of discerning decidability from a language description? Like some simpler rules of thumb than just reduction.

[woeful crag]

could someone help me with this?

do i first try and prove g is a tree?

[stray reef]

what's lowercase g?

you could induct on the number of connected components, and perhaps first show that a tree has exactly one less edge than the number of vertices

@woeful crag

[woeful crag]

if you're implying i should use induction, we haven't done that yet:/

[woeful crag]

G*

[stray reef]

okay, this is possible to do without induction

but you will first need to show that a tree has |E|-1 vertices, which i'm not sure is possible at all if you do not have access to induction

[woeful crag]

i think we can use that, they've just told us we done need to prove it

[stray reef]

unless you're just given that fact for free

okay so you are given that fact for free, great

[woeful crag]

also what does it mean when we have multiple connected graphs?

does it imply their all detached from one another?

[stray reef]

here is a graph on 11 vertices with 3 connected components

i hope this illustrates the meaning of the word 'connected component'

[woeful crag]

i see.. since we have no cycles

does that mean we have k trees?

[stray reef]

well this one does have a cycle so its not an example of a graph from your problem

but yes, your G is a disjoint union of k trees

maybe disjoint union is a bit too fancy as a term

[woeful crag]

i think i get it

[stray reef]

but yes your G consists of k trees

[woeful crag]

alright i'll see what i can do with that information

would i be using that |E|-1 rule?

[stray reef]

you could do that if you wanted

it may take a little bit of notational song and dance to get the proof right

and there is a clever way to avoid that, which i can share if you want

[woeful crag]

i mean that would be nice

[stray reef]

so your graph consists of k trees

pick 1 vertex on each one of those trees and mark it, so that you have k marked vertices

then weave a path through these k marked vertices - this will mean adding k-1 edges to your graph. maybe color them so that they're distinct from what was there before

say the original graph could be drawn in black and these extra edges in red

does this make sense to you

[woeful crag]

im following so far

[stray reef]

yeah so this path stitches together all the connected components of G into one

and the resulting graph is a tree

do you see why?

[woeful crag]

cuz theres no cycles?

[stray reef]

well yeah, but if i asked you to prove rigorously why there's no cycles, would you be able to do it?

[woeful crag]

since you have added k-1 edges probably not

or do u riggorously prove there is exactly one path between 2 vertices?

[stray reef]

i feel as if my yes/no question is not getting properly answered by you here

[woeful crag]

wouldn't i need to proove that my resulting graph is a tree?

[stray reef]

that's part of the proof

you want to show it's acyclic

[woeful crag]

ah alright

so we add k-1 edges and connect all the k trees together to get a larger tree graph

now what?

[stray reef]

now we have one big tree on n vertices

how many edges does it have

[woeful crag]

so u added k-1 edges, soz

[stray reef]

no i added k-1 edges

[woeful crag]

did u have n-1 edges before/

[stray reef]

no

you are not answering my question

now we have one big tree on n vertices
how many edges does it have

how many edges are there in a tree on n vertices?

[woeful crag]

so would u do (k-1)+(n-1)

[stray reef]

AAAAA

answer

my

question

please

[woeful crag]

n-1?

[stray reef]

after adding these red edges, our graph became connected, and thus a tree on n vertices.

yes

there are n-1 vertices in this new graph

there are n-1 vertices in this new graph and this count of n-1 includes the red edges we added

of which there are k-1

but we need to find the number of edges before we did any tampering with the graph

[woeful crag]

ah so n-1-(k-1)

=n-k

[stray reef]

finally

[woeful crag]

thank you so much sorry for my incompetence lol

[vague veldt]

what is 6+7·9-56=?

[stray reef]

if your question can be answered by literally plugging it into a calculator or even typing it into google then it doesn't belong here.

[woeful crag]

ik that g1 is 3 and g2 is 5

but how do i justify my answers

[stray reef]

show that you can't 2-color G1

also G2 can be colored with less than five colors

here's a 3-coloring of G2

[weary tiger]

In a binary code of length 5, there are 5C1=5 words with 4 1's and a 0. Is this correct?

[stray reef]

yes

11110, 11101, 11011, 10111, 01111

[weary tiger]

Thanks 💯

[stray reef]

oh wait

fuck im stupid lmao its edge coloring not vertex coloring

(in ref to zeldas problem)

yeah @woeful crag edge-coloring G2 still doesnt require 5 colors, you can do it in 4 like this

[woeful crag]

ahh thank you

is there really no way to justify my answers

[stray reef]

well your answer for G1 is correct

a justification consists of presenting a 3-edge-coloring and showing that a 2-edge-coloring is impossible

[woeful crag]

other than assume it can be done with less colours and contradicting myself

right i see

[stray reef]

im not entirely certain whether its possible to do G2 in 3 colors

wait no of course you can't do G2 in 3 colors you have 4 edges incident to the top vertex

that means at least 4 colors are needed

[vague veldt]

v

vhttps://cdn.discordapp.com/attachments/496785905474994186/841280539402960906/cj

https://cdn.discordapp.com/attachments/496785905474994186/841280539402960906/cj

https://cdn.discordapp.com/attachments/496785905474994186/841280539402960906/cj

https://cdn.discordapp.com/attachments/496785905474994186/841280539402960906/cjhttps://cdn.discordapp.com/attachments/496785905474994186/841280539402960906/cj

https://cdn.discordapp.com/attachments/496785905474994186/841280539402960906/cjhttps://cdn.discordapp.com/attachments/496785905474994186/841280539402960906/cjhttps://cdn.discordapp.com/attachments/496785905474994186/841280539402960906/cj

v

https://cdn.discordapp.com/attachments/496785905474994186/841280539402960906/cj

https://cdn.discordapp.com/attachments/496785905474994186/841280539402960906/cj

bro

bri

rbrob

r

rb

s

s

s

s

s

s

suck my dick @graceful condor

[civic horizon]

wat

[stray reef]

get banned speedrun any%

[proper mulch]

anyone's here

i want to learn discrete maths
is CS70 a beginner course or are there any other?

[pale epoch]

this?

[proper mulch]

yes

[pale epoch]

this looks like a beginner course

[proper mulch]

can i take it as a beginner in maths .

[pale epoch]

what does beginner in math mean

you have to be able to perform arithmetic

basic algebra

[proper mulch]

I mean like in highschool we do have math but that's like no interesting for me . So iam very much interested in CS . so want to learn maths for that

[pale epoch]

oh

highschool math should be sufficient

[proper mulch]

iam not very much perfect in that but i can manage

[pale epoch]

i mean, if you struggle with this

its not because you dont know enough math already probably

[proper mulch]

do you know any other courses on discrete math

[pale epoch]

no, sorry

just books

[proper mulch]

what are they :?

[pale epoch]

what grade are you in?

[proper mulch]

12th

[pale epoch]

i like this book: https://www.math.bgu.ac.il/~lipyansk/discrete/Invitationto discrete.pdf

but i don't know if it's good for a beginner

[proper mulch]

seems to be pretty advance

[pale epoch]

(studying from a book as opposed to a lecture series is also harder)

[proper mulch]

yeah

bye and can i add you for help if needed

[pale epoch]

why do so many people from this server dm me recently

context?

you mean $\bZ_6$?

[vital dew]

Lochverstärker

[pale epoch]

is it not explained elsewhere?

hm

do you know what an equivalence relation is?

there are multiple ways to explain this set

$(\bZ_6, +)$ is the set of integers but with addition modulo 6

[vital dew]

Lochverstärker

[pale epoch]

so you define an equivalence relation on Z but consider two integers a and b equal if their difference is divisible by 6

you can also kinda do this

think of it as the set of integers {0, 1, ..., 5}

since 6 = 0 mod 6

[proper mulch]

sorry . i didn't do that yet

[pale epoch]

oh, it wasn't meant negative

just an observation

you can dm me if you want

but don't be mad if i don't reply at all

yes, that is why the table is that way

there is a more technical way to think about that group but you probably do not need it

just the numbers 0 to n with addition modulo n

well, this group has a neutral element 0

since whatever you add 0 to, you get the same thing back

{2, 1} is not an element of that group

you can e.g. check that table and see that 3 + 3 = 0

this shows that 3 is the inverse of 3

the inverse of what

this is an equation, not an element of Z_6

the elements of Z_6 are (kind of) the numbers 0, 1, 2, ..., 5

equations dont have inverses

elements have

check the definition of inverse

you first have to find the neutral element of your group (which in this case is 0)

and then the inverse of a is an element b such that a+b=0

and since 3+3=0 the inverse of 3 is 3

the inverse of 1 is 5, etc...

yes

sometimes it be like that

[weary tiger]

Okay I'm missing something obvious - consider Bernoulli trial with probability of success $p$, $\Omega = {0,1}^n$, $A_k$ - event denoting exactly k successes. I need to show that for any $B \subset \Omega$, $P(B\mid A_k)$ doesn't depend on p.

[vital dew]

Ledog

[weary tiger]

I guess it would be true if B and Ak were independent, but that doesn't seem like that's the case for any B

[valid wave]

hi

does this represent the chromatic number?

[weary tiger]

Depends on context.

Usually it's denoted by $\chi (G)$ I guess

[vital dew]

Ledog

[valid wave]

oh

oops

so what symbol is the one i just pasted?

i read something about independent sets

oohh

independence number

sorry for noob question

thanks

[wanton seal]

Solve the following congruence equation
x11 congruent 7 (mod 61)

Anyone knows how to do this?

[pale epoch]

what have you tried

[rich siren]

How exactly do you solve this?

[lilac breach]

If an edge in a graph is added independently of other edges, does this imply that the endpoints of the edge are independent? For example I would like to know something like for an edge e: Pr(degree(e_u,e_v) <= 1)

[weary tiger]

no it doesn't

i.e imagine a complete graph minus an edge

im not sure if im interpreting your question correctly though

[lilac breach]

I see.. so in the problem I mentioned a few days ago. Creating a random graph from a 3-regular graph. The question was about probability of endpoint vertices having a maximum value. Say that you want to calculate the number of edges with at most degree 1 can I just write: Pr(edge e is in graph)\*Pr(degree(e_u,e_v) <= 1)

[lilac breach]

In the 3-regular case, it's at most 3, giving 2^3=8 possibilities

I'm asking since my TA thinks the previous solutions were overly complicated. Here's how the algorithm goes: First, e is included temporarily in the subgraph with probability p. Then, it stays in the subgraph if, in addition, at most one of the two edges e1 and e2 incident at one point of e and at most one of the two edges e3 and e4 incident at the other endpoint of e survives.

[vital dew]

Steverman

[lilac breach]

Oh, I only have to consider 2 incident edges e1, e2, so it's 4 rows

[lilac breach]

so for $Pr(deg(u,v)<=1)$ is it:

$\sum_{i=0}^1 Pr(deg(u)=i) + Pr(deg(v)=i) - (Pr(deg(u)=i) \cdot Pr(deg(v)=i)) $

[vital dew]

Steverman

[lilac breach]

Oh, it's slightly wrong. I need to sum them individually

[valid wave]

so i have to prove a graph is symmetric, reflexive and transitive?

i thought this only applied to functions

or sets rather

[deft current]

S is a set

[valid wave]

but what are my"values"

could you break it down more im lost

[deft current]

simple, undirected graphs

[valid wave]

I get that :/

but im asking

what exactly am i relating within these graphs

[deft current]

so R is a relation on the set of all simple, undirected graphs
G and H in S are related i.e. (G, H) in R, if G and H are isomorphic

[valid wave]

ok so im relating the vertexes of these grahps

gotcha

[deft current]

you're relating the graphs themselves

[valid wave]

but when im trying to set it up to prove reflexitivty

would I make it like

let v, u e V(G)

Then there is a path from u to v

but how would I show v, u e V(H)

sorry for noob question

[deft current]

I think you misunderstand the question

[valid wave]

how so

so would it just be like v e V

since the graphs are isomorphic?

so they are basically the same?

idk im kinda confused with setting it up

[pale epoch]

do you know what a graph isomorphism is?

[valid wave]

if thats the case would I have something like u, v e V and u~v so theres a path

and also a path the other way too

[pale epoch]

is that supposed to answer my question?

[coral citrus]

Reflexivity:
so a graph is isomorph to itself.
Symmetrie:
You can use the inverse.
Transivity:
just jump from a graph in the middle

[valid wave]

no I dont

i was answering someone else

im so lost :pepehands:

[deft current]

I think you're used to seeing relations on vertices in graphs

[pale epoch]

so do you know what a graph isomorphism is?

[deft current]

the relation isn't on vertices in a graph, it's on graphs themselves as objects

[valid wave]

no

[pale epoch]

maybe start with that

since this is part of the question

G and H in the question are graphs

so you should know what it means for two graphs to be isomorphic

i think this will clear things up

[valid wave]

ok!

so same vertices and edges

so V1 = V1'

E1 = E1'

[pale epoch]

not necessarily?

you have a bijection between vertices that preserves adjacency

(you should probably look at some examples of this)

but anyways, the question uses this definition of isomorphism to define a relation