discrete-math

[sour arrow]

No not really haha

Moving the parenthesis isn't really going any good direction though

[lucid marlin]

Thanks, I didn't know what was "allowed" here, but division where c=/=0 totally makes sense and is what i wanted to do but wasnt sure if you were allowed to

additional question, what are the algebra steps to show dividing by d on both sides of the inequality of the expression: a-d * floor(a/d) >= d is a/d - floor(a/d) >= 1 ? this is basic but i'm not seeing it

[sour arrow]

a - dx = d
Divide both sides by d
a/d - x = 1

That is, every term gets divided by d

[lucid marlin]

i'm kind of confused: how do i group the terms? (a - d) * (a/d) >= (d) and then do (a-d)/d * (a/d)/d >= (d)/d ?

(a/d)/d = (a/d^2) no?

[sour arrow]

Is it (a - d)x = d? Then what you said doesn't follow

[lucid marlin]

red arrow

[sour arrow]

So it isn't lol

Just take x to be floor(a/b)
a - dx = d
Divide both sides by d
a/d - x = 1

[lucid marlin]

this is how I am now seeing it: (a) - d(a/d) >= d -> (a)/d - (a)/d >= (d)/d -- but thats obvs wrong so not seeing where it is wrong

because d(a/d) = a

[sour arrow]

You are using (a/d) where it is actually floor(a/d)

Take x to be floor(a/b)
a - dx = d
Divide both sides by d
a/d - x = 1

[lucid marlin]

ooh

[sour arrow]

Note that d|a/d| ≠ a

[lucid marlin]

that debugged my misconception

thank you

i'm really close to understanding this proof but have 2 questions. 1) why are you allowed to set a = d * floor(a/d) + (a-d * floor(a/d)) --- initially I thought the d * floor (a/d) cancelled out and you get that expression had various cancellations so it'd be a = expression = a, but now i see that isn't correct, so wondering why you can say: a = d * floor(a/d) + (a-d * floor(a/d))

for : show that if a is an integer and d is an integer greater than 1, then the quotient and remainder obtained when a is divided by d are ⌊a/d⌋ and a − d⌊a/d⌋, respectively.

[sour arrow]

Your first part is correct. That does cancel

[lucid marlin]

2. once you have 0 <= a − d⌊a/d⌋ < d and a = d⌊a/d⌋ + a - d⌊a/d⌋, then how do can you apply uniqueness to know this shows those are your q and r, i can see you proved r=a - d⌊a/d⌋ but dont see how you get q= d⌊a/d⌋

[sour arrow]

a = dx + (a - dx)

No matter what x is

[lucid marlin]

ah i see!

you proved this is your r, because you bounded it by that inequality, but how do you know that is your q?

or, rather i am assuming you know this is your r, because of that inequality

[sour arrow]

a = dx + (a - dx)
Is in the form
a = dq + r

So from that, x and a - dx are good canadates to be the quotient and remainder. Most of this proof is just showing that they're each within the bounds set by the division algorithm

Only x = floor(a/b) ends up working here

[lucid marlin]

so basically to prove its the q and r when its in the form of a = dq + r: you need to show r satisfies 0<=r<d

and if r satisfies that, then due to uniqueness you know thats the q and r you needed

?

once you get 0<=r<d you got the q?

[sour arrow]

It also needs q ≥ 0, which they seem to be ignoring lol

Wait, no it doesn't

I'm talking shit don't mind me

[lucid marlin]

so basically the idea is: get it in the form a = dq + r, show 0 <= r < d, then you automatically get your q,r due to uniqueness ?

[sour arrow]

I suppose

[lucid marlin]

that's how the proof appears to be working (from what i can see)

[sour arrow]

If you can get that form, and 0 ≤ r < d, then you are stuck with that q and r haha

[lucid marlin]

ah i see

[sour arrow]

Can't get any other pair

[lucid marlin]

okay, i see

this is very helpful ty

[charred forge]

I cant seem to wrap my head around this problem ```For integers c, d, prove that if c is congruent to d (mod 42) or c is congruent to d (mod 24) then c is congruent to d (mod 6).

Could anyone help?

[unreal stump]

Do you understand what c is congruent to d(mod 24) means?

[charred forge]

somewhat

it means like C divided by mod24 will give you a remainder

and that will be D?

[unreal stump]

Is it understood if I say C congruent to D implies 24 divides (D-C) ?

[charred forge]

uhhh yeah kinda

[unreal stump]

So,we have 24 divides (D-C) or 42 divides (D-C)

Which means 6 divides (D-C)

[charred forge]

it would be entirely different numbers for both of those right?>

like i kinda get it

[unreal stump]

Wdym different numbers

[charred forge]

Like if we fill in 24 divides (D-C)

[unreal stump]

Let's say 24 divides (D-C)

Then a factor of 24 also divides (D-C)

[charred forge]

hmm

like my brain is trying to fill it in

for some reason

[unreal stump]

6 is a factor of 24

[charred forge]

yeah

i was thinking 6

[unreal stump]

So,6 divides D-C

[charred forge]

since 6 is a factor of 42/24/6

[unreal stump]

Yea, so either 42 divides (d-c) or 24 divides (d-c)(or both)

So 6 divides (d-c)

[charred forge]

Like

when we do it like that

my brain goes

6 | (7-1)

[unreal stump]

Sure

You can say 6|(13-7)

[charred forge]

because i know A congruent b(modM) iif m| a+b

[unreal stump]

(a-b)

Not a+b

[charred forge]

oh yeah yeah

mb

[unreal stump]

Yea,That works out ig

What's the prob?

[charred forge]

idk

just trying to write an answer

to prove that ig

[austere stirrup]

hii

hello

[tawdry pasture]

@ember obsidian

[burnt herald]

this is not reflexive and not anti symmetric

but it's also not reflexive but symmetric right?

[stray reef]

this is symmetric yes

[weary tiger]

How many number of outcomes are there in S and E?

Is |s| = 4 and |E1| = 2?

[stray reef]

no, |E1| = 1.

[weary tiger]

o right

so it's 1/4 I see

Yeah that makes sense

What does this symbol mean?

[stray reef]

product

[weary tiger]

thanks found the answer in first 10 sec of woo's video

Could someone explain this to me?

Specifically how it calculates the total number of possibilities

Why from 13 to 9?

[steady kernel]

Poor ducks 😩

[weary tiger]

xD

[steady kernel]

See this

[weary tiger]

Nevermind about the ducks

I think the one I just uploaded better explains it

it's the same concept

but I dont understand

[steady kernel]

See this

[weary tiger]

why factorials?

[steady kernel]

You have to choose from 78 animals, 12

In the first choice, you have 78 options, right?

[weary tiger]

yeah

I have 78 options

[steady kernel]

Then, you choose one animal

[weary tiger]

and then once I choose one, one option is decreased

[steady kernel]

Now you have to choose 11 from 77

But, you have 77 options

In this case

Before you had 78, for every one of those options, you have 77

That's 77 + 77 + ... + 77 (78 times)

That's it 78*77, right 9

?

[weary tiger]

🤔

Before you had 78, for every one of those options, you have 77
@steady kernel

Could your elaborate on that?

[steady kernel]

I choose one animal from 78

78 options

But

For every option

I have left 77 more

Right?

[weary tiger]

i see

so no matter what I choose I will always be remained with 77 more?

[steady kernel]

Yes, of course

You choose one animal, then, there are 77 left

[weary tiger]

i still dont get it

[steady kernel]

You have 3 numbers, {1, 2, 3} and you have to take 2. You have three options if you want to take the first

1, 2 or 3, once you take the first, you left two more, then, there are two options, given that you already take one.

If you take 1, you have two options, 2, 3
If you take 2, you have two options, 1,3
If you take 3, you have two options, 1,2

Then, you have 6 = 2*3 options

Counting order

In this case for every first option you have 2 more optiona

[weary tiger]

oh...

[steady kernel]

There are 3 possibles ways to choose the first option, then, there are 3*2 ways to choose

[weary tiger]

in other words

3!

3! ways to choose

which is 6

[steady kernel]

Well in this case is better to see it like 3*2

[weary tiger]

ok i understandd so far

[steady kernel]

Now think the same but larger

You have 78 options

Then, take one

[weary tiger]

77! ways to choose

[steady kernel]

And have 77 options for every first animak choosen

No

[weary tiger]

ok

[steady kernel]

77

The second one

The first one is 78

The second one is 77

So far we have 78*77 possible ways taking 2 animals

Taking order too

See that in this problem you have to plan the order

Do you agree that there are 78*77 possible ways to choose 2 animals from 78?

Taking order

If we don't take orden, we would count the options twice (If the order doesn't matter is the same go first to see the bear and then the gorilla than first the gorilla and then the bear)

[weary tiger]

https://www.youtube.com/watch?v=p8vIcmr_Pqo

[weary tiger]

Very stuck on this q any help would be appreciated

[pale epoch]

(a) or (b)?

[weary tiger]

A

Thank you for replying

[pale epoch]

what's (3)?

[pale epoch]

i don't think this is referring to that

anyways, this is some weird notation, do you know what you are supposed to be doing?

[weary tiger]

This is the page 29 that they are referring to as well (I think)

[pale epoch]

yeah well, you are going to have to use the properties of set operations

[weary tiger]

Oh @pale epoch (3) is the statement itself if you look at the q

[pale epoch]

mostly the first 3

ah yeah

[weary tiger]

Where do Istart sorry I’ve been stuck for a very long time

I figure I would need to use them 🤕

[pale epoch]

well, you will want to start with $(A\cap B) \cup (A\cap B^c) = \dots$

[vital dew]

Lochverstärker:

[pale epoch]

then e.g. distributivity gives you $$(A\cap B) \cup (A\cap B^c) = ((A\cap B) \cup A) \cap ((A\cap B) \cup B^c)$$

[vital dew]

Lochverstärker:

[pale epoch]

eh, wait

yeah it does

then probably use distributivity again

and use the fact that $B \subseteq A$

[vital dew]

Lochverstärker:

[pale epoch]

and at some point you will arrive at A

similar for the second claim showing that the intersection is empty

use distributivity and keep going until you arrive at the empty set

[weary tiger]

@pale epoch

Any chance I could get help on B(

[pale epoch]

oof

seems very convoluted to use (3), (4) and (5) to prove that

or well

check what properties of P you know

one of them should be that if $A$ and $B$ are disjoint, then $P(A \cup B) = P(A) + P(B)$

[vital dew]

Lochverstärker:

[pale epoch]

and you will need something else

then the idea is to write $A \cup B$ in some other way and apply those

[vital dew]

Lochverstärker:

[quartz hound]

guys

here's a very stupid question

hol up

nvm guys

i figured it out

[wild flame]

$A 4rte$

Herere $filler roll$

[weary tiger]

how can you prove that this is surjective?

[ocean turret]

If y = 3x + 4 can you derive a valid X for every y?

[weary tiger]

i was thinking about proving if it's continuous

but this is a discrete math class

and i heard that's a 2 hour proof

[sick swallow]

It is easy to prove that this is surjective u are probably overthinking

[weary tiger]

i proved that it's injective

[drifting sail]

just find $x$ in $y=3x+4$; since it's a simple affine function you can even find its inverse explicitly

[vital dew]

bastian.uwu:

bastian.uwu:

[blissful zenith]

Whats an example of a subset of R that is bounded above but has no least upper bound.
@here

[drifting sail]

(0,1)

[sour arrow]

There isn't one. That's a property of R

[drifting sail]

hold on; that has no maximum.

There isn't one. That's a property of R
yeah

[sour arrow]

There's subsets of Q that can do this though

[blissful zenith]

u sure @sour arrow

its in my textbook :/

like thats literally a q in my textbook but i just dont see how a subset of R can have no lub

@drifting sail

[sour arrow]

They're probably trying to hint at the empty set, but that is different in every book

[naive mural]

If it’s not bounded

[sour arrow]

The empty set can be given a meaningful lub, but some books choose not to.

[weary tiger]

empty set has no lub in R. it has in extended real line tho.

[drifting sail]

yes, $\sup \varnothing = -\infty$ since every extended real number is an upper bound of the empty set

[vital dew]

bastian.uwu:

[drifting sail]

They're probably trying to hint at the empty set, but that is different in every book
if the book/course doesn't work with the extended reals then it's probably this

[opal cedar]

I was hoping someone could maybe walk me through this, the answer is on Slader, but I have just absolutely no clue what's happening.

[karmic falcon]

Who can help me out with this question. I'm confused.

Let b be a positive integer. Let S = {qb + r | q,r ∈ Z and "0 <= r < b"}. Prove that for ever a ∈ S there exist unique q,r ∈ Z such that "0 <= r < b" and a = qb + r.

[unreal stump]

What have you tried?

[karmic falcon]

@unreal stump

[austere stirrup]

https://media.discordapp.net/attachments/269573202018041856/766870240218710036/unknown.png

help on yhis

this*

[robust mango]

<@&268886789983436800>

[weary tiger]

🤔

[plucky stirrup]

Can A xor B xor C xor D xor E
be rewritten as
(A xor B xor C xor D) xor E?

[stray reef]

xor is associative, yes

[neat holly]

Can someone help me find equivalencies to the limit definition?

[burnt herald]

can someone explain what is n ?

[cerulean ore]

https://stackoverflow.com/a/6110767
I am trying to learn the proof of Floyd algorithm.

(Image taken of the proof given in the above link)

I am unable to understand how the first marked paragraph leads to the conclusion that is the second marked paragraph.

Does it mean that if we move the tortoise only m steps forward, then the hare will be k steps short to the point where they met the first time? That k steps short is actually the beginning of our cycle.

[abstract ravine]

Hey o i have a question about Graph-Theory

[final linden]

@abstract ravine ask

[abstract ravine]

i asked in #help-1

sorry forgot to mention that

@final linden

[final linden]

Ok

[scarlet current]

im a bit confused

why is the intersection An instead of A1?

[granite dust]

Who’s good with measurement word problems

[stray reef]

@scarlet current intersection of what?

[scarlet current]

nvm i understood it so i removed the picture hahah

[abstract ravine]

Question: if i have to solve a graph using prims algorithm does that mean all the vertexes need to be connected?

here is my task and solution:

,rotate

[merry heron]

Quick question

Is a constant function surjective? I'm asked to prove that one isn't, but doesn't it fit the definition of a surjective function?

[pale epoch]

solve a graph @abstract ravine ?

[abstract ravine]

...

ow

Whats your question sorry?

[pale epoch]

but yes, computing a minimum spanning tree of a disconnected graph makes no sense

only connected graphs have minimum spanning trees

[abstract ravine]

No the graph to the right is the original Graph

i was supposed to make a sanning tree from the graph to the right

so my solution is the graph to the left

[pale epoch]

looks fine

[abstract ravine]

im confused

sorry

[pale epoch]

wait

[abstract ravine]

yes?

[pale epoch]

it doesnt span B

[abstract ravine]

well ye?

does it need to?

[pale epoch]

hence it's not a spanning tree?

for it to be a spanning tree, yes

[abstract ravine]

i see ...

But how do i span B then in this case?

i need to connect A with B?

[pale epoch]

choose the minimum weight edge that connect B to the tree

that's what prim's does

[abstract ravine]

Well it has to be A

Do you agree?

[pale epoch]

yes

[abstract ravine]

Can i just draw a line from A to B?

[pale epoch]

yes

@merry heron a constant function may be surjective, it may also not be

it depends on the codomain

[abstract ravine]

Final solution ?

[merry heron]

So in this case the codomain is the complex numbers except 0

[pale epoch]

that looks correct, dont forget to add the cost

[abstract ravine]

yes thank you @pale epoch

[pale epoch]

then a constant function is never surjective

[merry heron]

I'm not gonna screenshot it since it's in spanish but I can type it on latex if you want

[pale epoch]

by definition a constant function only hits a single element in the codomain

so it is surjective iff the codomain only has a single element

[merry heron]

ohh right because it's for all elements of the codomain

[merry heron]

thanks

[scarlet current]

isnt the answer for the union wrong?

shouldnt it be all integers not all real numbers?

[pale epoch]

(-i, i) is the interval of all real numbers between -i and i

excluding -i and i

[scarlet current]

oh interval

right

i thought it was the set bracket

[pale epoch]

it is not

[scarlet current]

yeah

thanks!

[hardy viper]

Question: Find the next term in 0, 1, 4, 5, 6, 9, 16, 19, 22, 29, 36, 41, 48, ...

[pale epoch]

that's ... impossible to answer

[gritty crescent]

Nothing turned up on OEIS, I'll try Wolfram now.

,w 0,1,4,5,6,9,16,19,22,29,36,41,48,...

Useless.

The squares of integers are interspersed in this sequence.

Nahh not even that 25 is missing

[hardy viper]

it's a variant of this sequence https://oeis.org/A239231, whose formula is floor((n^2+1)/3) for even and floor((n^2+3)/3) for odd (I should add that formula )

[gritty crescent]

Does this sequence have any particular significance?

[hardy viper]

the oeis sequence is max number of nonadjacent shaded cells in an nxn grid with unshaded cells connected edgewise

the sequence I'm asking is that but you can draw a loop that goes through all the unshaded cells

like

[gritty crescent]

Damn.

[abstract ravine]

Hey ehmm

so lets say i was given the word "PASS"

and i was given the question ^

the subject here is "Permutation and Combinatrics"

Now, in this case i know there are 12 different ways to write the word "PASS"

since it will be 4!/2! = 12

But i dont get the question fully

im not sure what they want

is there a way to do this without losing your mind?

<@&286206848099549185>

pls help * - *

What do you mean write them down

but dude it says order matters

wtf is order?

what

thats the question

uuuuh

But how will that change anything

PAS1S2

PAS2S1

different words?

ow shit

ye

what if the order doesnt matter

for PASS

would there be less different words?

owwwwwwww wait wait wait

So you are saying

if they ask me to do Ordered

then i dont need to do 4!/2!

if its not supposed to be ordered, then i can just do 4!/2!

5!/3!

[abstract ravine]

ok so long story short im retarded

i cant manage to write the word differently 24 times

yes

[abstract ravine]

@loud ingot challenge you to do it

[rough shard]

Is it possible to write 'the sum from 0 to n' in closed form? I prob can't send the problem here but I've found a formula for the recurrence and there is this sum in the middle, but otherwise it looks fine.

i guess i should say I've found a sort of closed formula but there is a summation

[violet kayak]

I don't really know how to tackle this

[weary tiger]

induction

[violet kayak]

I think I need to prove this with a more combinatorical approach and one with the factorial formula

ohw

oh

induction on n?

[weary tiger]

induction and combinatorial approach seems good

induction on n?
yes of course

[violet kayak]

ahh okay thx. I'll try induction first

[lyric pumice]

No induction required.

[violet kayak]

ohw huh

induction worked for me btw but how else would you do it?

besides the combinatorial approach

[lyric pumice]

You could use basic transformations.

[violet kayak]

huh?

would that be the combinatorial approach

where I have to make a bijection?

because I would also need to do it that way and don't know how to approach it

[lyric pumice]

You can separate k choose 2 into two parts by using Pascal's formula.

[sick swallow]

you can do it purely algebrically

by doing RHS=1/2(sum from 0 to n, n^2-n)

then use the formulas for sum of first n squares and sum of first n integers

which gets n(n-1)(n+1)/6 which is precisely the LHS

[violet kayak]

by doing RHS=1/2(sum from 0 to n, n^2-n)
@sick swallow how'd you get this?

[sick swallow]

n choose 2 =1/2(n(n-1))

[lyric pumice]

From there you just rearrange terms using a few additions and subtractions.

[violet kayak]

huh n choose 2 is n!/2!(n-2)!

[sick swallow]

yes which is equivalent to what i said...

[violet kayak]

oohw millenial, does that work?

oohw yeah kane, sorry I see it now

But how would you do this going from the combinatorial way?

[sick swallow]

that isnt a combinatorial argument

[violet kayak]

I mean with bijections and the other definition of n choose k

[lyric pumice]

The last term is cancelled to give 0 and you are left with ((n+1) choose 3).

[violet kayak]

huh

is that correct

[lyric pumice]

I meant this.

[violet kayak]

you took ((n+1) choose 3) out of the sum but should you not also take (n choose 3) out

ahh

[mystic moss]

okay, yeah. i think the use of pascal's identity there is neat

[lyric pumice]

The last two terms are cancelled to give 0.

[violet kayak]

huh why is that so?

I don't really see it

[lyric pumice]

The lower limit becomes k=1.

[violet kayak]

Ooh is that how sums work?

I'm not really that familiar with the properties of those yet

[lyric pumice]

When you expand with k=0, you get (1 choose 3), which is 0.

So, you can sum starting from k=1.

[violet kayak]

Ooooohhh

right

hah

that's a pretty neat and short way of proving this yeah

thx

that's a pretty neat and short way of proving this yeah

[mystic moss]

oh @violet kayak i was thinking about a combinatorial approach, tell me if this looks okay:

let's start with the RHS. so we have a line of n people

but we might not be able to consider all of the people in the line. say we can only look at the first k people in the line

out of those k people, we need to choose 2

k can be anything from 0 to n. the number of possible scenarios is counted by the RHS

[lyric pumice]

In total, basic transformations would give you something like this.

This method generalizes beautifully.

[mystic moss]

(yeah, it's the hockey stick identity, right?)

[lyric pumice]

Yes.

[mystic moss]

now look at the LHS. we now choose three numbers from 1 to n+1. the highest number of the three will be k+1 (i.e. we cut the line off at the position just before this value)

and the other two numbers will be the indices of the people that we choose from those k people

[sick swallow]

what is the point in all of those steps in that picture

all u need to say is that is telescopes

[mystic moss]

which counts exactly the same scenarios as the RHS does.

[sick swallow]

that is a nice proof

[lyric pumice]

The telescoping is clarified.

[sick swallow]

tbh it is less clear by doing that

[zenith thorn]

Sup guys I have a question and I’m not sure I’m thinking the way my professor’s questions are phrased?

At first I thought about doing a tree for part a, but if i do that, then for part b, there’s no way I could alter the graph without changing the adjacency matrix

So then my second thought was to try $C_6$

[vital dew]

Majez_tic:

[zenith thorn]

which works and for part b I got a non-complete looking bipartite graph. But it doesn’t seem satisfactory enough and I’m not sure if I’m missing something

[violet kayak]

@lyric pumice Oohw woah, it's very cool how you find such a proof in a combinatorial approach. Thank you , this has definitely helped me thinking about these kind of problems!

[lyric pumice]

@violet kayak I will leave the derivation of Pascal's rule to you.

[violet kayak]

already did that one as a previous exercise though :p

[lyric pumice]

Good.

[weary tiger]

yeah got it. Thanks

is there any theorem i need to know for this?

[delicate ridge]

nope

imagine you have a set like this

since they are disjoint and all subsets of S, then A, B and C make up a partition of a subset of S

think about what that looks like geometrically

as in, how can you turn "choose a partition of a subset of S" into "choose a partition of S"

[lyric pumice]

@weary tiger There are no special theorems required.

[neat holly]

Can someone simplify the epsilon-K definition of a limit for me?

I need to find equivalencies for it.

[lyric pumice]

Ask in #calculus.

[neat holly]

Huh. Thank you!

[scarlet current]

would the transitive closure of a transitive relation be the transitive relation?

[pale epoch]

ye

if a relation R is transitive, it's transitive closure is R

[scarlet current]

ok thanks!

[scarlet current]

would this be an acceptable lexicographical order hasse diagram for the set

[scarlet current]

if there is a set = {0}

would the power set be {{0},{empty set}} or {{0}, empty set}

[pale epoch]

the latter

[scarlet current]

ok thanks!

[pale epoch]

{0} has two subsets: {} and {0}

[scarlet current]

oh ok

[junior bridge]

Need help with a question:
Ɐ x, y ϵ ℝ, Let P be a relationship defined on ℝ such that x P y iff x + y is rational. Determine if P is transitive.

Im not sure if I solved it correctly and I feel like there is a much better way. What I've done is let a, b ϵ ℤ ϶ x + y = a/b
let c, d ϵ ℤ ϶ y + z = c/d
x + z = (a/b) + (c/d) - 2y and I then used a contradiction proof to show that that will end up in a contradiction if y is an irrational number which would imply that the x+z only works for cases where y is strictly rational. What is the correct way/better way to do this?

[stray reef]

that won't work DD

[unreal stump]

Take (√2,-√2) and (-√2,4+√2)

[stray reef]

@junior bridge are you looking to prove or disprove?

or rather, are you looking to prove that P is transitive or that P is not transitive?

[junior bridge]

the question asks me to determine if it is or isnt

[stray reef]

yeah but what's your proof aimed at?

[junior bridge]

it shouldn't be transitive i think

[stray reef]

ok

then it's better to give a concrete counterexample

such as, (π, -π) and (-π, 2+π)

0 and 2 are rational but 2+2π certainly isn't

[junior bridge]

my class didn't really cover proof by counterexample that much, that's it? I just give a counterexample and explain in what way it doesn't work?

[stray reef]

proof by counterexample is the bread and butter of shooting down false claims in math lol

counterexamples in general are very abundant in mathematics as a whole and sometimes inventing one can tell you a lot about whatever it is that you're studying

but yes transitivity can be disproved with even a single counterexample

[junior bridge]

I see, thanks

[unreal stump]

What is the axiom of choice according to your book?

[elfin egret]

I proved it from AoC to the given statement... I just have problem in assuming given statement and prove AoC

This is the definition of AoC taught to us

[hasty ibex]

Prove that if a + bare all rational,

How do I prove this using contradiction?

[unreal stump]

Just do a normal proof

((a+b)+(a+c)-(b+c))/2=a which is rational

[stray reef]

why do you need contradiction for this exactly

are you explicitly made to prove it specifically by contradiction

[hasty ibex]

I am learning contradiction and I was wondering how to prove it that way

[stray reef]

i don't think a contradiction proof will be easy here

[hasty ibex]

why we divide by 2? @unreal stump

[stray reef]

...to get a itself and not 2a perhaps

anyway, if you insist on contradiction, the case of a, b and c all irrational (one of 7 cases) is... probably gonna be tricky if not outright impossible to handle

[hasty ibex]

Oh okay! I see. I need to do subcases

Got it! Thank you for the help 😉

[elfin egret]

Can anybody help me with my question above... About axiom of choice?

[cloud crest]

Need some help! are the pigeonholes all three sides AB, BC, AND CA and the pigeons are triangle ABC

[pallid lintel]

i havn't come across automorphic group of a graph before, is that just a group of permutations on vertices of H where the permutation is symmetric to H

wasn't sure, looked it up on wiki

So if i switch the top two vertices in this 5 vertex graph with bottom 2, its in the automorphic group however if i switch top left with far right, that wouldn't be?

[pale epoch]

automorphism group but sure

the automorphism group of a graph G is the set of all isomorphisms G -> G with function composition as group operation

[pallid lintel]

the size of the automorphic group of that graph would just be 2 right?

thanks

[pale epoch]

no, it's bigger

the far right vertex has to be fixed, it's two neighbours may be swapped and the remaining two may be swapped as well

[wild dome]

Is discrete math easy ?

[pale epoch]

what's discrete math?

[wild dome]

a game

[quaint whale]

@pallid lintel in this case its easier to look at the dual of this graph...which has far less edges...hence easier to see the symmetries...i hope you can see why automorphism group of a simple graph is isomorohic to the automorphism group of its dual...

[pallid lintel]

it is size 6

[quaint whale]

Also this graph has something special...there are two vertices of degree 3, two of degree 4 and one vertex of degree two...so any automophism preserves the degrees of vertices...you can also figure it out using this...

So i guess it should have four symmetries... you can switch the degree three vertices or the degree four vertices...the deg 2 vertex will be fixed

[pallid lintel]

that doesnt sound right. why can i switch degree four with degree 3? then the degree 3 one is adjacent to the fixed vertex and it is not an isomorphism

oh nvm think i misread

[quaint whale]

The dual graph will be • •
•---•---• and this also has four symmetries...interchange the points or flip the line...

[deep portal]

or maybe this is a better channel. refresh my memory. What;s the difference between necessary and sufficient?

[shrewd spindle]

In this problem: https://math.stackexchange.com/questions/1715246/eight-digit-number-is-formed-using-all-the-digits-1-1-2-2-3-3-4-5

can someone explain why you divide 7! by 2!

like 7!/(2!*2!)

i understand it's supposed to represent each repeating digit

but why does a repeating digit turn into a factorial

in the first explanation of part a someone does that logic

[lyric pumice]

@floral field Yes.

[versed summit]

Hey guys, I'm having a real hard time trying to figure out how to solve something that seems so simple

31x ≡ 2 mod 16

Trying to solve for x. Apparently the correct answer is x = 14 mod 16, but I have no idea how to get that, or why.

[robust light]

can someone walk me through a discrete math problem?

i don't really get recurrence relations

[weary tiger]

so guys
I am in a course called performance analysis of software systems
its a fourth year software engineering math course
Its basically stats
i was wondering if anyone knew any practical examples of dtmc (discrete time markov chain)
They are not only used in software engineering/ computer science applications
they are also used in sports, genetics, population models, economics

[errant bear]

you need to find the multiplicative inverse of 31 mod 16 @versed summit

[pallid lintel]

has anyone here done this course? https://ocw.mit.edu/courses/mathematics/18-217-graph-theory-and-additive-combinatorics-fall-2019/index.htm. I got to lecture 4 and could no longer follow because i don't understand the algebra. (i have studied up to elementry rings, polynomial rings, ect. no galois theory yet).

[compact onyx]

are there any known lower bounds for the cardinality of the union of k sets?

[proven shard]

Yes

0

[versed granite]

hey! could anyone tell me, what this acutally means? so An ={0,1,...,n} what is A1 or A2?
My friend has the answer for this question is N but i am not sure.

[pale epoch]

$A_1 = {0, 1}$, $A_2 = {0, 1, 2}$, etc.

[vital dew]

Lochverstärker:

[pale epoch]

you are right to be skeptical.

[versed granite]

so the 'schnitt' would bhe {0,1}?

sry dont know the english expression

[pale epoch]

indeed

[versed granite]

for that

[pale epoch]

intersection

[versed granite]

ty

[karmic nymph]

in combinatorial, what does it mean when order doesnt matter and when it does matter?

<@&286206848099549185>

[last sigil]

look up the difference between a permutation and combination

[karmic nymph]

so permutations we care about ordering

and in combinations we dont

[last sigil]

yes

try some problems to get an idea of when we do/do not care

[karmic nymph]

that doesnt answer my question

:/

Example: we have 6 people and we need to choose 3 different people to stand in a line

The different number of combinations for the line up would be 6 x 5 x 4 right

[last sigil]

yes, but here order might matter

[karmic nymph]

what does it mean order matters

[last sigil]

let the 6 people be a, b, c, d, e, f

the first letter is the first in line

2nd letter is second in line, etc.

is a b c the same as a c b in a line?

[karmic nymph]

what do you mean by "same as"

[last sigil]

This depends if we consider the position of the student as a factor in the line

For an example of a combination, think of it like selecting a group of 3 students out of 6

There is no order to the students, so we use combinations

If we were to select 3 students to give 1st, 2nd, and 3rd medals to out of 6 students, we have "order", so we use permutations

[karmic nymph]

okk

So

when order doesnt matter, we use combinations

and permutations otherwise

[last sigil]

yes

okay, question!

is a computer password a permutation or combination?

[karmic nymph]

permutation

[last sigil]

yes, cause order matters

[karmic nymph]

yep

[last sigil]

how about selecting one type of bread and one type of meat for a sandwich

[karmic nymph]

combination

[last sigil]

yes

[karmic nymph]

because i can choose meat first or the bread first, doesnt matter

[last sigil]

[karmic nymph]

nice i think i got it for now

thank you

[short hamlet]

how do i prove this using inductio n

induction

[karmic nymph]

is it saying that there are 8 differents bag of 6 donuts?

[glass condor]

I think it's saying that there's 8 kinds of donuts, and you need to choose 6 donuts total (any mix of kinds).

[neat holly]

Can anyone help me start this off? I plan on starting by defining the nonempty closed intervals as subintervals of I_1.

[burnt herald]

Consider aRb, and R = {}.

Is R reflexive, transitive, symmetric, anti-symmetric?

[robust mango]

@neat holly Have you studied nested intervals?

[neat holly]

It's 2.5 in Introduction to Real Analysis 4e, the book we use for this class.

[robust mango]

have u studied it?

[latent patrol]

anyone know how to do this pigeonhole problem?

[neat holly]

Yeah, we went over it.

I'm sure I can get some of the fundamental things of nested intervals down on this proof, though I don't want to miss important details.

[tame hound]

hi

Can anyone help me real quick? 😦

i keep being stuck on the cardinality of intersections

it doesn't make any sense to me and im about to give up but my midterm is tomorrow.

If anyone could help me with this i would greatly appriciate it

It is really confusing since n(A ∪ B) = n(A) + n(B) – n(A ∩ B). However n(A ∩ B) = n(A) + n(B) – n(A ∪ B), but when i am given an example, i only get (A) (B) where the elements are undefined

That's what i don't get at all

[drifting sail]

but when i am given an example, i only get (A) (B) where the elements are undefined
I don't get what you mean by this

anyhow it's good to e.g. draw a picture to see why n(A ∪ B) = n(A) + n(B) – n(A ∩ B) holds

(when A and B are finite that is)

[tame hound]

i am given a set a that says that the cardinality of A is 5 and the cardinality of B is 6

find cardinality A union B

[drifting sail]

you're right, you can't find n(A ∪ B) without any other information (you sure there isn't any?)

you could get bounds though

as in, n(A ∪ B) must have at least x elements and at most y.

[tame hound]

i am positive

the professor didn't give anything

he just said that we need to add - a intersection of B

which we can't since we don't no A union B

makes absolutely no sense

[drifting sail]

yeah lol

guess you could just rewrite n(A ∪ B) = n(A) + n(B) – n(A ∩ B)

except you replace n(A) and n(B) by their respective values

that's as far as you can get for an equality

[tame hound]

i guess that's all i can do

[drifting sail]

you could get bounds though
since you aren't expected to do this presumably (though it's still a good exercise)

[tame hound]

but if he gives the value of a union b i will know what to do

and also one more thing, n(A ∪ B) = n(A) + n(B) – n(A ∩ B) is also used to find the total numbers of possible ways to perform a given amount of task but without repetitions right?

or do i use the formula of n(A ∩ B) instead?

[drifting sail]

and also one more thing, n(A ∪ B) = n(A) + n(B) – n(A ∩ B) is also used to find the total numbers of possible ways to perform a given amount of task but without repetitions right?
if you see A and B as sets of possible tasks then yes

[tame hound]

got it thank you

wait

so this is what im supposed to do if i am not given the union's cardinality?

wouldn't that result in a 0 as a result?

[drifting sail]

no, unless |A|=|B|=0

[tame hound]

gotcha

[frail agate]

can someone explain how to prove this?

i honestly have no idea how to do this at all

[unreal stump]

You could just write the expansion of 7^n-1

[frail agate]

nevermind, i figured it out. i was not thinking in the right way for this.

[safe scroll]

how would you do this

using direct proof

[stray reef]

may i suggest factoring x^2 - 7x + 12?

[safe scroll]

right

[stray reef]

you might find it easier to think about once you do that

[safe scroll]

(x-3)(x-4)

wait one sec

[stray reef]

yeah

that's the correct factorization

[safe scroll]

ya lmao

oh I see

actually

ok ok

thanks man

[weary tiger]

weird, i thought u solve these with the combinations/permutations thing

oh nvm

thats for finding out the number of solutions

[stray reef]

these = ?

[safe scroll]

wait hold on

if I do that

nvm

ok ok

[pallid lintel]

are there many variations of the pigeonhole principle? Only one's i've found so far is infinite pigeonhole principle. (jam infinite balls into a draw if finite draws and infinite balls). and strong pigeonhole.

just wondering, because so many proofs in math come from pigeonhole

[sand turret]

@pallid lintel I know of Generalised Pigeonhole principle

[weary tiger]

Specialized Pigeonhole Principle

most famously the Jacobin Pigeonhole Principle

and the Homing Pigeonhole Principle

and the English Carrier Pigeonhole Principle

[unreal stump]

You forgot german nun pigeon principle

[weary tiger]

https://upload.wikimedia.org/wikipedia/commons/0/0a/Deutsche_Nönnchen.jpg

[weary tiger]

Is there a mathematical formula to solve this problem ?
If I have a triangle of point N*N, how many path are there to go from the point at the very top left to the point at the bottom right.
The only condition is I have only two movements possibilities...
I can go down ⬇️ or go right ➡️

+  <----- Start
+ +
+ + +
+ + + +  <----- End

so ur talking about a right-angle triangle, of height and base N.

u can probably make a decision tree and see a few results and find a general formula

Ok, but is there a general formula made on the past, or Something like that ?

generally, u can find a general formula, then find out someone made it in the past

Okay, i m going to check that

like, do induction

Ok, but what is induction ?

the thing i xplained, u do the first few results

then assume the same pattern applies for the rest

Ok, but in this case, we must assume something

yea, u see the pattern

Ok

and u "assume" it applies for the rest

Ok

[brave cedar]

Do I post Theory of Computation problems here?

Please someone help me

[unreal stump]

Functions?

[weary tiger]

"Theory of Computation"

dfa

u just gotta convert it to a regular expression

[brave cedar]

u just gotta convert it to a regular expression
@weary tiger yeah

@weary tiger you know how to do it?

[weary tiger]

i forgot

i watched a youtube video on it by some indian guy a while back

[brave cedar]

Oh if anyone else know it, then please solve it

[weary tiger]

if u just wanna "solve it", u can use an online fsa to regex converter if u only want the answer

[latent patrol]

does anyone know how to approach this pigeonhole problem?

[unreal stump]

The problem?

[latent patrol]

I was thinking of making the 12 positions the pigeons and the 30 sums they can make up the holes

but that doesnt work

[naive mural]

Is it meant to be solved by pigeon hole or are you assuming that

[latent patrol]

it is meant to be solved with pigeonhole

[naive mural]

Simple

[weary tiger]

no idea how to do this

like is there a good approach to solving these questions?

[naive mural]

If you have a palindrome you slap on the same number on both ends and you have another one

But of length 2 more

And you could either do both 0’s or both 1’s

[weary tiger]

but how is the answer d

[naive mural]

Because of what I said

[weary tiger]

but you said of length 2 more

doesn't that imply + 2

[naive mural]

No

[weary tiger]

then?

can you give me an example please

[naive mural]

101

You can get 11011

Or 01010

So each one of length 3 gives 2 of length 5

[weary tiger]

is P_3 = 101?

ok i get it now

thanks

b*a(bb*a)*a(b+a(bb*a)*a)*

[latent patrol]

is it possible that my question is unprovable by pigeonhole?

[tame hound]

Can anyone possiblly explain me this?

Really confused on that orn

[pale epoch]

what confuses you

[tame hound]

How to find set S

I don’t understand where i can get y from

[pale epoch]

just take an element of the set, lets say start with 5

and check if 5S5

then if 5S6

and so on

[tame hound]

5S5 = 1/2

[pale epoch]

no

S is a relation

either 5S5 is true or it is false

[tame hound]

Ah ok then it is false

[pale epoch]

why?

[tame hound]

Because (5-5)/2

[pale epoch]

what is that supposed to mean?

[tame hound]

Uhm

Im not sure how to explain that. Sorry

[pale epoch]

it's hard to help if i don't understand you

anyways, "x | y" stands for "x divides y"

you should look it up in your book/script

also look up the definition of what a relation is while you are at it

[tame hound]

I thought that 2|(x-y) would mean X times unknown(c) = (X -y)

[pale epoch]

it means 2 divides x-y

[tame hound]

Wait no

Yeah

[pale epoch]

or in other words, that x-y = 2*k for some k

or in yet other words x-y is even

[tame hound]

Ok?

I have to find k?

So i can put up the set S?

?

[pale epoch]

you have to find out if x-y is divisible by 2

for all pairs (x, y) with x, y in A

but first you should study

[tame hound]

Ok got it. Thatnks for trying to help

Can i also ask help for anyother concept or nah?

[unreal stump]

Sure

[tame hound]

Thank you. This one is also a but tricky for me. How can i prove algebraically that (n r) = ( n n - r)

[unreal stump]

God?

[tame hound]

What?

[unreal stump]

Sorry,you meant nCr,my bad

[tame hound]

Hold ill find a picture of it for ya

This

[pale epoch]

gcd = God proven

[tame hound]

for interers n and r where 0 inferior equal r inferior equal n

[unreal stump]

Just expand both expressions

[pale epoch]

how did you define $\binom{n}{r}$

[tame hound]

What is that?

[pale epoch]

did the bot die

[vital dew]

Lochverstärker:

[pale epoch]

it's the (n r) thing in your pic

[ocean turret]

It's dead all the time

[pale epoch]

there it goes

[unreal stump]

Why do bots die?

[pale epoch]

do they dream of electric sheep?

anyways, this is called binomial coefficient

[tame hound]

Hold on im writting it down to show you since idk how to use the bot

[pale epoch]

ye, that's fine

but then it's probably defined by $\frac{n!}{r!(n-r)!}$

come on bot, you can do it

[unreal stump]

Bot is dead

And we killed it

[vital dew]

Lochverstärker:

[tame hound]

I suppose that’s what you mean

[pale epoch]

wait what

your picture does not answer the question

[tame hound]

Didn’t you wanted the formula? Im confused

[pale epoch]

i wanted to know what $\binom{n}{r}$ means

as there are multiple ways to define it

you don't need any fancy formula to answer this question

[vital dew]

Lochverstärker:

[pale epoch]

but like, that is the first thing you should ask yourself when reading this question: what is $\binom{n}{r}$ maybe try some example like $\binom{5}{3}$

and your picture does not answer how i would actually compute \binom{5}{3}

[vital dew]

Lochverstärker:

[tame hound]

I think it’s used to find the number of ways to find all the r elemts that can be selected from a set of n itens

?

[pale epoch]

something like that, yes

it's the number of subsets with cardinality r in a set of n elements

but you should check if you defined it that way, or if you instead defined $\binom{n}{r} = \frac{n!}{r!(n-r)!}$

or if that is a theorem that you did

because you should use the latter to prove that

[vital dew]

Lochverstärker:

[tame hound]

But how does that relate to making it equal to ( n n -r)?

[pale epoch]

you do the same thing to that

you get two fractions that you can algebraically manipulate

until you see that they are equal

[tame hound]

Alright

[boreal widget]

Anyone know how to solve a single degree recurrence relation?

[unreal stump]

Induction

If that doesn't work,well that's why the rest of theory exists

[boreal widget]

Ok well specifically could you help me solve an=an−1+n with initial term a0=4

[honest barn]

What

This is just a_n = 4 + (n)(n+1)/2

Since it’s a_n = 4 + sum_1^n k

[harsh warren]

hey everyone quick question relating to graph theory: does every graph contain a matching?

[mystic moss]

yes

[harsh warren]

so the empty set is a valid matching?

[mystic moss]

yes

[harsh warren]

so with that can i also assume that every graph has a maximal and maximum matching?

[mystic moss]

yeah, not necessarily unique

[harsh warren]

great, thank you!

[harsh warren]

For every graph G without perfect matching and every vertex v of G there is a
maximum matching M of G such that v is M-unsaturated.

can i prove this just by using the definition of perfect matching?

[mystic moss]

what is M-unsaturation?

[harsh warren]

there is no edge in the matching M that is incident to v

[mystic moss]

i think this is untrue. say you had a graph that was a star, with one vertex as a hub

like simply a line with three vertices

every maximum matching will have the center vertex

(and this is not a perfect matching)

[harsh warren]

oooooooo

that is true

good catch, let me soak this in for a bit

thanks again

[safe scroll]

does anyone know how to do this

the way I started is to rearrange and I got

$4x^2-4x+1\geq0$

[vital dew]

The "Great" King:

[safe scroll]

which I could then convert to

[fast temple]

might be a bit unrelated, this is boolean algebra, but any idea how they got from x + x'y to (x + x')(x + y) ?

[safe scroll]

$(2x-1)^2\geq0$

[gritty crescent]

Uh @safe scroll , I don't think this question is suited to this channel. Consider asking in #precalculus or #prealg-and-algebra , or any unoccupied question channel.

[vital dew]

The "Great" King:

[safe scroll]

that is a proof though?

for my discrete class

how do you get from on to the other

[gritty crescent]

Oh, alright, I just thought the nature of this problem is better suited to those channels.

[bitter moss]

well for smaller and smaller x values it gets bigger and bigger than four @safe scroll

[safe scroll]

right but how do I prove that if x is between 0 and 1 then that other term is greater than 4

because if x <0 or x>1 then the answer is <4

[bitter moss]

you found that at x=1/2 its equal to 4. going below that x value but not equal to 0 gives you a greater value than 4

[fast temple]

is there a better channel for my question?

oh crap I should probably ask in the computer science server, sorry everyone.

[safe scroll]

no that is a math question @fast temple

wait @bitter moss

[bitter moss]

that just looks like calculus @fast temple

[safe scroll]

no that is boolean algebra

I think this is the correct channel

to ask it in

[bitter moss]

ight

[fast temple]

it's math but I think more people would be able to help there

[safe scroll]

and @earnest sedge they distributed

[fast temple]

it's from my digital design textbook

[safe scroll]

since I assume + is AND and multiplication is OR

so x AND (!x OR y) = (x AND !x) or (x AND y)

also @bitter moss I get x > 1/2

you are right

but how does that imply that 0<x<1

[bitter moss]

well at x=1 we get 0 in the denominator and thats a no no

[safe scroll]

lmao

ya

but how do I prove this

[bitter moss]

nvm at both cases you get 1/0

wym how do u prove it

[safe scroll]

like is there a way to rearrange 1/(x(1-x)) >= 4 into 0<x<1

I am so lost rn

[carmine grove]

What do we do if:

• order matters and there's no repetition
• order doesn't matter and there's no repetition
• order matters and there's repetition (order of repetition doesn't matter)
• order doesn't matter and there's repetition (order of repetition doesn't matter)
• order matters and there's repetition (order of repetition matters)
• order doesn't matter and there's repetition (order of repetition matters)

I just started permutations and combinations so I want to know about all the possible states (?)

Combinatorics is discrete math right?

[deep portal]

Permutations
Order matters and repetition is Allowed is n^r

Order matters and repetition not allowed is

n!/(n-r)!

Combinations

Order doesn't matter and repetition not allowed

n!/(r!(n-r)!)

And combination with repetition

(r+n-1)!/(r!(n-1)!

That last one is he one I never know how to use. But is this what you're meaning?

[brave lava]

can anyone check these if they make sense

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

[karmic nymph]

Could someone help me out on part D please

so we need to select 6 from a possible set of 8 donuts

im aware that 8 different choices will net me atleast two varieties

im thinking it should be 330 + 8 :/

[safe scroll]

@karmic nymph I think the right way to do this is

how many ways are there total

now how many of those ways are there not 2 varieties

well that is when they are all the same variety

there are 8 possible ways

8^6

-8

262136

[karmic nymph]

wot

[safe scroll]

?

[karmic nymph]

i dont think theres 8^6 different ways

[safe scroll]

actually

you are right

since it is 8 choose 6

right

[karmic nymph]

yes

[safe scroll]

hold on

that doesn't seem right either

wait let me think for a second

[karmic nymph]

sure

[unique herald]

What does this mean?

[safe scroll]

ok wait

@karmic nymph I think the way to do it is

6+8-1 choose 6

which is 1716

-8

would be

1708

[karmic nymph]

oh

um

why did u minus 8 ?

[safe scroll]

well 1716 are the total number of bags right

all but 8 of them have 2 types

there are 8 bags of donuts

[karmic nymph]

ok i see

[safe scroll]

where all 6 of them are the same

[brave lava]

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

<@&286206848099549185>

[karmic nymph]

@safe scroll

[chrome gull]

What does this mean?
@unique herald It means that the values of x are discrete, they take values 0,1,2,3,4,... instead of any real number.

[safe scroll]

oh shoot

let me think about that

I think you just do it by parts lmao

so no jelly filled

1 jelly filled

2 jelly filled

[karmic nymph]

yeah

so 3+8-1C3

take that away from (c) ?

[safe scroll]

no wait

(n+r-1)Cr