discrete-math

[stable temple]

and got this:

is this correct so far? and, idk what to do next...

[unreal stump]

It should x T(1) in the second step

[stable temple]

oh, right!

[unreal stump]

Other than that it's fine

[stable temple]

ok

[unreal stump]

Now just move the the terms which contain G(x) to the lhs

(1-x-x^2)G(x)=2c-xc+sum(cx^n)

Simplify sum(cx^n)

And then divide both sides by (1-x-x^2) to get your gen function

[stable temple]

ah

like this?

cause the series starts at n=2?

[unreal stump]

Yes

[stable temple]

okok

[stable temple]

the numerator doesn't have real roots 😕

[stable temple]

ok so

[stable temple]

should i try decomposing the fraction now?

[unreal stump]

Yes

[stable temple]

its so ugly though

i have

and

so they're all like

[coral raven]

well they simplify

like, phi*psi = -2?

psi^2 = psi + 1?

that's the cool thing about phi and psi

[stable temple]

😮

[coral raven]

p^2 - p - 1 = 0, right?

[stable temple]

🤔

oh

yes

[coral raven]

so just apply p^2 = p + 1, etc.

[ivory sinew]

φψ = -1

[coral raven]

ah right

yes that makes sense

but things like that

[inland ledge]

wow finally I found a discrete-math discord server hurah

do you recommend any e-books for discrete math

please recommend if only you tried it yourself

[terse crane]

am i doing this right

how am i supposed to get T(3), T(5) etc

[terse crane]

pls

[unreal stump]

You can't

You get T(3),T(5)... In terms of T(1)

[terse crane]

@unreal stump Im confused in finding a pattern in this

So would it be for all 2n?

its been over a year since i took Discrete so im very rusty

[unreal stump]

Yes,You can only find a pattern for the even integers,for odd integers it will be determined by T(1) which is not given

[terse crane]

a friend of mine gave me the solution: T(n) = 2^((n-2)/2) + 2^((n/2)+1) - 1

it works, but i have no clue how he got to that solution

so im trying to figure it out myself

[unreal stump]

That is,only if n is even

[terse crane]

do u have any ideas

or hints

[stable temple]

generatingfunctionology says, for solving recurrence relations:

1. Make sure that the set of values of the free variable (say n) for which the given recurrence relation is true, is clearly delineated

by delineated does it mean it needs to be in a linear form?

i also dont understand what it means in this step:

3. Multiply both sides of the recurrence by x^n, and sum over all values of n for which the recurrence holds.

[odd saddle]

People who actually enjoy this class are masochists

[raw mason]

You seem pretty salty today

[bitter moss]

you'r'e' mom

[stable temple]

i simplified from there and put A, B, C back into the G(x) and got this:

im not sure where to go next? how do i turn this into a summation

hold on

ok im not sure what to do

[stable temple]

no wait hold on

[stable temple]

ok i rewrote the first term and replaced the numerators with symbols and divided terms by phi and psi, is this OK?

[stable temple]

yoooo i think it works >:D

[stable temple]

generatingfunctionology says, for solving recurrence relations:

1. Make sure that the set of values of the free variable (say n) for which the given recurrence relation is true, is clearly delineated
   by delineated does it mean it needs to be in a linear form?
   i also dont understand what it means in this step:
2. Multiply both sides of the recurrence by x^n, and sum over all values of n for which the recurrence holds.

<@&286206848099549185> (i asked a while back but didn't get any answer i hope its OK to ping?)

ok nvm i think i get it now! sorry!

[turbid meadow]

trying to implement 4 sets with generalized inclusion-exclusion,
i got a part missing and i dont know why it's needed: this is what i have
|A∪B∪C∪D| = |A|+|B|+|C|+|D| - |A∩B|+|A∩C|+|A∩D|+|B∩C|+|B∩D|+|C∩D| + |A∩B∩C∩D|
i know it should be
|A∪B∪C∪D| = |A|+|B|+|C|+|D| - |A∩B|+|A∩C|+|A∩D|+|B∩C|+|B∩D|+|C∩D| + |A∩B∩C|+|A∩B∩D|+|A∩C∩D|+|B∩C∩D| - |A∩B∩C∩D|

but i dont understand why

[slender dome]

okay so due to inclusion-exclusion we know that by adding |A|+|B|+|C|+|D| we are adding several elements multiple times but we doesn't want to do so

so as you did you then substract all of the |A n B|

now you substraced several things again multiple times

it would be better shown on a picture

ok sorry for my drawing skills

you can see that after substracting all of the |XnY| terms you are actually substracting AnDnC AnBnC DnBnC twice

DnBnA is empty in that case

[livid drum]

@turbid meadow sorry. last bother. its exactly as pekaro says. here is the general argument (oops 1. the count "2^n distinct regions" should be "2^n -1"; oops 2. the set subtraction by U should be the subtraction of "the rest of the elements" in U for each of those calligraphic A's. The argument is fair though.)

[slender dome]

Also i have a problem with generating functions, maybe someone can give me a hint on that

how to describe generating function of (n under m)

newton symbol

m is an natural number

[cerulean ore]

A 5 digits numbers divisible by 3 to be formed the numerals 0,1,2,3,4 & 5 without repetition. The total number of ways this can be done is?

[gritty crescent]

Hint: A number is divisible by 3 if and only if the sum of its digits is divisible by 3.

[cerulean ore]

I am trying to solve this question.
The sum of the number has to be divisible by 3 and we cannot put 0 in the start.
The number of ways to form a 5 digit number using the given numbers without repetition would be: 5*5*4*3*2

How do I find all the numbers which are not divisible by 3 and have the given digits?

Found another way

1,2,3,4,5 will sum up to 15, so 5! numbers will be divisible by 3.
If I take 0 as one of the digits then, I will have to choose 4 numbers out of 1, 2, 3, 4, 5.
Let's exclude 1, 2, 3, 4, and 5 one by one the respective sum would be 14, 13, 12, 11, 10.
So, 1,2,4, and 5 is also a combination that would work.
0, 1, 2, 4, 5 are 5 numbers so, 5! ways to arrange them, but 0 cannot be in the starting so, 5!-4! would be the ways to arrange these numbers with no 0 zero in the start.

Total ways = 5! + 5! -4! = 120 + 120 - 24= 216 numbers

[clever sage]

What is a disjoint union?

like $\sqcup$

[vital dew]

Moosey

[drifting sail]

it's like the typical union of sets except you force $A\sqcup B$ to have cardinality $\abs{A}+\abs{B}$ regardless of whether $A\cap B$ is empty or not. Sometimes it's also used as notation for $A\cup B$ when $A\cap B=\varnothing$

[vital dew]

derivada.schwarziana

[drifting sail]

see https://en.wikipedia.org/wiki/Disjoint_union

[clever sage]

so if the sets are already disjoint, it wouldn't matter for either definition?

I'm mainly asking this question to help define axiom of choice

and does this mean there's multiple possibilities for what the disjoint union could be??

@drifting sail

would it be the case that you repeat them? I"m confused by wikipedias use of 0s and 1s in second one

oh wait

[drifting sail]

yes, you can repeat them. The notation in Wiki is b/c you can't just go and define a set as
$$
{5,6,7,5,6}
$$

[vital dew]

derivada.schwarziana

[clever sage]

ahhh

[drifting sail]

if the sets were already disjoint to begin, say $A={1,2}$ and $B={3,4,5}$, then using Wiki notation we'd have
$$
{(1,0),,(2,0),,(3,1),,(4,1),,(5,1)},
$$
but obviously there's a bijection between this set and
$$
{1,2,3,4,5}.
$$

[vital dew]

derivada.schwarziana

[clever sage]

AHhhhh

[drifting sail]

as for this no; a properly defined disjoint union would be something like what Wikipedia does.

however the abuse of notation ${1,2}\sqcup{3}={1,2,3}$ is commonplace lol

[vital dew]

derivada.schwarziana

[clever sage]

is it a fancy way of getting around repeating elements in the set, sorta?

or like labeling it

so like this 5 belongs to THIS set, and this 5 belongs to THAT set

they are different 5s

[clever sage]

ahh...

then order matters for disjoint set?

i.e. $ A \sqcup B \ne B \sqcup A$

ffs

I'm still rusty at LaTeX

it shouldn't?

ahhh

it's just the assigned indexing that's different?

[sand adder]

Suppose a graph is k-vertex-connected and has at least k+1 vertices. Show that by removing k-1 vertices, the graph stays connected.

I've tried to solve this using the alternative definition: If G is k-vertex-connected, then for any pair of vertices u and v there are k disjoint paths from u to v. My initial guess was to first prove this for a graph with exactly k+1 vertices and then to deduce a general pattern. Especially, if a graph G has k+1 vertices and you remove k-1, then we have 2 vertices u and v left. So this boils down to prove that initially the edge {u,v} existed.

I've been thinking about this for 3 hours now and I can't come up with the solution

[mystic moss]

Isn’t this just the definition

[sand adder]

In some textbooks yes, in my problem set no

[mystic moss]

Okay then is your definition what you have up there

[sand adder]

right, that every vertex is connected to any other vertex by at least k vertex-disjoint paths

[mystic moss]

Okay then doesn’t the proposition follow

Think about how many paths you will “break”

By removing k-1 vertices

[sand adder]

k-1 paths i think, if these paths would go through the deleted vertices

[mystic moss]

Think about it as an upper bound

[sand adder]

so if there are k vertex disjoint paths between any 2 vertices. then there should be at least one path between any of the remaining vertices

i thought so, too. but can i just assume that we just broke the "right" paths

i dont clearly see why this needs to be the upper bound yet

[mystic moss]

Wdym right

[sand adder]

if we remove k-1 vertices, could it not be that for a specific vertex all paths went to any of the deleted vertices

[mystic moss]

What is the condition on these paths

[sand adder]

ah you're right if they would all go through the deleted vertices, it can only be on k-1 paths because they're disjoint. so the kth path needs to go through one of the non-deleted vertices (and not through any deleted one)

the cat thumbs up motivates my brain to think more

thanks @mystic moss

[mystic moss]

Lol! No problem

[stable temple]

can someone help me understand case 2 of the master theorem for recurrence relations? Where does log^{k+1} n come from?

is it because f(n) is executed log n times? then, shouldnt it be log^{k+1} f(n) instead?

(in this case 2)

(from https://cs.stackexchange.com/a/2823)

[gilded finch]

Where does log^{k+1} n come from?
Where did you read this ?

There is no such formula in Master Theorem

[stable temple]

from the link i shared above

[gilded finch]

Oh well, they do not use the exact same case hypotheses (f(n) = Theta(n logb(a) log^k n) instead of f(n) = Theta(n logb(a))

It looks like a more precise form of the Master Theorem 🤔

[stable temple]

yeah, it worked correct when i tried it, so

[gilded finch]

Usual form (eg. CLRS's) simply assume k = 0, AFAIU

[ebon valve]

how can i solve this

[weary tiger]

I'm not sure what channel is best for this, but it's related to generating functions so I'm posting it here: show that $\Sigma_{m,n}min(m,n)x^my^n = \frac{xy}{(1-x)(1-y)(1-xy)}$.

[vital dew]

lugita15

[weary tiger]

I tried approaching this multiple ways but things aren't working out. One thing I tried was manipulating the left hand side, by splitting the sum over n into the case when min(m,n) = m and the case when min(m,n) = n, but then things just get really messy. I also tried manipulating the right hand side, by expressing 1/1-x and 1/1-y and xy/1-xy in terms of infinite series. But I'm not making progress that way either.

[obtuse lance]

I'm thinking split it as $$\sum_{m=1}^\infty \sum_{n=1}^\infty \min(m,n) x^my^n$$ $$= \sum_{m=1}^\infty \left(\sum_{n=1}^{m-1} \min(m,n) x^my^n + \sum_{n=m}^\infty \min(m,n) x^my^n \right)$$

[vital dew]

Merosity

[weary tiger]

@obtuse lance Yeah, that's exactly what I did. The sums start at 0 by the way, not 1.

Not that it makes much of a difference.

[obtuse lance]

it can't start at 0 because it has xy in the numerator

[weary tiger]

@obtuse lance Sorry what?

[obtuse lance]

expand the 3 geometric series on your RHS

(1+x+...)(1+y+...)(xy+(xy)^2+...)

this looks like xy+... when you combine it together

but if your sum started at m=n=0 then you'd have 1+...

so it can't

[weary tiger]

@obtuse lance Oh that's a good point, maybe my Professor made a typo.

@obtuse lance Wait but min(0,n) and min(m,0) both equal 0, so the 0 terms are just zero anyway.

[obtuse lance]

haha good point

well either way makes no difference so we're good

[weary tiger]

@obtuse lance In any case, so I did what you did, but after that I wasn't able to get anywhere useful. It just becomes messier and messier.

[obtuse lance]

it should be pretty easy after that step

[weary tiger]

Like the first term in the parenthesis is a finite sum that doesn't seem to equal anything nice.

[obtuse lance]

you can handle them with derivatives

[weary tiger]

Oh how?

[obtuse lance]

it should be a finite geometric series I think

$x \dv{x} x^n = n x^n$

[vital dew]

Merosity

[obtuse lance]

this kind of trick

then pull the derivative out of the sum

[weary tiger]

Hmm, I'm not really familiar with how to write these things in terms of derivatives, can you explain further?

[obtuse lance]

$$\sum_{m=1}^\infty x^m \sum_{n=1}^{m-1} n y^n$$

[vital dew]

Merosity

[obtuse lance]

this sum is what you want right, just making sure

[weary tiger]

yeah

[obtuse lance]

$$\sum_{m=1}^\infty x^m \sum_{n=1}^{m-1} y \pdv{y} y^n$$

[vital dew]

Merosity

[weary tiger]

Oh, you have to use partial derivatives?

[obtuse lance]

$$y \pdv{y}\sum_{m=1}^\infty x^m \sum_{n=1}^{m-1} y^n$$

[vital dew]

Merosity

[obtuse lance]

idk if you have to but it's a pretty standard generating function trick

probably the first one I ever learned tbh

[weary tiger]

Ah ok

So then how does that help you, expressing it all in terms of the partial derivative?

[obtuse lance]

can you not simplify the sum now?

just focus on the inner most sum one at a time

[weary tiger]

Oh right

[obtuse lance]

cool gonna make some coffee let me know if you run into too much trouble 😛

[weary tiger]

OK thanks for your help!

[obtuse lance]

you're welcome 👍

[weary tiger]

@obtuse lance OK, things are getting messy again. After summing over n, should I differentiate first or sum over m first?

[obtuse lance]

sum over m next

differentiate at the very end

cause at that point you won't have a sum to worry about

[weary tiger]

@obtuse lance But I don't know how to sum either $1-y^{m+1}$ or $\frac{1-y^{m+1}}{1-y}$ over $m$. In the first case summing 1 gives you infinity, though of course in the generating function context we're not concerned with convergence.

[vital dew]

lugita15

[obtuse lance]

should be m cause it went to m-1

$$y \dv{y} \sum_{m=1}^\infty x^m \frac{y^m-1}{y-1}$$

[vital dew]

Merosity

[obtuse lance]

or I guess it doesn't start at n=0 but n=1 lol

but since it didn't matter we might as well make it n=0

let's pretend I wrote everything with m=0 and n=0 to start it lol

[weary tiger]

sure

[obtuse lance]

so now 1/(y-1) factors out

and you can separate it as two sums

I was gonna write it but I think you should

[weary tiger]

Oh I see the problem, I dropped x^m from the first sum by mistake at some point.

[obtuse lance]

you can write it on paper and send a picture you don't have to latex it or whatever

oh ok

[weary tiger]

Now things are working out.

[obtuse lance]

yeah you don't have to write it if you got it worked out now then lol

[weary tiger]

@obtuse lance I got an answer now, but it's wrong, I don't know where my error is:

I hate problems like this, there's one zillion places where you can make errors.

[rose wing]

May I ask, if I have 20 assets, and I want to calculate the VaR. Then how to compute the sigma? The formula of sigma already shown on the slide.

I need to add up 400 items for the computation of sigma, if n = 20?

[gilded finch]

Yes

[rose wing]

but how to solve it in practice?

[gilded finch]

Don't, VaR is bullshit

[rose wing]

why lol

[gilded finch]

https://arxiv.org/abs/2001.10488

The assumed underlying distributions are plain wrong from the start, VaR will fail you hard when real risk emerges

VaR only works when there's no risk, ironically

(wrong channel btw, see #probability-statistics )

[slim storm]

how do i apply the stars and bars theorem such that there aren't any consecutive bars (zeros)?

forget it, did it by hand...

[daring crater]

Let $n_k$ be the number of uncovered elements in the k-th iteration in weighted greedy set cover algorithm. How exactly does inequality 1.6 follow? The hint in the text doesn't really help.

[vital dew]

Darius

[remote mulch]

question 2

the base case n=0 is not true...

-1 != 0

or am i missing something

cus the question says true for all n >= 0

[pale epoch]

how is the LHS equal to -1 for n=0?

ah, i see

well, technically this is the sum $$\sum_{k=1}^{n}(2k-1)$$

[vital dew]

Lochverstärker

[pale epoch]

and for n=0, this is also 0

so the notation here is unfortunate

(just start from n=1 if that bothers you)

[oak spire]

how it got this

[vital dew]

slimvesus

[ebon valve]

anyone can help me with this ?

[pale epoch]

did you do similar examples in class?

[ebon valve]

this is my answer

im not sure if it is correct ?

[pale epoch]

why is F adjacent to H? and H not adjacent to F?

[ebon valve]

oh i fix it now

now is this correct ?

[pale epoch]

i don't know, what is your reasoning behind this?

[low raven]

Hello, can anyone help me understanding a proof? its about graph theory

[river dawn]

???

[solid garden]

could i get some help with permutations/combinations?

[ebon valve]

is this correct ?

[last timber]

what are you doing here?

[ebon valve]

mathematic induction

[last timber]

ok lol

the statement is false

that;s why proof fails

because

,calc 3^7

[vital dew]

Result:

2187

[last timber]

,calc 7!

[vital dew]

Result:

5040

[last timber]

@ebon valve

[ebon valve]

how to solve this problem ? can u show the correct working

[last timber]

wym

the statement is false

you cannot force 3^n > n! to be true

i gave you counterexample that for n = 7 ineq does not hold

[ebon valve]

this chapter is about assuming ( mathematic induction)

[last timber]

yes, but for this particular problem induction fails

because the statement is false

[obtuse lance]

I'll try writing it out, maybe that will help show you what @last timber is saying
$$3^n>n!$$
$$3^7>7!$$
$$2187 > 5040$$
but this is false

[vital dew]

Merosity

[last timber]

my name is very funny

[ebon valve]

hmm

can someone show me the working

[obtuse lance]

I just did

do you not know how to calculate 3^7 or 7!?

[ebon valve]

then that means the question is wrong ?

[obtuse lance]

that's what we're saying

the question is wrong

[ebon valve]

hmm

[errant bear]

lol

ok but for real how to solve

[buoyant raven]

factorial will always eventually overtake exponential (the graph grows faster) so from the start the statement cannot be proven

[errant bear]

can you show me the working

[iron pine]

can u help me with that

[harsh warren]

hey i've got a quick question: are linear time transformations/reductions reflexive and transitive (like polynomial time transformations)?

[shut fjord]

Need some help understanding Lemma 3 of the Euclidean Algorithm if anyone can break this down from the pdf:

Specifically the part highlighted in red, when they substitute m for the floor of x/y shouldn’t there be an extra y left over?

It says r = x - my = x - [x/y] (sorry I’m not using latex)

But what happened to the extra y if m is the floor of x/y?

[hazy pine]

yeah, it seems like a typo

i believe thats meant to be $r = x - my = x - \floor{x/y} \cdot y$

[vital dew]

Namington

[hazy pine]

and then the argument makes since in that $r - x = \floor{x/y} \cdot y$ and so $r \equiv x \pmod{y}$

[vital dew]

Namington

[hazy pine]

by definition.

@shut fjord

[shut fjord]

Yeah

The pdf is in its alpha state, my CS department has been creating it since last semester

[hazy pine]

yeah, i'm assuming they just made a typo

the argument doesnt make sense otherwise

[shut fjord]

Side question, how long did it take you to pick up latex?

Because I’ve never used it before, but my class is requiring we do it

[hazy pine]

able to write basic mathematical statements: like 30 minutes
able to make proper documents: a week or so to learn the ropes of formatting and whatnot, sometimes i still have to google random stuff like how to reference a theorem with a hyperlink or w/e

and if i want to do something i don't know how to do, i can always google it

the tex stackexchange is fairly active.

able to write tikz: ?????

i didnt really like, sit down and tell myself "time to learn this" though

i just started writing documents

and googled whenever i needed to do something

theres lots of resources

in any case, it didn't take much time or effort to get into a functional state

[shut fjord]

@hazy pine thanks for the insight. Also got the pdf fixed because of that little error by a staff member

[low raven]

hello, does the prim algorithm just find the lowest weight tree, and there is one or can be more?

i guess there can be more, but the prim algorithm just finds one of them

[iron pine]

can u solve this

<@&286206848099549185>

[gilded finch]

yes

[sand adder]

@iron pine use the symmetry of M due to undirectedness

[iron pine]

can u explain the steps

[sand adder]

draw a simple undirected graph 4-5 nodes maybe, write down the adjacency matrix and perform the matrix multiplication. you should see the pattern

u will see its symmetric along the main diagonal. that means for any i, row(i) = col(i). [M^2]_ii is then the dot product of row(i) with col(i). because they're the same and the entries are either 1 or 0, the sum of squares of entries (which is the dot product) is the same as the sum of entries.

[crimson sigil]

can someone check my solution for this knapsack problem?

[crimson sigil]

<@&286206848099549185>

[iron pine]

in b the question asks " b) What does it mean?" i could not understand that question

what is the point of these two question that i send ? i could not understand , proving this has any importance?

[weary tiger]

can someone help me

im confused with this

[last timber]

it would be better if you give context

[weary tiger]

I don't know how to do lol

Don't even know how to start with

is the output return 4?

[crimson sigil]

yes it will be 4

m=4 and n=3, so m>=n holds true

[crimson sigil]

so output is 4

[weary tiger]

also wait

im confused on the number thingy

Do you have to put return here?

is it return 3.5?

[crimson sigil]

yeah 3.5

[weary tiger]

do i have to put return?

or just 3.5?

@crimson sigil

[crimson sigil]

just 3.5

[weary tiger]

im confused on this

[crimson sigil]

First it will give you 'D' and then 'B'

[weary tiger]

hmm

idk how to put it tho

[crimson sigil]

D,B

like this

[crimson sigil]

or
D
B

[weary tiger]

THANK YOU 🙏

[atomic ibex]

Does the exclusive disjunction (XOR) operation follow the associative law?

[crimson sigil]

yes

[atomic ibex]

Thanks

[atomic ibex]

Can I post a question again?

[weary tiger]

Can someone help me with this

[errant bear]

no

[crimson sigil]

3

[fresh rapids]

Am I correct in assuming that i can just use De Morgan's Laws on the first half of this to verify the logical equivalence?

[foggy hatch]

It depends. Do your De Morgan's laws deal with three terms like that? If not, then no, it's not that simple.

[fresh rapids]

Only has two terms so guess im back to the drawing board. Thanks 🙂

[amber hill]

De Morgan's holds for 3 variables too

[fresh rapids]

Perfect. Thank you.

[foggy hatch]

I assume the point of exercise 60 in that book is to prove it from less powerful things

$\land$ not $\and$

[vital dew]

dirib
Compile Error! Click the reaction for more information.
(You may edit your message to recompile.)

slimvesus

[amber hill]

I mean basically you can assume (AU B) = D too so De Morgan's holds

[foggy hatch]

That is a hint to the problem, yes.

[foggy hatch]

The point of an exercise is to practice applying the facts you've covered so far in more complex situations. If you haven't covered "De Morgan's for three variables" so far, you're defeating the point of the exercise (and probably won't get much credit if this is being graded).

[fresh rapids]

Ill have to go back through the slides

[fresh rapids]

Im not familiar with usernamephobics notation, what is the U? And the one you showed is the exact opposite of my case. not (p1 ^ pn) instead of not (p1 v pn). Im having a hard time understanding how to apply it.

Sets are the next lesson i think so know nothing about them. As for swapping it to my case, do i just need to negate the statement basically?

Alright ill try that

Ahhh ok

I think I got it?

[amber hill]

Yes, I think but you are comparing p and q ^ r, so putting them in bracket would be nice

[fresh rapids]

Fixed. Thank you both for the help 🙂

[gritty crescent]

Why is the empty-set excluded from the partition of a set?

(Since it doesn't seem to harm the fact that the union of subsets should be the set itself, and it won't naturally be equal to any of the other non-empty sets and would have a null intersection with them)

[last timber]

because to produce a partition of a set is like to divide set into its subsets so that each element of the set is in exacly one element of a partition

and you can see that there is no element in {}

[gritty crescent]

Makes sense, thanks!!

[maiden shell]

Hello, I have a question regarding Petersen graph. I have to find it's automorphism group and it's orbits and fixed-points.

I found this proof of automorphism of Petersen graph:

https://arxiv.org/pdf/2012.02942.pdf

However, I'm quite new to this topic, and I have trouble finding the fixed-points and orbits

Could someone give me a hint?

[crimson sigil]

<@&286206848099549185> Can anyone help me with part B and C in this Graphical method question?

[harsh warren]

hey i have a question relating to graph theory:
can a graph with 3 vertices (triangle), with one matching edge, be an M-alternating cycle?

this graph for example with the matching, M = {ab}

so if we take cb, ba, ac, it is M-alternating. but if we take ab, bc, ca, it is not M-alternating

[weary tiger]

Can someone help me with this

[river dawn]

Wth is that💀

[errant bear]

their hw

[languid cradle]

yo i have no idea what to do with this

[balmy cedar]

@weary tiger Isn't that an algorithm for Collatz' conjecture? No matter what natural number you plug in the algorithm, it will reach 1 in the end? What do you want help with?

[weary tiger]

I need to get output but not sure if it N

[balmy cedar]

Shouldnt it print numbers?

[languid cradle]

theres 14400 possibilities

but i need to exclude the ones where 1,2,3,4,5 arent covered at least once

[balmy cedar]

Like, for 12, for instance, it should print: 12, 6, 3, 10, 5, 16, 8, 4, 2, 1

Not sure what kind of application you use though

[weary tiger]

How did u get numbers?

IM so confused bro

[errant bear]

literally just follow the arrows

[weary tiger]

i did

i go tN lol

[balmy cedar]

@weary tiger You're supposed to replace N with a concrete number. For instance, if the input is 12, the second box says "print 12", not "print N"

[weary tiger]

OH yeaa

smh

[balmy cedar]

do you get it now?

[weary tiger]

yea but howd u get 3, 10,5,8,4,2 and 1

[balmy cedar]

Let's say N is 12 and you reach the box that says N = N/2. This box means that from now on N should be replaced with 12/2= 6 instead

Was that clear?

[weary tiger]

yea

i know that

how about others?

6==1

[balmy cedar]

This box is different since it has two = signs. Now you should NOT change N. This box just asks a question: is 6 equal to 1?

[weary tiger]

no

[balmy cedar]

then you should follow the "False"-line

[weary tiger]

ohh

i get it on

we keep following the false line till it equal to 1

or if the number is not even

[balmy cedar]

Well know you reach the box that says print 6

now*

I guess it means that you shall write down 6? I dont know what the exercise is exactly

[weary tiger]

yea

[balmy cedar]

After you have written it down, you must continue to the next box, that says "6 is even"

(You must continue even if it means that you visit some boxes more than once. You're not done until you have reached the box that says STOP)

[dusk stirrup]

I dont want the answer, but can someone just tell me what 15 references? Is it vertices?

[balmy cedar]

Yes, it's the number of vertices

[dusk stirrup]

So if there are 15 vertices and its a cycle graph, so each having a degree of two, that gives me a sum of degrees of 30. If I divide that in half, it would give me 15. Does that mean there are 15 edges?

I don't know why I didn't just try that. Ignore me.

[balmy cedar]

As you say, you can draw it and count the edges. But giving an argument like you do first is actually better

Because you can now easily give the answer for any number of vertices, you have found the pattern

[dusk stirrup]

thank you!

[weary tiger]

how do I show this is true

does the left side simplify to p implies p?

[analog sonnet]

Construct a truth table

[weary tiger]

so it says I shouldn't use a truth table rather the identities

[analog sonnet]

Man I don't understand why teachers hate truth tables so much

They're very useful

[weary tiger]

my teacher is a weird

[analog sonnet]

Yours hasn't been the only one

I've answered quite a few questions like these in the past

All of them be like "oops sorry you can't use a truth table haha"

[weary tiger]

lmao

so can you point me in the right direction or

[analog sonnet]

Well

If p AND q is true, then p is true AND q is true

which clearly implies that p is true

qed

you could alternatively use the identity that A implies B is equivalent to (NOT A) OR B

[weary tiger]

so I used that conditional equivalences and then applied demorgans law, so now I have Not P or Not Q or P?

[analog sonnet]

Let me do this on the fly: $p\wedge q\to p\iff\neg(p\wedge q)\vee p\iff \neg p\vee\neg q\vee p$ yep it checks out

[vital dew]

(R/I)/(J/I) S + F bending PhD

[analog sonnet]

Then you can use the fact that $p\vee\neg p$ is always true

[vital dew]

(R/I)/(J/I) S + F bending PhD

[weary tiger]

is there an order of operations i should be worried about?

[analog sonnet]

nah

[weary tiger]

in this case

[analog sonnet]

it's because you end up with only ORs

You have to be a bit more careful when also ANDs are involved

[weary tiger]

so now I have
True or Not q

[analog sonnet]

But the rule of thumb is that AND behaves like multiplication and OR behaves like addition

[weary tiger]

I see there is a identity that says True or P is True, but I'm not sure how the negation effects it

[analog sonnet]

compare $a\cdot(b+c)=a\cdot b+a\cdot c$ and $p\wedge(q\vee r)\iff p\wedge q\vee p\wedge r$

[vital dew]

(R/I)/(J/I) S + F bending PhD

[analog sonnet]

True or (any other statement) is always true

[weary tiger]

ohh ok

[analog sonnet]

Just substitute P with (NOT q) and you're done

[weary tiger]

Damn you're actually amazing, that makes sense I'm just having a hard time adjusting to this type of math

[analog sonnet]

Sorry to burst your bubble but 1) I'm not that amazing and 2) this is hardly math

It's more like first order logic

[weary tiger]

well the dude said it's math so idfk anymore

[analog sonnet]

Well it is the very foundation of math, that's true

Math wouldn't exist without logic axioms

[weary tiger]

i thought i was going to learn about a rapper

[analog sonnet]

But it's kinda like calling an egg a chicken

[weary tiger]

i see

[analog sonnet]

🥚 🐔

[weary tiger]

does this mean the egg came first

[analog sonnet]

Now we're getting philosophical

[weary tiger]

wrong channel xD

[analog sonnet]

[weary tiger]

well now I shall try my next few problems thanks again

[analog sonnet]

But honestly I would welcome questions about logic in this server

So please don't hesitate to return if you have additional questions

[errant bear]

okay cool

[balmy cedar]

@weary tiger did you understand how to read the diagram in the end?

[weary tiger]

Yeh little bit

but i understand the concept how to do that

[balmy cedar]

okay, just ask if there is anything else

[weary tiger]

yea for sure @balmy cedar

thank you so much 😊

[dusk stirrup]

So for this one, I am really confused. It is a homework question so I apologize but I'm not looking for the correct answer. Just what I am doing wrong here.

• What is the diameter of the cycle C15?

So the diameter, I believe, is the greatest distance between two vertices on a graph. Since it's a cycle, this would place it in the middle. So the farthest distance from one point to any other point is seven correct?

What am I doing wrong here?

[balmy cedar]

Yes, seems correct to me.

[dusk stirrup]

So weird, it's telling me it's wrong..

[balmy cedar]

Weird, what does it say is the answer? Does it come with a solution manual?

[dusk stirrup]

Nope. It's edfinity so it just says the answer is wrong. I'll message my professor because it's confusing me.

[balmy cedar]

Yes, just checked the definition, diameter is usually defined just as you said. And in this case the answer should be 7

[dusk stirrup]

Strange. Alright, well I appreciate your time.

[weary tiger]

Sorry if this is the wrong channel.

What would a list of elements that extends infinitely in both signs of indices be called? Essentially a sequence but without a first term. Is that still a sequence? If so, I think then that Wikipedia is wrong in saying that "a sequence can be defined as a function whose domain is either the set of the natural numbers (for infinite sequences)".

I am, in turn, trying to figure out if "integers" in this section of my professor's notes should instead be "positive integer" or "natural number":

[near prawn]

should be pos integers

[stable granite]

I agree with lemon

[merry steeple]

is (not A V not B) same as not(A V B)?

[stable granite]

Nope

You have to have and operator

Between a and b in second expression

[merry steeple]

oh i see.... so what would not(A V B) be if you expand it?

lol i thought it was distributive

oh nvm i got it, thanks @stable granite

[normal sentinel]

for 1) why is the 3+6+9+12+... not included in the proof?

and for 2) how does that prove it? he just plugged it in

[errant bear]

you're showing it true for n=1, the base case

so the sum is just the first term, 3

[normal sentinel]

hmm

[errant bear]

n=2 would be 3 + 6

[normal sentinel]

i see. and what indicates that function is the “...” ?

[errant bear]

yea, its just another way of saying the sum from i=1 to n of 3i

[normal sentinel]

for 3) he put ...+3k +3(k+1) to prove n=k+1

why is that first 3k included if its just n=k+1

[errant bear]

because its the previous term

[normal sentinel]

ah ty

[weary tiger]

I am doing question 6, is that correct?

[weary tiger]

idk what to tell my professor...

[unreal stump]

I mean, That's literally the same as considering the index set to be N, since Z and N are isomorphic

[weary tiger]

I don't think I understand your point. For clarification, this is referencing a previous thing I posted here, and also the problem with what he said is that if say the sequence starts at -10, this theorem does not hold true for n = -11.

The strange indices are fine, it's the fact that the sequence would have to go backwards infinitely for this theorem to hold true.

[coral raven]

but we can just define the sequence infinitely off of f(n)? so it's a weird sorta sequence but it works?

[obtuse lance]

I wouldn't worry about it if I were you

the limit is being taken as n-> infinity, so it's not really that relevant

[weary tiger]

A sequence is different from its defining function, is it not? In fact, can't the same sequence be defined by different functions as long as they act the same for natural number inputs? I guess I am making to big of a deal about this though.

[obtuse lance]

yeah that's right

explicitly if you use f(x) you could also use f(x)+sin(pi x) and get the same sequence

[coral raven]

yeah so it's an 'if' not an 'iff'

still works

i think

[errant bear]

what is an iff

[coral raven]

it's like

say you had a wire

and you were considering how many ways you could make the two ends meet

where two shapes are different if you can't turn one into the other without allowing the wire to pass through itself somewhere

so these are like just knots

and there's gonna be a lot of them

in fact there's an infinite number of knots, some more fundamental than others

and the fundamental ones are called prime knots

now bear with me here

in the olden days, people used to think that different atoms corresponded to different knots in the 'ether'

and they were dumbasses

hah! suck it, lord kelvin!

[errant bear]

is this a pasta

[weary tiger]

Iff is shorthand for "if and only if"

[obtuse lance]

@weary tiger nice pfp btw

[weary tiger]

Thanks, do you watch theminutehour? It's a hue shifted screenshot of the face of the main character of this animation: https://www.youtube.com/watch?v=EkDOuRAwrYE

[errant bear]

i was asking which statement they thought was an iff

[obtuse lance]

yeah lol that's why I like it

[untold hare]

A bank account provides annual interest in the following way: they pay 4% interest on the previous
year’s balance and 12% on the balance of the year before. If you put $600 in this account, how much
money will be in it after 26 years? Show the recurrence relation you use to find the answer.

[last timber]

what have you tried and where are you stuck

[untold hare]

so, apparently all the work i’ve done so far is right and the advice my teacher gave was to write code for it. but does anyone have any advice?

i’ll copy my work one minute

I started out with an = 1.04(an-1) + 0.12(an-2). The first half makes sense to me that it's just the previous year's balance plus 4% of that year's balance. I went on to write out the first few in the sequence in terms of a0 getting: an= 1.04^n(a0). The 12% interest part is confusing me. I tried a similar approach writing out the first few in the sequence:
a0= 600
a1= 1.04(a0)
a2= 1.04(1.04(a0)) + 0.12(a0)
a3= 1.04(1.04(1.04(a0))) + 0.12(1.04(a0))
a4= 1.04(1.04(1.04(1.04(a0)))) + 0.12(1.04(1.04(a0)))
an= 1.04^n(a0) + 0.12(1.04^(n-2)*(a0))

[last timber]

well

ye, this looks correct one

[vital dew]

Commander Vimes

[last timber]

it is correct

[vital dew]

Commander Vimes

[last timber]

now, have you ever heard about characteristic equation of recurrence relation?

[untold hare]

i’m not sure maybe if i see an example (this is a very short 6 week class)

[vital dew]

Commander Vimes

[untold hare]

yeah, i already tried lol. i got very overwhelmed

[vital dew]

Commander Vimes

Commander Vimes

[untold hare]

yes, i’ve seen that before

[last timber]

suppose this equation has two distinct real roots

[vital dew]

Commander Vimes

Commander Vimes

[untold hare]

okay, so i'm looking at a similar problem i worked but i was given c1 and c2 for the recurrence relation

[last timber]

well in your case you also have c_1, c_2 given

[untold hare]

600 and 624?

[last timber]

c_1 = 1.04, c_2 = 0.12

[untold hare]

oh

[last timber]

600 and 624 are initial conditions

600 = a_0, 624 = a_1

[untold hare]

i'm writing it out rn using the quadratic equation to find the roots?

[last timber]

ye

[untold hare]

almost done

not really sure how to check my answer or if i made a mistake

also i got this right off the bat the first time i tried but i was following an example of my teacher's that's why i did the like an = 1.04^n(a0) ... approach but i don't have to do any of that?

[last timber]

you can just expand

but in case with recurrence of second order this is going to be cumbersome

,w x^2-1.04x-0.12=0

[vital dew]

Results provided by WolframAlpha

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

Requested by Commander Vimes#0001

[last timber]

ok seems to be fine

[untold hare]

wow

that's a much better approach without all the headache

i dunno why my teacher didnt suggest it 😭

thank you for the help

so, just to clarify with simpler problems you can just expand them to find the answer. but with more complicated ones like this it's better to just use the method of finding the characteristic equation, etc

[last timber]

ye

[unreal stump]

Also,suppose the two roots are equal,then the solution to the recurrence will be of the form (a+bn)p^n where p is the equal root

[untold hare]

I also have this problem: Let 𝐸 be the event that a randomly generated bit string of length six contains an odd number of 1s, and let 𝐹 be the event that the string starts with a 1. Are 𝐸 and 𝐹 independent? Why or why not?

which I solved but I'm wondering if there's a better way to do the last part. i can post my work

all the similar problems I found just wrote out what is in both E and F but they were much shorter problems. Is there a better way other than writing them all out like I did?

[round geyser]

is there a lot of reserach to be done in graph theory\

is it a hot field

[untold hare]

i think i got it first bit should be 1 so that leaves 5 to choose from, 5c0 + 5c2 + 5c4 = 16 P(EnF) = 16/64

[primal lava]

yes

wait

bro

are u the real djokernole

@round geyser

[balmy cedar]

I looked at the numbers of papers submitted to arxiv. Since 1995, the areas that had the most increase relative to others are: optimization and control, probability, number theory, numerical analysis, combinatorics, PDEs. Looking at the submissions in combinatorics this month, I would say that at least one third of them are about graph theory

So I would say that graph theory is an active field

[terse crane]

am i using this recursion tree correctly?

[orchid saddle]

Does anyone understand this

[errant bear]

the inequalities, definition, or what

[orchid saddle]

Like why is it 4n^3

@errant bear

[errant bear]

a + 2a + a = 4a

a=n^3

[orchid saddle]

and why n > = 3

[errant bear]

because the inequality isnt true for n=2

[orchid saddle]

but how do u know it works for 3 and above

is there a way to figure it out

or just checking

[errant bear]

i mean its sort of obvious, 2^3 < 16 < 3^3

and you know n^3 grows, so you just need to find any case that works

[orchid saddle]

oh ok

[clever sage]

Verify that if $S$ is finite, then any injection from $S$ to itself is also sur-jective.
\begin{center}
Let S=${x_{1},x_{2},x_{3}...,x_{n}}$, where $n \in \mathbb{N}$. We define injective function $h:S \rightarrow S$. We know $S$ has $n$ elements. This must mean that the range of $h$ contains at least $n$ elements, but we know that the range of $h$ is a subset of $S$, so it also has at most $n$ elements. We can only conclude then that the range of $h$ contains exactly $n$ elements, and therefore, the whole of $S$, meaning $h$ is surjective.
\end{center}

[vital dew]

Moosey

[clever sage]

Nvm.

[round geyser]

Would it be safe to assume or state that Nash Equilbrium is a major topic/part of Game Theory?

[burnt pewter]

https://cdn.discordapp.com/attachments/763494654007836732/802210024348319846/unknown.png

[errant bear]

ok

[burnt pewter]

how do

[last timber]

[pale epoch]

you have to use the definition of the set B

Assume that B is in B, then by the definition of B ...
Now assume B is not in B, then by the definition of B ...

@burnt pewter

[river dawn]

Somebody

[gritty crescent]

Wrong channel. Try the general question channels, or #geometry-and-trigonometry .

[molten hearth]

Is this statement true?

I mean $$ \abs{a+b} = \abs{a} + \abs{b} $$ right?

[vital dew]

dlp

[molten hearth]

So the statement is partially true in the sense that it uses the geq operator, but the g in geq never kicks in so I am in two minds

[unreal stump]

If a and b are of the same sign,yes equality holds

[molten hearth]

ah

the statement does not say anything about same sign

yes yes thank you

[weary tiger]

fun thing yall might appreciate

especially the little "Homework"

|| The infinite 'library' of all (page-orderless) 'books' of scrawlings on R^2, which contains as subsets every library which ever existed or will exist ||

[atomic ibex]

This equivalence confuses me a little.

The sentence says that the biconditional of p and q is equivalent to "p if q" AND "p only if q".

The latter part of this conjunction is logically equivalent to "if p then q" and which is equivalent to "if not q then not p", but in the truth table they use "(p ->q) AND (q -> p)", the latter part of which is confusing me.

Also wikipedia said that "p if q" is the reverse of "if p then q" but I don't understand what that means.

[midnight dock]

Discrete maths books are just too confusing smh, so hard to read

[balmy cedar]

@midnight dock Which book do you read? So I know what to avoid 😆

[midnight dock]

Uhhh well i tried reading the rosen book cus a lot of people say its great and i think its actually really good cus the author writes as if he knows whats going on in the reader's head

Unfortunately the pages were a bit too wordy for me

I didn't even finish the entirety of the first chapter of the book so I'm not one to say its a bad book

Maybe give it a read yourself and see if you like

Although my opinion may have already given you a bias

[balmy cedar]

Well, I know many of the topics in the book I think, so I didnt plan to read it

But do you generally like concise/symbol-heavy books?

Rather than wordy

[midnight dock]

Well maybe something in the middle would be nice, where they like to skip some tiny details and give us a case

[errant bear]

y make word when symbol do trick

[balmy cedar]

Yes, sometimes you learn more from figuring out the intuition yourself, rather than being "served" everything in length

[midnight dock]

True

[balmy cedar]

But other times an informal discussion of the intuition is in place, all depends on the topic imo

At least if the intuition behind the topic is not very accessible

Another way is to incorporate exercises in the text that you have to do before moving on, like Tao does in his analysis books I think

He does it in Epsilon of Room

In any case, no point in wasting time on a book that doesnt suit your learning style, when there are so many options out there

At least in undergraduate subjects

[fallen tinsel]

i know the empty set is a subset of $\mathbf{z}$ but is the {{emptyset}} a subset of $\mathbf{z}$

[vital dew]

bakes

[errant bear]

do u mean the set containing the empty set

[west hedge]

I was wondering what they were smoking when I was just looking at the TeXit output lol

[fallen tinsel]

yeah my bad hahaha

like is the set containing the empty set a subset of integers

[errant bear]

is the set containing the empty set an integer

or the empty set itself

[fallen tinsel]

empty set itself right

[errant bear]

is {} = {{}}?

(no)

the set on the right, contains an element, namely the empty set

[fallen tinsel]

this is the question btw im now thinking its 1,2,4 and not 3

[errant bear]

mmhm

[fallen tinsel]

thank you !

[shut fjord]

Can anyone suggest how modular could help with this contradiction?

So far I believe no solution would have different values on the LHS & RHS using same mod..but I don’t know of such a mod or how to prove if that is the case

I do know that the 2 will not be going anywhere from the equation so perhaps that can be used with my mod?

[clever sage]

wait

mod 5 seems the most obvious to use

properties of mod also show amodn+bmodn=(a+b)modn

and squaring mod numbers only given you a certain mod in turn

so you only need to check 1,2,3,4

squared, and what their mod must be

@shut fjord understand?

[shut fjord]

I’m a bit confused at the squaring portion

[clever sage]

so integers can only be 0,1,2,3,4 mod 5

yes?

[shut fjord]

Squaring mod numbers only gives you a certain mod in return?

[clever sage]

yes

and it will be like a pattern

[shut fjord]

Doing up to 4 will give us that integer back

[clever sage]

wait

[shut fjord]

mod(1,5) = 1, ... , mod(4,5) = 4

[clever sage]

yes

but what is mod(2,5)

[shut fjord]

2

[clever sage]

yes, and mod(2^2,5)

[shut fjord]

4..

[clever sage]

and mod(3^2,5)

mod(4^2,5)

[shut fjord]

4

Wait

[clever sage]

it loops you see

[shut fjord]

It wrapped around

[clever sage]

014410...

[shut fjord]

Never goes passed 4

[clever sage]

notice that left hand side must be 2 mod 5

and rhs can never be 2 mod 5

only 1, 0, 4 mod 5

[shut fjord]

Do I have to be concerned about the x^2 or y^2?

This is why I square the mod numbers I believe right

[clever sage]

yes

[shut fjord]

So if I can show that amodn + bmodn != (a + b)modn

[clever sage]

no no

wait

yeah, if you can show that, then you will come to a contradiction

because that property is always obeyed

[errant bear]

wut

[clever sage]

you know one side will always have the form 2 mod 5, and rhs will never be equal to it, due to squaring pattern of 1,2,3,4 mod 5

[languid cradle]

this is confusing me

i drew this

[mint steeple]

Oh no.

A pupil who has two people vouching for him is not the impostor.

and then you know he tells the truth.

and even if only one guy vouches for you, that is verified, you are also verified.

And now I am confused as well.

[languid cradle]

yeah I’m wondering if my prof messed something up

his english is not always the best lol

[mystic moss]

@languid cradle try drawing out the intervals for which each student was at the library—I think it’ll help in seeing the inconsistencies with what the students are saying

[languid cradle]

ahhhhh

I was thinking about students being there at certain times

but I didn’t consider that a student could be there over multiple time intervals

ok thanks

[balmy cedar]

But the exercise says that the students are there once. And this must be important, because if we allow multiple visits, it's easy to construct a timeline where everyone tell the truth.

And I would assume it's also important that when two students have overlapping visits, there must be an edge between them in your graph.

[languid cradle]

yeah makes sense

I didn’t mean repeated visits btw

just that intervals for students overlap non-perfectly

I guess would be more accurate to say

[balmy cedar]

Ah, okay, what do you mean by non-perfectly btw?

[languid cradle]

the intersection of two student’s time intervals doesn’t necessarily have to be equivalent to one time interval

like they can be there for some of the same time

but some of their respective intervals could be exclusive to them

student A could be there from 8-9, student B from 8:30-9:30

[balmy cedar]

Yes, that's true, no such restrictions are given in the exercise.

One inconsistency I noticed is in the cycle A-E-C-D-A. I think at least one of the edges A-C or D-E should be present.

I don't care that about the direction of the edges now btw, I just consider the undirected graph

Anyways, in what course did you get this problem? Is there some part of the curriculum that should be used for this problem?

[balmy cedar]

@languid cradle Since you drew the graph, I assume it's related to graph theory. If I have read the exercise correctly, I think it's possible to deduce that ||every 4-cycle in the (undirected) graph should have at least one chord (edge crossing "inside" the cycle). Then consider all 4-cycles without chords, is there a vertex that is present in all of them? ||

[shut fjord]

Can anyone verify if I have to be worried about the x^2 variable? I’m trying to show that the LHS and RHS cannot be equal to one another

[obtuse lance]

you've done it wrong by dividing by 5 and doing mod 5

look at $ 5x^2 +2 = y^2 \mod 5$ directly

bot dead I guess lol

@vital dew

[shut fjord]

Yes latex bot is not working ):

5x^2 + 2 = y^2mod 5?

[obtuse lance]

yeah

this make 5x^2 = 0 so it's just

2 = y^2 mod 5

[shut fjord]

Shoudn’t I have mod on the lhs as well though?

[obtuse lance]

the mod applies to the entire equation

you can put it on both sides if it makes you more comfortable, some people don't even write it

[shut fjord]

5x^2 = 0...

That’s what I wanted to get rid of..

[obtuse lance]

because 5 = 0

mod 5

this is all mod 5 so I'm not writing it out of laziness

lol

[shut fjord]

5mod5 remainder is 0

OH

Okay sorry,

[obtuse lance]

yeah haha

[shut fjord]

When I do mod5

It applies to each term

[obtuse lance]

yup

[shut fjord]

Ahhh

[obtuse lance]

since 2 is not a perfect square mod 5

[shut fjord]

Can you elaborate on this? I am fairly new to modular arithmetic

[obtuse lance]

(the only squares are 1 and 4)

sure what in particular

[shut fjord]

Is it like any other operation?

The mod operation

Like I know what it returns, but in context of how it affects an ENTIRE equation

That’s where I’m a bit confused

[obtuse lance]

basically it takes any integer and makes it some number from the set 0,1,2,3,4

you can always add or subtract a multiple of 5 to get one of these representatives

[shut fjord]

Yeah because it wrap around once it goes above that

[obtuse lance]

you can think of the equation as just having numbers plugged into it

[shut fjord]

But I guess what I’m specifically asking is

When I use mod5

Is it like with distributive property?

[obtuse lance]

no not really

[shut fjord]

Like I distribute it to each term of the equation like if I am multiplying by a term or dividing by one

[obtuse lance]

think of it as mapping every integer to one of those representatives

[coral raven]

a%5 + b%5 + c%5 = (a+b+c)%5

[obtuse lance]

like suppose you have integers x,y then the mod operation is doing f(x+y) = f(x)+f(y) and also f(xy)=f(x)f(y)

f(x)= x mod 5

[shut fjord]

So mod is just a function mapping

[obtuse lance]

from the integers with their addition and multiplication to the set {0,1,2,3,4} with this addition and multiplication

[shut fjord]

Thanks a lot for the clarification

I went with a proof by cases within my proof of contradiction, showing each case for 0 through 4 and how all the integers will be mapped to that set, showing that its not possible for there to be a solution

I was thinking of using a bijection method for this question here, but I am uncertain of what I should set my variables to. I was going to initially set a and b to the entire GCD but that would mask away its functionality.

Would letting a = x+y and b = y (don’t have to necessarily let b = y) make my life easier in proving the 1 to 1 correspondence of both of these gcd functions?

I don’t think substitution of any sorts would help out at this point tbh

[scenic folio]

Hi, I have a question, I have to prove that (~p v ~q) is equivalent to (p ^ q ^ r). Is there someone who knows how?

[pale epoch]

make a truth table

[scenic folio]

by doing that they end up being very different because of the difference in propositions

[pale epoch]

turns out they are not equivalent then

[shut kindle]

Can someone please recommend to me a very good book for discrete mathematics filled only with exercises and solutions, which could garantuee to pass the finals?

[unreal stump]

Get Donald Knuth's book and just do the exercises

:)

[languid cradle]

@balmy cedar so D seems to be the liar then?

as in, the A-B-F-D 4 cycle shouldnt exist, since theres no chord and D is only connected to A and F by its testimony

and the A-E-D-C can be fixed by having D actually see A and E there, instead of A and F

[shell wadi]

hey can anyone help me with a question ?

8c) I believe the answer is {x (- Q| 0 < x < 1/infinty}

[shell wadi]

nvm I got it Finally

[errant bear]

what was your answer

[analog sonnet]

$\varnothing$

[vital dew]

(R/I)/(J/I) S + F bending PhD

[errant bear]

i wasnt asking u..

weeb

[tepid aspen]

woah chill

[errant bear]

[balmy cedar]

@languid cradle Yes, this was the answer I got to. Of course I can't guarantee that it's right

[languid cradle]

No worries !

Can u go more into detail why there has to be a chord between a 4 cycle

just for my own understanding

the problem itself is not for a grade

I just wanted to wrap my head around it

[balmy cedar]

Let's take the cycle A-E-C-D-A

Assume A and C were not there at the same time

Then there's a time gap between A and C's visits

But clearly both E and D's visits must fill that time gap

[languid cradle]

right

oh yet D and E don’t see each other?

[balmy cedar]

So E and D must've been there at the same time, and by the rule in the exercise there should have been an edge between them

[languid cradle]

ok that makes perfect sense actually

[balmy cedar]

On the other hand, if E and D weren't there at the same time, the same argument shows that there should be an edge between A and C

So at least one of the edges E-D and A-C should be there

But the exercise was quite hard, and maybe there is some easier argument to deduce the answert

[languid cradle]

no that seems about right I think

given the difficulty of the problem we went over in class

before this one

[balmy cedar]

Ah okay, but is it a combinatorics course, graph theory course or what?

Not that it matters, I was just curious

[languid cradle]

bit of both

but it’s only been a week

lol

[balmy cedar]

Ah okay, pretty hard exercises you get then lol

[languid cradle]

yeah it wasn’t exactly for a grade, I just wanted to get my head around

it

[solid garden]

could i get some help with proofs?

[unreal stump]

idk what's the point of asking that, when no is not an option

[errant bear]

no

[solid garden]

Oh right I thought i sent the image already

so thats the question

basically i understand its asking

for all x, y that are elements of R there exists z which is an element of R so that z = x/y. You have to find whether this is true or false.

i believe its true but im not sure where to go with it

just learned this

[unreal stump]

do you know ratio of 2 real numbers is real?

[solid garden]

yeah

[unreal stump]

That's it

[solid garden]

yeah i understand that, but im having trouble with phrasing that with the specific language which im guessing proofs used

use*

[unreal stump]

ratio of 2 real numbers is real

Therefore x/y=z is a real number

[solid garden]

Thank you!

[gritty crescent]

No

Hold up

[last timber]

x/0=?

[gritty crescent]

Nothing prevents y=0

[unreal stump]

mb

That's wrong

[last timber]

x=y=0?

[solid garden]

Hmm

Do we say it’s an exception?

[gritty crescent]

No

The statement fails

[last timber]

we say it is counterexample

[gritty crescent]

Since the quantifier makes the claim for all real x and y.

[solid garden]

I think this is okay?

[last timber]

x=y=0 is overkill here

but yes

[solid garden]

Great, I’ll fix that and thanks for the help! There’s a second part to this question which I think I can do

[solid garden]

So I’m not really sure how to find this negation statement

Luckily I figured out all the other problems

[last timber]

negation of "for all x P(x)" is "exists x such that not P(x)"

and negation of "exists x such that P(x)" is "for all x not P(x)"

and nested quantifiers can be splti

like "for all x and y P(x,y)" is like "for all x H(x,y)" where H(x,y) is "for all y P(x,y)"

[solid garden]

That makes sense

So like this?

∃ x, y ∈ R ∀ z s.t.z ≠ x/y
This statement says that there exists x and y in the set of real numbers for all z in the set of real numbers such that z is not equal to x/y.

[last timber]

ye

but without s.t

i mean it would be properly worded then like "exist x and y such that for all z, z != x/y"

[solid garden]

Oh I see

[hardy quartz]

hello, i am currently taking a discrete maths course and i am hella confused by what they are teaching me

can I post what I have done in one of my answers and guide me to the right direction thank you

[amber prism]

dont ask to ask, just ask

[hardy quartz]

so I have these 2 questions

i solved question 2 this way

however I understand that I might have made a mistake some where in there

when i plug in 1 for n i get a totally different answer compared to what i would get if i plug in the first equation

so if i plug 1 into my equation, i get 2/3 - 1/3

which is 1/3 when the answer for n = 1 should be 2/3

i have another method I can use which is divide the difference between the 2 equations

however that confused me greatly.

[last timber]

@hardy quartz you can see that you can actually split (n+1)/3^n into two parts

n/3^n + 1/3^n

and 1/3^n is just geometric series

[hardy quartz]

the fraction rule right ?

thats what i did

if you see my answer on top there i already did that

[last timber]

ok so look

i mean

[hardy quartz]

i was thinking maybe i can do ((n+1)/3 ^n) / (n / 3^n-1)

[last timber]

please parenthesise it properly

[hardy quartz]

sorry about that

so i would get (3^n-1)(2+1) / (3^2)(2)

[vital dew]

Commander Vimes

[last timber]

i mean you are on right track

so look

[vital dew]

Commander Vimes

Commander Vimes