discrete-math

[weary tiger]

$\in$

[vital dew]

§`

[brave rock]

Of course, the set inclusion symbol is what anyone means when they say that

[weary tiger]

is it because i didnt say {b} is in A

[brave rock]

But this is nonsense, because it is even less meaningful to say that b is a subset of A.

And in general it is still not true that {b} is a subset of A.

[weary tiger]

because we dont know if b is in A

but since {{b}} is a subset of A

then {b} is in A

[brave rock]

And?

[weary tiger]

is this what ur trying to say

[brave rock]

That is indeed what I said

[weary tiger]

ok thanks

i'll make sure i use the {} next time

this got burried, if anyone could help, thanks in advance.

nvm solved

[brave rock]

Yes.

[shut bolt]

would this statement entail WOP?

[tidal tulip]

great, thanks!

[brave rock]

This is the statement of the W.O.P. that I am used to.

[tidal tulip]

what does W.O.P mean?

[shut bolt]

would u say its equivalent or entailment?

[brave rock]

I was replying to Danvs, not you

[tidal tulip]

ok, i thought it was to me sry

[brave rock]

If it is the statement itself, of course it is equivalent.

I don't know what statement of the principle you've been given.

[shut bolt]

but then how is it any different to this statement?

[brave rock]

You can come up with sets that are not N that have this property but do not have the well-ordering property. It is a good exercise to try to do so.

Hint: choose any set without the well-ordering property.

[shut bolt]

but doesnt it have to be sets that are N

[brave rock]

This will tell you why these statements are necessarily different

I don't know how to better explain that this statement and the w.o.p. are just different.

Furthermore, no – there are many ordered sets that are not N that have the well-ordering property.

[brave rock]

A comment on this: because both statements are true in the naturals, they are of course equivalent in the naturals—true is equivalent to true! In order to show that they are logically distinct we are forced to find contrary examples, which must of course be something other than the naturals.

[shut bolt]

oh i see

[dry raven]

part of a study guide I think I understand these concepts and got them right. Could anyone lmk if they think I should double check one of em or try to lead me in right direction?

[weary tiger]

how from the first comes the second line

[elder berry]

Just a contraposition of the two statements

recall when $P \to Q ~\equiv~ \neg Q \to \neg P$

texit ded

[weary tiger]

this statement is right/

ok wait I think I got it

this is the full solution btw

[stuck yoke]

someone can explain what to do in q1 and q2 ?

[vale cairn]

Blur 100

[chrome sand]

Hi guys can i write this

as

i should simplfy

can i solve it like this

[fickle meteor]

Does anyone know any good websites with counting practice problems?

[covert bolt]

Hello, I don't really understand the solution to b

In particular why the negative of both r was taken

[covert bolt]

And why the negative of b was also taken

Ok I think at this rate something is very wrong with the solution 💀

[worldly berry]

I need help with what this means.... I don't understand how i got that combinatorial formula. Anyone who knows it, please help

[haughty garden]

,rotate

[dry raven]

does this seem right? its for a test study guide sop tryna get it right

[stray reef]

@dry raven answer does not match mine. show your work.

[dry raven]

Wait I actually got 136 after redoing it

[stray reef]

that still does not match mine and i would still like to see your work.

the number is less important than the work going into it...

[dry raven]

Ok one sec

The maximum is realized by the array [1, 19, 18, ..., 15, 7, 14, 13, ..., 8, 6, 5, ..., 2, 20]. First we ignore slots x1, x7, and x20, and deal with the worst case of 17 elements-- this is 17(8)=136. Next we deal with the other slots-- x1 and x20 contribute nothing while x7 contributes 5

This is kinda my thought behind it

[stray reef]

hold on

i don't think 7 and 16 are in place in that array

or maybe we have different definitions of what it means to be in place

but the way i read it, x7 being in place means that all elements less than x7 are to its left and all those greater than x7 are to its right

[dry raven]

I get what you’re saying now

One sec I’m trying to figure it out too

[chrome tree]

NEED HELP FOR THIS:
The proportions of the other ingredients indicate that there is between 4% and 6% breadcrumbs in it, so let's assume that there is
5% breadcrumbs. It also appears from the ingredient list that there is 15% wholemeal rye flour.
There is, however, an obvious problem: At one point or another, the company must have started to
bake this bread, and naturally at one point they did not have crumb from this bread available. Let us
therefore assume that they replaced the breadcrumbs with (more) wholemeal rye flour in the first round of bread they baked.
It is easiest to calculate with shares instead of percentages, so 5% corresponds to 0.05, and 15% corresponds to 0.15.
Let rn be the total proportion of whole grain rye flour in the n'th batch of bread (this is the sum of the rye flour,
which has entered directly into the dough and the rye flour the rasp contains, which (possibly) has entered ´
the dough).

• Determine r1. Find a difference equation for rn

How do do i determine the r1 and find the difference equation?

[pearl hull]

I have a question, what does this mean? That | what does it represent?

[indigo ferry]

13 divides 143

[pearl hull]

Oh gotcha

But what does it mean when divides?

Is not the same as /

[indigo ferry]

it means 143 is divisible by 13

not the operation division

13 | 143 is a statement, which is either true of false

[pearl hull]

Oh gotcha

So I always have to invert it

Why does math always overcomplicate something

[indigo ferry]

well it's still just saying divides

like how you would normally say it

so 13 | 143 means 13 divides 143 (without a remainder), which is a True statement

[pearl hull]

Ok gotcha

I am stuck with another problem, but it takes so long

Imma finish the rest and then I will show you the problem

[fiery sonnet]

Hello, I need help with the following induction

Either I forgot how to do algebra to get rid of the +3, or the formula I derived from the sequence is wrong

Idk which one

[indigo ferry]

Your hypothesis doesn't work for e_2

[fiery sonnet]

So the equation is wrong, thats an overlook from me

Thanks for pointing it out

[indigo ferry]

You get e_n = 2 4^(n-1) if it's just e_n = 4 e_n-1

[fiery sonnet]

I see

I found my mistake, thank you for the help

[weary tiger]

meaning of this?

[mortal tide]

@weary tiger The intersections of A_i

[vital dew]

Рами

[mortal tide]

Think of it like the "sigma sum" of intersection

[weary tiger]

thanks man

[astral fractal]

For an integer n, prove that if 2^n − 1 is prime then 2^(n−1)(2^n − 1) is perfect.
Does anyone know how to approach this question?

[indigo ferry]

Is this $2^n-1$ and $2^{(n-1)(2^n-1)}$ ?

[vital dew]

Franz

[astral fractal]

It is this

[indigo ferry]

You should be able to count up all the divisors

[astral fractal]

so that is 2^n - 1 and 2

But I need to prove it properly

[indigo ferry]

you know what a perfect number is?

[indigo ferry]

do you see that it's true?

[astral fractal]

yeah and it is true..

[desert ibex]

Bruh

[indigo ferry]

wait nvm it works

[haughty garden]

Hint: the divisor sum function is multiplicative, and it’s easy to see that 2^{n - 1} and 2^n - 1 are coprime

[desert ibex]

2^n - 1 is prime, let it be x. The only divisors of 2^(n-1)(2^n - 1) are of the form x^a times 2^b where a is either 0 or 1 and b is an integer between 0 and n-1.

Consider the sum of these:
(2^n - 1)(2^n - 1) + 2^n - 1
= (2^n)(2^n - 1)
= 2 times (2^{n-1})(2^n - 1)

By definition, this implies that (2^{n-1})(2^n - 1) is perfect.

[desert ibex]

But yeah, basically this

[verbal blade]

Any idea on how to prove this?

[desert ibex]

What does this notation mean?

You want to prove that there exist integers a, b which satisfy those properties?

[verbal blade]

Yes, exactly

[desert ibex]

Okie

Well that seems simple. You can construct A and B as follows:
For any prime factor of r that is not a prime factor of s, put the highest power of it that divides r in A
Similarly do the same for s and B
For prime factors that divide both, put it in the one which has a higher power. Break ties arbitrarily.

[pearl hull]

I am not understanding how to get B in this part:

[indigo ferry]

where do you get quizes like this

[pearl hull]

In the Rochester Institution Of technology

[indigo ferry]

fancy

[verbal blade]

Oh you are right, i was making it harder than it was, thank you 🙂

[pearl hull]

I have no freaking idea of what to do there

Where can I find actual help?

Professor might be busy

[fiery sonnet]

Proof by induction, am I doing this right? If so, I am stuck here. Any hints would be appreciated

[pearl hull]

Found it by myself

[viral crown]

what're you proving here

[fiery sonnet]

4^(n+1) + 5(2n+1) is divisible by 21

[viral crown]

do you mean 4^(n+2)

and here are the properties of the mod function

you may find them helpful

[blazing warren]

what's the maximum number of maximal chains in a size n poset

im thinking oeis 792

[blazing warren]

but i have no proof or any idea where to start

[weary tiger]

How come there's only one chain of (321) in the numerator yet both sets are cancelled out in the denominator?

[wicked bolt]

it’s the 6

[weary tiger]

Ah of course.

Thanks a lot.

[wicked bolt]

lol np

[edgy vine]

My idea was to show the upper and lower bound of |E(G)|. Using sum deg term, and assuming our graph to be at most a complete graph I get n^2/4 <= |E(G)| <= n(n-1)/2.

And now I show that when we remove one vertex, say n/2 edges at least, I show that |E(G)|>= (n-1) in both extreme cases of |E(G)|. Because only then it still is connected.

And show that |E(G)| is guranteed to be smaller than (n-2) if we remove one more time atleast n/2 - 1 edges. My idea has to be wrong somewhere..

[desert ibex]

Divide G into its maximal connected components

If G is not connected then there exist at least two connected components

Therefore there exists at least one component with <= n/2 vertices

Pick any vertex V in such a component

It can have at most n/2 - 1 edges to other vertices in that connected component. Since delta(G) > that, there must be at least one edge going to a different component. This contradicts the maximality of connected components.

[solar flame]

<@&286206848099549185>

appreciate the help if someone can help

[blazing warren]

help me 2 😦

[barren bear]

Can anyone explain how I am supposed to look at these types of circuits? Or tell me where I can go to read about it so I can understand it? I've only seen the basic boolean gate logic style before. (The ones you see in Google Images if you search "boolean gate")
How can I tell which values need to be true or false for these more realistic looking circuits? (In this example, to make the lamp turn on.)

[indigo ferry]

For the Lamp to light up, the circuit needs to be complete in some way

think of it as layers

If you look at the first layer and the second layer, switches R or ( P or Q) should be on to connect those

and then you need (Not Q) or (Not P)

since all three layers need to be connected, you have [ R or ( P or Q ) ] and [ (Q') or (P') ]

[barren bear]

Thanks Franz. Knowing that those branches are what "OR" is supposed to look like helps a little.

So to satisfy the top side, R can be True. If not R, either P or Q can be True.
But then the middle section (Q' or P') has to be True too, so either P or Q has to be True to satisfy this section.

So... both of these can work right? Since one of them is true in these cases, we can ignore R?

P: True, Q: False
P: False, Q: True

And what if R is True?
What about this?
R: True, P: True, Q: True

I guessed this for the question but it says it's wrong. Why is it wrong?

Nevermind on the last question. I forgot about the middle section when I was thinking about it. That would make the middle section False, False. So I see why it's wrong now.

Thanks a bunch for your help! 🙂

[spring hound]

Is there a more specific term for a DAG with finite nodes where the edges are labelled with unique natural numbers and directed edges can only go from lower labels to higher labels?

Or, I guess one whose adjacency graph is strictly upper triangular.

[blazing rose]

can anyone tell me what the term in a) means?

[haughty garden]

I assume it's $a \equiv b \pmod n$, something of that sort?

[blazing rose]

ohh ok

so if a equals b mod n then c to the power of a equals c to the power of b mod n right?

[little prism]

that's what you have to prove or disprove, yes

[blazing rose]

alright thanks

[raw jetty]

can someone help me prove that □P → ♢P is D-valid?

as well as prove that it is F valid?

[untold nimbus]

is this a valid statement?

[indigo ferry]

True

The first part is saying $\forall a \in A ; \exists b \in B$ such that $a=b$

[vital dew]

Franz

[barren bear]

@indigo ferry @foggy marsh Thanks again for your help yesterday / this morning. I took my Discrete Math 1 exam a few hours ago and passed!

Now I’m working on Data Structures & Algorithms 1. But right after this I’m sure I’ll be back again asking for help because Discrete Math 2 is next! lol

[hidden locust]

i dont understand the conversion why is the reminder different than whats on my calc

can anyone explain the steps please

[stray reef]

@hidden locust what are you putting into your calculator?

it's likely that it does not know you want quotient and remainder, and instead gives you a decimal expansion.

[hidden locust]

i feel like im completely wrong can u tell me the steps

@stray reef ya i have no idea how to do it

[stray reef]

...

[hidden locust]

i know its very simple

i just dont know how to do it

[stray reef]

do you still want an explanation specifically for the "why is my calculator giving a different thing than written here" issue

yes or no

[hidden locust]

so im just dividing the number by 8

[stray reef]

please answer the questions i ask you!!!!

[hidden locust]

yes yes

[stray reef]

right

so you want to know why the calculator gives you something different than you expect

please show what you are entering into the calculator and getting out of it.

preferably with a picture.

[hidden locust]

.8 is the problem

[stray reef]

right. that's more or less what i thought was going on, but i wanted to make sure.

the calculator does not know that you want a quotient and remainder, and instead gives you the result of division as a decimal.

[hidden locust]

what are those?

quotient and remainder

[stray reef]

do you know how to do long division by hand

[hidden locust]

yes

[stray reef]

long division produces those

[hidden locust]

oh ok ok

[stray reef]

and in fact i was going to suggest that you do this via long division by hand

look up "division with remainder" later

[hidden locust]

ok ill

so i cant use a calc with these?

[stray reef]

you can, but it takes some workaround.

record the integer part of the result, subtract it away, and multiply the fractional part you're left with back by 8

[hidden locust]

the integer is?

sorry i learn this in arabic

[pallid lintel]

Guys i need help with my multiplication 😢😢

Pls dont tell my mom

Whats 7x7 Pls help

[stray reef]

the whole number

the part before the decimal point

[pallid lintel]

Plsbhelp

[pallid lintel]

Plsss

[hidden locust]

oh ok like 4.5 its 4

[pallid lintel]

Ok

[stray reef]

@pallid lintel you're too young to use discord

[pallid lintel]

Whats 9x9

Nooo Pls

Help

[stray reef]

also your computer can answer this for you

[rugged jackal]

..

[pallid lintel]

I dony know how Pls

[stray reef]

if you can use discord then your device has a calculator

[rugged jackal]

81

[stray reef]

@rugged jackal don't encourage them

[rugged jackal]

81..

[pallid lintel]

Whats 6 times 1 Pls

[rugged jackal]

..

[stray reef]

@rugged jackal don't.

[rugged jackal]

ok

[hidden locust]

lmao

[pallid lintel]

I need help

Pls

Om only 7

Plsssss

[rugged jackal]

why u got discord

[pallid lintel]

Because i Hadked my phon

[stray reef]

@pallid lintel you need to be 13 or older to use discord.

[pallid lintel]

My screen Time

[stray reef]

you cannot be here.

[pallid lintel]

I am 13

[rugged jackal]

wow ok

[stray reef]

no, you said earlier that you were 7.

[gritty crescent]

Gottem

[hidden locust]

ty mod

[stray reef]

🫡

[rugged jackal]

you just grew 6 years in 1 mintue

[hidden locust]

ann so if its 4.453 the integer is 4?

[stray reef]

yes that's what i was talking about

[hidden locust]

oh ok ok

ohhhhh ok ok

thats easier than doing all that long division stuff

i used to do advanced math stopped doing math for 2 years nowim so bad

[still belfry]

how do i prove this?

[azure willow]

hello 👋 i don't understand this at all

could someone help me?

[stray reef]

@azure willow how much do you know about generating functions, particularly ordinary ones

[azure willow]

not too much. i can sort of see some recurrence relation being formed but i can't particularly solve it myself

[stray reef]

well you understand that the infinite series that gives you your ordinary generating function is $\sum_{n=1}^{\infty} \frac{1}{n} x^n$, yes?

[vital dew]

Ann

[azure willow]

yes

🤔

1/x * (x / (1-x) ) ?

nah that ain’t t right

[stray reef]

if we let f(x) = this sum then you will have f'(x) = 1/(1-x)

[azure willow]

i do not follow

if we multiply the function out then yes it will be 1/(1-x)

but as far as the derivative i don't see it?

[stray reef]

"if we multiply the function out"

??

[azure willow]

this is what i mean lmao

i'm totally lost on this

i meant, if we multiply 1/x * x/(1-x) we get 1/(1-x)

[stray reef]

1/x * x/(1-x) is wrong and came from nowhere

[azure willow]

yes

i was guessing

[stray reef]

...

[azure willow]

😭 what dude

[stray reef]

let's try to start from the beginning, because clearly a communication issue happened somewhere along the way.

we want to find a closed form for the generating function $f(x) = \sum_{n=1}^{\infty} \frac{1}{n}x^n$.

[vital dew]

Ann

[azure willow]

yes

[stray reef]

to this end, i suggest taking the derivative of your series

you will get $f'(x) = \sum_{n=1}^{\infty} \frac{1}{n} \cdot nx^{n-1} = \sum_{n=1}^{\infty} x^{n-1}$

[vital dew]

Ann

[azure willow]

yes, i follow

we get 1, x, x^2, x^3, etc etc

this is the geometric series

[stray reef]

yes

so $f'(x) = \frac{1}{1-x}$

[vital dew]

Ann

[stray reef]

at this point i have not yet claimed any closed form for f itself, mind you!

[azure willow]

yes yes

im with u so far

[stray reef]

yeah and now we integrate

[azure willow]

ok

[stray reef]

noting also that f(0) = 0, which will help us pin down the constant of integration

[azure willow]

i got -ln|1-x| + C for my integral

😭

[stray reef]

yes this is correct

sorry for the delay on my part

[azure willow]

ur fine

i think i got an answer?

i used the S-xS method

hold up lol

$f(x) = \frac{1 - \frac{x}{2}}{1-x}$

[vital dew]

Ourple

[azure willow]

i'm also seeing a 1 - 1/x but that could just be nothing

@stray reef

for 1, 2, 3, 4, it's $f(x) = \frac{1}{(1-x)^{2}}$

[vital dew]

Ourple

[azure willow]

for 1, 1, 1, 1, it's $f(x) = \frac{1}{1-x}$

[vital dew]

Ourple

[azure willow]

can i do the generating function for 1, 1, 1, over the generating function for 1, 2, 3, 4?

$f(x) = \frac {\frac{1}{1-x}}{\frac{1}{(1-x)^{2}}}$

[vital dew]

Ourple

[azure willow]

so then $\frac{(1-x)^ {2}}{1-x}$

[vital dew]

Ourple

[azure willow]

so it would just be $1-x$

[vital dew]

Ourple

[azure willow]

???????

[spring elk]

can i get help with part b?

so the domain is {t1, t2, ... ,tn} and the range is {1, 8, 27, .., n^3} for g of f restricted

would the domain of g be {1, 8, 27, ..., n^3}?

?

and if so whats the range of g?

[ember obsidian]

@spring elk u mean g or g^-1?

[indigo ferry]

for (a) do we consider a fixed n?

hmm I guess that's doesn't really matter

[ember obsidian]

also in general if $g:X\to Y$ is invertible then we have $g\inv:Y\to X$

[vital dew]

RokettoJanpu

[spring elk]

the domain of g

we are given that for g of f the domain is {t1, t2, ..., tn} and if we use these in f then we get {1, 8, 27, n^3}

[ember obsidian]

so i think theres a misunderstanding of what g is

[indigo ferry]

okay so g is invertible on it's codomain idk if it's valid to say range

[ember obsidian]

this is false

[indigo ferry]

why

[ember obsidian]

whats the codomain of g

[spring elk]

thats what im not sure of

[ember obsidian]

ok so lets review the def of restriction

[indigo ferry]

$$CoD_g = {k^3 | ; k \leq n, k \in \mathbb{N}_0 }$$

[vital dew]

Franz

[spring elk]

if i restrict f on A1 then the domain of f would be the elements of A1 right?

thats restriction

[ember obsidian]

false

[ember obsidian]

yes

[indigo ferry]

how so>

[spring elk]

so in this case g of f im restricting to domain t1 t2, .. tn

[ember obsidian]

codomain isnt the same thing as range

[indigo ferry]

that's what I'm saying

[indigo ferry]

okay so what is the codomain of g then?

[ember obsidian]

for a function $f:X\to Y$, the restriction of $f$ to $A\sse X$ is a function $f|_A:A\to Y$ given by $f|_A(x)=f(x)$

[vital dew]

RokettoJanpu

[ember obsidian]

in this case, g is the restriction of f to {T1,..,Tn}

so the domain of g is that set. the codomain of g is Z_>=0

[spring elk]

still dont really get how the domain of g is the set because that set is the domain of g of f (so g(f(S))

[ember obsidian]

i think youre confused by the wording

we dont have a composition g with f

[spring elk]

ohhhh

[ember obsidian]

g is defined as a restriction of f

[indigo ferry]

So f|g is just f, but with a limited domain

[ember obsidian]

in this case $g=f|_\brc{T_1,…,T_n}$

[indigo ferry]

defined on limited inputs

[spring elk]

oh so g is restriction of f and f is restriction of {T1, T2, ... Tn}?

[vital dew]

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

[ember obsidian]

using my notation for restriction

[spring elk]

so when they say "g of f to {T1, T2, .. Tn} they just meant that g = the restriction of f to {t1, t2, .. tn}?

[ember obsidian]

the intent of the wording is “the restriction (which we’ll call g) of f to {T1,…,Tn}”

[spring elk]

Ohhhhhhhhhh

i seee now..

ok given that I am going to attempt to solve it thanks

[ember obsidian]

ur welcome

[spring elk]

in this case it is one to one because since f is restricted on a set that has multiple subsets each of different cardinality, clearly they cant have the same range.
Since the cardinalities are the same can we straight up say its injective without proving its onto?

eitherway it is also onto because the cardinalities are the same and since its given that it is a function clearly everything is mapped

but if domain and range have same cardinality is it enough to just prove its one to one or onto to conclude its injective?

[ember obsidian]

the restriction of the codomain of a function to the range is always onto

u can check this urself if thats not clear

we’re showing that g, with its codomain restricted to its range, is invertible, so we just need to show g is injective

the only use of cardinality here should be in the injectivity argument

[spring elk]

this makes sense

[spring elk]

so does my argument make sense?

for injective part

we already know its a function (so all domains are mapped) and because of cardinalities we know its not mapped to the same thing

[ember obsidian]

it mostly makes sense, just a vocab issue

i think u mean to say output, not range

range=set of outputs

[spring elk]

ah yes

thanks!

[gilded knoll]

Hey how are you guys doing

I need help with a discrete math problem dealing with finding a value looking at pseudo code was wondering if someone can show me how to actually do it

[glacial flame]

Have you learned about summations?

If so, try thinking about how these could be written as summations (and take note of how s starts and changes)

[ionic field]

Hi , can you give me a textbooks for descrete math combinatorial analysis

[snow axle]

What is discrete math

[jagged hearth]

This is a graph theory question, but theres no channel for it. The proof is for the theorem that: "A finite connected graph is Eulerian if and only
if all its vertex degrees are even". Consider a trail $T = v_0e_0v_1e_1....e_k$.

Assume that there are $2s$ edges incident to $v_k$. One of these edges is required to be $e_k$, Where do the other 2s - 1 go? If $v_k$ occurs as an internal vertex of $T$, that is $v_j = v_k$ for some $1 \leq j < k$, then $e_j$ and $e_{j+1}$ must both be edges to $v_k$. Thus, any internal occurence of $_k$ takes up 2 edges. This explains where $2s - 2$ of the edges of $v_k$ go, leaving one trail.

[vital dew]

sam

[jagged hearth]

This is direct copy of my lecture notes, but is this last part not a typo? Surely this would explain where 2s - 3 of the edges go?

The continuation is also: leaving one trail - and that one has to go out of v_0 to v_1 != v_k

Which I also dont uderstand

[tidal tulip]

@uneven violet that makes sense. thanks!

[cerulean wind]

look up multisets and ordered pairs.
surjective set is not standard terminology

oh, then yes

if f is a function from X to Y (it does not matter if Y is a subset of X or not) then for each x in X, f(x) is an element of Y.

if Y is a collection of sets, then each function value f(x) will be a set. for example, f : R —> P(R) where f(x) = {x}

[pallid lynx]

Hi i did'nt understand what is an 8bit two's complement is. Can someone explain it to me pls ?

ok thanks

it's just the first digit that change ?

ok i understood

And it's used when ?

ok

[sly sinew]

i'm having trouble finding a recurrence for T

[sly sinew]

<@&286206848099549185>

[indigo ferry]

pretty cool

https://cdn.vox-cdn.com/thumbor/KwXyAUZGjHOfbZ7Ef0AAtXnzG7M=/0x0:1409x785/1400x1050/filters:focal(734x364:735x365)/cdn0.vox-cdn.com/uploads/chorus_asset/file/8846551/Screen_Shot_2017_07_13_at_1.09.20_PM.png

[sly sinew]

yo

[indigo ferry]

so what've you got so far?

[sly sinew]

i got t1 = 1 t2 = 2 t3 = 6

and im trying to figure out a recurrence based on these initial conditions

im noticing you can place the new number n before either n-1 or n-2

so for every permutation there's two new permutations but i think theres more places to put the new number

@indigo ferry what do you think?

[indigo ferry]

working on it

but yeah, there a lot more than I thought of at first glance

[indigo ferry]

where's this problem from?

[sly sinew]

my discrete math class

[sturdy bear]

What is this? Context: group theory

[haughty garden]

The degree of the field extension G / H when G is considered as a vector space over H

[wicked bolt]

i thought it would be the index of H in G

[haughty garden]

Index and degree are synonymous in the context of field extensions

[wicked bolt]

but...

Context: group theory

[haughty garden]

ah my bad

yeah it's the index of a subgroup H in G (aka the number of left cosets of H in G)

tfw I've done too much field theory

[vale cairn]

and for what it's worth, group theory would normally belong in #groups-rings-fields

Groups needn't be discrete

[formal palm]

is an arithmetic sequence with the initial term 50 and the common difference -3.

for this question would be be 50-(-3) or just 50-3?

[lean spear]

Difference between $a_1$ and $a_2$ is $-3$, meaning $a_1+(-3)=a_2$ so it's $50-3$

[vital dew]

Lachlan

[formal palm]

thanks

[sly sinew]

can someone point me to the right direction to solve this problem?

came up with a couple recurrences but they don't seem to work in all cases

[sly sinew]

<@&286206848099549185>

[red nest]

T_(n+1) = 3T_n for all n >= 2.

[sly sinew]

you think so?

i had T(n) = 2T(n-1)

[red nest]

Because n+1 goes in one of three places, behind n, behind n-1 or at the end

[sly sinew]

plus cases where you can put n at the end

but you can’t put n at the end for all permutations of T(n)

[red nest]

You can

[sly sinew]

oh will it always end in n-1 or n-2?

[red nest]

No

[sly sinew]

oh wait no you’re so right

can’t believe i missed that

[red nest]

Lol we all have those moments

[chrome lily]

Am I wrong?

Is this not false lol

[haughty garden]

0 is not prime

So, while the statement is false, it’s not false because of n = 0

[turbid gorge]

Not sure if this is discrete math but idk where else this would fall

I have to simplify this boolean expression

[vital dew]

斗地姿

斗地姿

斗地姿

[short phoenix]

(Boolean Algebra) Is this simplification corect? I am not sure if x+x'y can be equal to (x+x')(x+y) using the distributive law

sorry if my handwriting is messy

[mighty ivy]

I cant visualize the difference between a mealy machine and a moore machine. Can anyone help?

[copper slate]

I am a bit confused with this equation { x ∈ S | P(x) }
In the book it says - x denotes "the set of all"
But isn't x only an element in set S here?

[indigo ferry]

The whole thing would read "the set of all x in S such that P(x)"

[copper slate]

True. But does x denote a subset here or just a single element?

[indigo ferry]

x is an element of S, but if S is a set that contains sets then x can be a set in S

[copper slate]

Right. I was just reading about the real number line.
And its a set of real numbers divided into 3 parts.

1. Set of positive real numbers. (R+)
2. Set of negative real numbers. (R-)
3. 0
   So i believe x can denote any one of them.
   Got it.
   Thanks @indigo ferry

[copper slate]

These links might be helpful.
https://www.geeksforgeeks.org/mealy-and-moore-machines-in-toc/
https://www.geeksforgeeks.org/difference-between-mealy-machine-and-moore-machine/

[formal palm]

b) An RNA sequence is a sequence of letters (also called bases), each of which is one of A, C, G, or U.
How many 4-element RNA sequences do not contain the sequence CUG?

how would i do this?

[gritty crescent]

It's probably easier to proceed by exclusion: count the number of sequences of the type _CUG and CUG_, and then subtract it from all possible sequences of length 4.

[thorn jacinth]

hey, posted this yesterday, someone suggested me to ask it here.

may i have some help ?

what i've tried :
if m = rs, then the graph should be complete. if it's not, then it has less edges, thus rs > m

but i'm pretty sure i can write that in a better way

[formal palm]

A committee is formed with a union. In the union there are 98 companies that participate, where each company provides 5 representatives. How many ways are there to form this committee?

Would this be 5^98 or is it 5 or is it P(98,5)?

[weary tiger]

If we do Kleen star, it certainly always include the original words of this language?

[weary tiger]

Is this how to prove it ?

(Automata and formal languages)

[grand totem]

The Kleene star of a language L is the least language that contains L as a subset, has the empty word as an element and is closed under concatenation.
So in particular, yes we have that L ⊆ L*

And you also noticed correctly that the proof makes use of the fact that we also have ε ∈ L*

Oh wait, your proof actually does contain a slight error concerning that fact. While the empty word is always part of the Kleene star of any language, you claim (in the 2nd line of the proof) that ε ∈ L₁ (and similarly for L₂). That however doesn't generally hold

[weary tiger]

What i tried to do is

I tried to make that w is in L1 and epsilon is in L2

Or its the other way around

Therefore
L2*L1 equals that^

[grand totem]

How do we know that the empty word is in L2 though?

[weary tiger]

But I'm not sure if that's true idk

[weary tiger]

I made two options

That it's either in L1

Or its in L2

[grand totem]

The empty word doesn't necessarily need to be in either one

[weary tiger]

Oh

True

[grand totem]

Your proof is almost correct, specifically it is correct to say that ε ∈ L* for any language L (by the very definition of the Kleene star)

[weary tiger]

Yh

[grand totem]

And that is really all you need

[weary tiger]

So wait

I just gotta add that

Epsilon is in L* for any language ..

Then the proof is correct?

@grand totem could u write it or something pls

Cuz I'm not sure of the first part too

That marked in yellow

Cuz yh its not necessarily having epsilon

[grand totem]

I'm not going to write the proof for you, especially because your reasoning is fine for the most part (though I suggest you write more words and less in symbols)

[weary tiger]

Ight I'll try to fix it ty

Do u think it's better now 😅

[weary tiger]

The thing written on right bottom side is this basically

[grand totem]

A generous prof (or TA) would probably accept this since the proof is correct but without any words justifying some of the steps (specifically the ones that rely on the definition of the Kleene star) the proof looks rather empty

For example, why is w ∈ L₁*

[weary tiger]

It was essentially a larger equation and i proved half of it with words and got this derived out of it basically that's why i thought proving it normally would be better 😅

[weary tiger]

In previous steps I've explained it yh

Now i just mentioned it back without explaining it since it was previously explained in the same question

[weary tiger]

Is that more correct than the pic i posted before ?

(changed second line)

[grand totem]

Yea, this one is correct (as in it doesn't contain any wrong assumptions like the previous one)

[weary tiger]

Ight tysm mate appreciate it

[grand totem]

👍

[indigo ferry]

Proof:
Wel
Wel
Well

[cedar token]

am I doing it correctly?

[weary tiger]

@grand totem u awake for a quick question? 😅

[grand totem]

Sure but in general just ask the questions so others can help too

[weary tiger]

All g don't worry ty i have done it 🙏

[weary tiger]

Ight getting fucked by a new question again

I need to give an example of two infinite languages L1,L2
That upholds these conditions
L1L2=L2L1
And
L2 cap L1 = ∅

Can i do
L1= {a}*
L2={b}*?

Idk it seems correct for me but that's so simple so doubt it lol

[haughty garden]

Consider the languages $L_1 = {a^{2k} : k \in \mathbb N}$ and $L_2 = {a^{2k + 1} : k \in \mathbb N}$.

If $w \in L_1$, then $|w|$ is even so $w$ can't be in $L_2$. Likewise, if $w \in L_2$, then $|w|$ is odd so $w$ can't be in $L_1$. This shows that their intersection is empty.

It's easy to see that $L_1 L_2 = L_2 L_1$. Take any string $w \in L_1 L_2$. Then it is composed of $(a^{2k})(a^{2m + 1})$ for integers $k, m$. But this is exactly the same string had you grouped the first $2m + 1$ $a$'s followed by $2k$ $a$'s to give you a string in $L_2 L_1$. The reverse argument holds.

[weary tiger]

Ty

[weary tiger]

Wait how did u prove that L1L2=L2L1 in the second part

[haughty garden]

Prove both inclusions

[weary tiger]

w ∋ L2L1

Which is composed of (a^2k)(a^2m+1)

Then what did u exactly do

[haughty garden]

Let $w \in L_1 L_2$. Then there exist integers $k, m$ such that [w = (a^{2k})(a^{2m + 1}) = \underbrace{\left(a \cdot \dots \cdot a\right)}{2k}\underbrace{\left(a \cdot \dots \cdot a\right)}{2m + 1} = \underbrace{\left(a \cdot \dots \cdot a\right)}{2m + 1}\underbrace{\left(a \cdot \dots \cdot a\right)}{2k},] which is in $L_2 L_1$

ehhh it cut off but hopefully you get the idea

the idea is that w is finite (in length), so you can regroup the a's to obtain a^{2m + 1} a^{2k}

but this is exactly an element in L_2 L_1

[weary tiger]

Oh got it

Ty

[haughty garden]

Yeah, the reverse argument follows by just reversing the argument we made

[weary tiger]

Yh

[sly widget]

I was confused as to how to approach this

[brave rock]

Maybe you could try induction.

[sly widget]

I am trying induction but I get stuck on the inductive step

[indigo ferry]

use the binomial expansion for x + h

[sly widget]

Can you elaborate as to what you mean? sorry for asking too many questions

[cerulean wind]

assume that its true for some $n$.
$$\frac{d}{dx}(x^{n+1})=x^{n}+x\cdot \frac{d}{dx}(x^n)=\dots$$

[vital dew]

c squared

[lusty fern]

What does it mean logically for a event to be transitive?

[stray reef]

an event?

@lusty fern do you still need help with this

[lusty fern]

Nvm, I think I understand it now

[weary tiger]

Prove or disprove

[haughty garden]

Is L^2 the concatenation of L with itself?

[jagged hearth]

I dont understand this marked section

How can this be a cycle, you must use the edge {x,w} twice?

How else do you "starting at x, following along P until w"

I don't see why P necessarily goes along another edge than {x,w}

what am I misunderstanding

[south dock]

Just a quick question. What is i in this equation?

We're doing currently doing frequency estimation using sparse fourier transform

[weary tiger]

$\sqrt{-1}$

[vital dew]

rakki

[weary tiger]

?

[south dock]

Oh yea ur right ty

[weary tiger]

lol yeah with all the other variables it took me a second to remember as well

[south dock]

Also, there's one other thing that I'm completely lost on. My prof found 49536, 669784, and (1024x1021x87) as N values and I'm unsure why. She initially had an N value of 715, fw = 100, and w = 67 with N having a factorization of 5, 11, and 13.

These were the equations she used

Any help is much appreciated ❤️

[solar flame]

can anyone help with this please?

[restive surge]

I know basic discrete math (like the stuff you would need to know for competition math), and it really intrigues me. I don’t really have access to any book nor money to buy books, and I learn best through practice problems. Anyone have any suggestions on i where I could learn some more advanced stuff?

[solemn zephyr]

How many k-element subsets of the set {1,…n} are there in which no two consecutive numbers occur?

is this correct?

[serene plume]

How do discrete math

[umbral blade]

True/ false / open
If factoring is an element of p, then p does not equal np.

Kind of confused when I consider the implication rules.

I was thinking it was open because because we don’t know if p= np

But I could also see it being false

Just confused with the implication rules when one part of the proposition is open or both parts of t are open

[rancid galleon]

. Let GO and S be predicates as shown below. Write using connectives ( and, or and negation and the existential and universal quantifiers), to express the following:

All the people will either go out when it is snowing or if some people do not go out when it is snowing then some people will watch a movie.
Use the following
GO(x): x goes out where x is a person
M(x): x watches a movie where x is a person
s : It is snowing.

[outer kayak]

how could i go about this?

[viral crown]

think about constructing bijections!

i'll give you a hint: so you know how to prove that the cardinality of N is the same as the even integers?

there's really not a big difference between even (divisible by two) and "s-even" (divisible by seven)

and much the same thing might work for the squares

and think about what T is a bit more relative to A

[outer kayak]

hmm

[viral crown]

and what do you know about the set of all primes?

[outer kayak]

they are in the set of all N

[vale cairn]

Another thing is uh well maybe a sledgehammer but every subset of N is either same cardinality as N or finite

[viral crown]

LOL

[vale cairn]

So uh

[viral crown]

i feel like that's too strong for this problem

[vale cairn]

I mean fair but it gives intuition hopefully lol / is smth you should be aware of

But yes definitely too strong for this

[outer kayak]

thanks guys

[rancid galleon]

can someone please answer my quesiont?

Let GO and S be predicates as shown below. Write using connectives ( and, or and negation and the existential and universal quantifiers), to express the following:

All the people will either go out when it is snowing or if some people do not go out when it is snowing then some people will watch a movie.
Use the following
GO(x): x goes out where x is a person
M(x): x watches a movie where x is a person
s : It is snowing.

[south dock]

Question. How can I determine frequencies in a signal using DFTs?

[outer mango]

anyone knows how to do this

[crystal oyster]

Problem 6: In simple terms, what is a binary predicate? Explain the difference between
the two binary predicates ∈ and ⊆ (these are symbols in the language of set theory) by
completing the following 4 parts: In each of the following four parts, find two sets A and
B such that
a) A ∈ B is true, and A ⊆ B is true
b) A ∈ B is true, and A ⊆ B is false
c) A ∈ B is false, and A ⊆ B is true
d) A ∈ B is false, and A ⊆ B is false

[crystal oyster]

can anyone help with those four proofs?

[urban cypress]

Is there a tool that shows induction proof step by step

[crystal oyster]

im not sure tbh, ive been trying to find out to help out but i cant see to find one

[velvet iris]

what does this notation mean?

Graph G, is there a dominating set D such that G[D] is connected?

what is G[D]

[jagged hearth]

https://math.stackexchange.com/questions/4577257/proof-that-every-finite-tree-with-at-least-2-vertices-have-at-least-two-vertices

Need help with this

[umbral blade]

Proposition True or False or Open:
If factoring is an element of P, then P does not equal NP.

I went with open because of implication rules.
A proposition with Open —> open makes the proposition open?

[steady nymph]

False. There exists a world where factoring is in P and P = NP

Also “P = NP => Factoring not in P” is clearly false and these are equivalent statements

[wicked bolt]

what about
if the riemann hypothesis is true, then the riemann hypothesis is false

[umbral blade]

Open —> open would be open

[steady nymph]

No

[umbral blade]

That’s my question it’s clearly false but since it’s open and with implication rules then wouldn’t it be open

if we dont know if P = NP then the prop. would have to still be open would it not

false --> open is open

so why wouldnt open --> open be open

[haughty garden]

P = NP implies coNP = NP

So just because one side is open doesn’t mean an implication is open

It turns out both sides of this implication are open problems

But the implication we have here is true

[umbral blade]

if primality testing is in p then p = NP

T --> open

would it be true, false, or open

[haughty garden]

Primality testing is in P, no?

[umbral blade]

yes

[haughty garden]

It doesn’t imply that P = NP

[umbral blade]

we discussed this problem in class, and my teacher said although we know Primality testing isn't NP hard

the propostion is still open

because of the open being on one part

[haughty garden]

It suffices to show that any problem in NP-complete is in P to show that P = NP

But primality testing is not in NP-complete because it isn’t in NP-hard

So supposing that primality testing is in P does not imply that P = NP

Or at least from what I recall anyways

[umbral blade]

i had the same logic, we know its in p but we still don't know that P = NP so the proposition is false

but my professor said its open so I just went with their logic

[haughty garden]

Mmmm having a quick search, it seems as though determining whether an integer is prime is unknown whether it is in NP-complete or not

And if it is, P = NP

[umbral blade]

hmm so the proposition just hasn't been directly proven false?

[haughty garden]

We just don’t know whether primality testing is NP-complete

It’s certainly in NP but we don’t know if it’s NP-hard

If it’s not in NP-hard, then it’s not in NP-complete and so having primality testing in P doesn’t really tell us a lot regarding P = NP

[whole field]

What does np mean

[haughty garden]

A problem X is in NP if X can be solved in non-deterministic polynomial time

Another way to think about this is that any solution can be verified in polynomial time

[whole field]

Wdym by non-deterministic

[whole field]

I see

[crystal oyster]

Could anyone tell me what’s wrong with this proof?

[runic junco]

H has no relation to anything, there is no reason it should be in F

[tidal bronze]

Can somebody explain how they got 4C1 for case 3?

[gray sun]

Not looking for an answer, but what would be the best approach to this open ended problem?

[lusty fern]

is there a trick to counting subgraphs of a graph?

[naive gust]

However, I am stuck on the second part and I still can not find the answer after several trials.

please help

[night stream]

would this graph have 13 vertices and 36 total degrees?

[stray reef]

"36 total degrees" is a little odd as far as wording goes, but yes, the total degree of this graph is 36.

[molten fjord]

can someone help explain to me why this is true

[haughty garden]

try proving big-oh and big-omega relations

[molten fjord]

Im trying to figure out c_1 and c_2 for this but I cant figure it out

I've been staring at it for a while

[haughty garden]

You can sorta guess c_1 and c_2 by working backwards

this would be suitable for the upper bound

[desert ibex]

Have a problem in mind?

[light sail]

an empty set can be considered a function ??

how

[pale epoch]

look at the definition of function

see if the empty set satisfies it

[midnight mural]

guys

Prove that the Goldbach conjecture that every even integer greater than 2 is the sum of two primes is equivalent to the statement that every integer greater than 5 is the sum of three primes.

what is the right way to think about this questions

question*

i mean how can i solve it

[blazing rose]

how do i understand this?

like is this the operation on 2 pairs of rational numbers?

and then what does the operation say

[balmy dune]

this question got me and im not sure if i solved it right. is (Q or R or P) is the right answer?

[indigo ferry]

shouldn't this be 3 C 1 . 2 ^ 2

[tidal bronze]

Thats what I was thinking too, i think this solution I have is wrong

[indigo ferry]

We'd need 1's on both sides, and this has no overlap with cases 1 or 2

[somber heath]

<@&268886789983436800>

[proper meadow]

I have a little packing problem where I want to find an optimal layout for maximizing the number of nodes in a 3D grid where the rule is that nodes should be within a taxicab distance of at least 5 of each other. Any idea how to go about it? And do you expect that for this distance it's intractable?

Ideally, the solution would be some X * Y * Z-sized pattern that can be tiled.

I'm not sure if this is the right channel, should maybe ask elsewhere.

Point me in the right direction, if that's the case. 🙂

[thorn lake]

Im confused

to find the union shouldnt I just add the caridnalities and then subtract the sum of that to the intersect?

thats what i did here

(126+58)-25

[pale epoch]

i think you missed the apostrophe on H

[thorn lake]

what does that mean?

[pale epoch]

i dont know, probably complement?

you have to consult your notes

[hollow dagger]

in a dag, if for any path from ui to uj, i add an edge from ui to uj, how can i show tht the graph i obtained is still a dag

[stray reef]

well presumably you want to show that the addition of all these edges never gave you a cycle

[hollow dagger]

wym by addition (sry not good w the english terminology)
i thought to assume through contradiction that the obtained dag (G') is cyclic, which would lead to G being cyclic (which is false), however i got stuck at expressing the supposed cycle

[stray reef]

i add an edge from ui to uj

this addition

[hollow dagger]

oh sry i rly thought of like a sum xdd

[gray sun]

Can i calculate the equation of a normal curve from a graph such as the following:

[outer kayak]

is this a sufficient proof ?

[viral crown]

uhhh if 'within 1 unit distance' is inclusive of 1 and you can't place a point along the lines of the outside triangle then yes

also technically the interior points don't have to be in the triangles so maybe you could write an allowance for that?

[outer kayak]

i see ok ty

[viral turret]

Anyone know what’s wrong here?

[viral crown]

you're doing induction wrong

https://www.youtube.com/watch?v=dMn5w4_ztSw&t=206s

this is the video that made it click for me

[viral turret]

Wrong induction?

[desert ibex]

Simple counting argument solves this. The total sum of degrees in a tree is 2n - 2. If n-1 vertices have degree >= 2 and 1 vertex has degree 1 then that results in the total degree being >= 2n - 1. Therefore at least two vertices must have degree 1.

[desert ibex]

Show that the topological sort is invariant

[desert ibex]

Start by assuming one of them and prove the other. Then go the other way.

[celest drum]

Hello hope you well. I have a question on number on number theory if any can help. Is there a different (more efficient method) of finding a multiplicative inverse of lets say 7 (mod 26) other than multiplying 7 by 1,2,3......15 checking if each will give 1 (mod 26)?

[uneven violet]

Hey, you can use the extended Euclidean algorithm for finding inverses. Here's a site that describes how it works: http://www-math.ucdenver.edu/~wcherowi/courses/m5410/exeucalg.html And otherwise, there's a ton of youtube videos on it as well.

[celest drum]

Thank you I will go over it

[hollow dagger]

thats the route i went on, thx u!

[desert ibex]

No problem!

[shadow grove]

Is there any obvious simplification to this that I am missing? Like some inductive proof-function I can't seem to find? I can find one for the version without the floor, but for the floor I cannot...

Without the floor, I have found:

Let k = 11/5, then

pop(n) = k^(n-1) - (k^0 * pop(n-2) + k^1 * pop(n - 3) + ...+ k^(n-3) * 1)

[vital flume]

how to find all solutions of a+b+c <= 6 and a,b <= 2 and c <= 4

[vital flume]

how can i prove this with induction?

[desert ibex]

Do the base case.

then we have
(-1)^m C(n, m) + (-1)^{m-1}C(n-1, m-1)
= (-1)^{m} ( C(n, m) - C(n-1, m-1))
= (-1)^{m} C(n-1, m) [since C(a, b-1) + C(a, b) = C(a+1, b)]

[weary tiger]

Okay so im trying to make sense out of what this question is asking, mainly in terms of what theyre saying $B^{A}{}$ is. From like thinking about it if figured they're talking the set looking something like $$
B^{A} = {F_{0,0},F_{0,1},F_{1,0}\dots F_{i,j}}
$$
Where $F_{k,0}{}$ maps the Kth Element of A to 0, and $F_{k}{1}$ maps the Kth element of A to 1.
My issue is weather this interpretation of $B^{A}{}$ is correct, if so why though? For any element in A isnt there an infinite amount of functions that map it to 1? So I think somewhere in my understanding its flawed of how $B^{A}{}$ is constructed, if i could figure what it looks like i think I would be able to solve the problem from there

[vital dew]

rakki

[weary tiger]

wait unless $F_{i,j}$ isnt a particular function, but make it the infinite set of functions where the property holds?

[vital dew]

rakki

[weary tiger]

also lemme know if this is the wrong channel lol. not sure if itd fit better in #proofs-and-logic more or smth

[sudden minnow]

no, that's not what an arbitrary element of B^A looks like

each function is defined on all of A

[weary tiger]

hm

alright let me try to remake it

alright so this isnt rly a rigerous way ive made it here, but like i wanna know if this is the step in the right direction

so like for each element in A i gave it a number between 0 and n, where like n is the nth element of A,
then say like the set of functions, like here function 1, would be like the set that maps element 1 to 1, F2 maps it to like a particular combination of 0s and 1s and then i kinda realized it was kinda like binary

uh just trying to think about the right way to word this to ask if on the right track, brb

[weary tiger]

written out more nicely this is what im thinking of so far

[vital dew]

rakki

[weary tiger]

$0 < i < |A| , i \in \mathbb{Z}$

[vital dew]

rakki

[weary tiger]

would this be a sufficient mapping of the functions in B^A ?

[sudden minnow]

... you are supposed to show B^A has |P(A)| many elements, while your set clearly has |A| many

so, not close

[weary tiger]

omg thats a good point

[sudden minnow]

all your functions map only one element to 1, that should give an idea how many functions you haven't listed

[weary tiger]

yeah yeah

im starting to see it

can i just say let F go from 0 to (2^|A|)-1 ? so then that way my binary representation hits all possible combinations

[sudden minnow]

I mean... you haven't really defined how this binary representation is defined, so you are just pushing the work one step further back

[weary tiger]

rip

[sudden minnow]

just think of a small set say {a,b,c}, write out every possible function from A to B, then write out every subset of A

think of a meaningful bijection

really this question is very easy if you just think of simple examples, instantly going way abstract is just going to make it harder to see the idea

[weary tiger]

yeah i bet

[desert ibex]

The idea is that the pull back of 1 (or equivalently 0) of a function in B^A is a subset of A, and each subset of A uniquely defines a function in which the pull back of 1 is that subset

@weary tiger

[weary tiger]

yee i think i got it

[desert ibex]

Awesome

[sudden minnow]

and fun fact, this is how cardinal arithmetic is defined

,, \kappa^\lambda := |B^A|

[vital dew]

lems

[sudden minnow]

where $|B| = \kappa$ and $|A| = \lambda$

[vital dew]

lems

[steady moon]

How do I write "if x then y"?

like if x is true then y is true

[glacial flame]

$x \rightarrow y$

[vital dew]

JJCUBER

[glacial flame]

Also known as x implies y

[unique karma]

would this statement be true?

[rapid mural]

What is P(n) here?

[unique karma]

quantified predicate

[rapid mural]

anything specific?

this statement is confusing, are you talking about induction?

[unique karma]

this is the whole question, consider the following predicates P(n): , explain why the quantified predicate is true

[rapid mural]

is n really in Z?

Because if you are inducting it's over N

(I mean I suppose you can induct over Z+ too but they're isomorphic)

[unique karma]

wait i figured it out nevermind lol

[limpid fossil]

how can i do D?

[proud needle]

Hello everyone. I have a graph theory research mentorship thing next summer, and I was wondering what the prerequisites to Graph Theory is. I am taking Pre-Calculus right now. I am reading the dover book about graph theory right now. Should I read up on some discrete math and study proof-writing?

[outer kayak]

Im a bit stuck on the surjective part.. am i on the right track ?

[heavy ridge]

Hi can someone explain the subset relation to me i dont rly get it

[frigid canopy]

The formatting is all ducked up, doesn’t make sense to me either

[desert ibex]

Well a very easy thing to do is just take the natural function from A to N which is obviously an injection, and then apply the Schroeder Bernstein theorem

[violet kayak]

That's kinda overkill though, just noting that each y=f(n) is divisble by 3 (by construction of f) is enough for the surjective part

[midnight mural]

Show that an infinite countable product of the set X = {0, 1} with itself is uncountable.

how can we start solving this question

[fluid torrent]

hint: ||binary representation of real numbers||

[vale cairn]

I would more say it's kinda the other way round aha

[unreal stump]

LHS is number of ways of picking n boxes from k+r boxes. Now RHS is also the same thing in a different way(Try to see why)

[weary tiger]

I don't understand haha, that's the point of the question lol

[unreal stump]

You want an explanation?

Or do you want to try

[eternal thicket]

How to get a recursive formula for the number of splitting 2*n elements into n pairs? I empirically realized that it would be a_{n+1} = a_n + n + 1, (although I still doubt the reliability), but I don’t understand how to get it combinatorially (through reasoning)

[weary tiger]

How about a hint hahah

[unreal stump]

Well if I give the hint,the question is done

[weary tiger]

Ah damn

Give me a moment I'll try to view it from a few more angles

[unreal stump]

||Think of RHS as pick i boxes from k boxes and the REMAINING boxes from r boxes||

||Clearly i can take the values 0,1,2...n since n<=k and n<=r||

||So you combine all the possibilities to get the total number of ways of picking n boxes from k+r boxes||

[weary tiger]

Thanks, makes total sense to me.now

I appreciate it

[vale cairn]

these combinatorial things are adorable

[scarlet orchid]

hi

i have a homework question that’s about graph theory and i just don’t

know how to prove it

i understand when this can be true, but don’t know how to make a proof that applies to all like scenarios ig

[spring hound]

What does ⊥ mean there?

[vital flume]

is there more than one way to show that in a group of 20 people, there exists 2 people who have the same amount of friends

my reasoning was that for [1,n-1] you give each person [1,n-1] friends like 1 has 1 friend, 2 has 2 friends, and 3 has 3 friends...

19 has 19 friends(friends with everyone)

20 cannot have 20 friends because you cannot be friends with yourself

so 20 must have [1,n-1] friends

But here is book reasoning

Each person can have 0 to 19 friends. But if someone has 0 friends, then
no one can have 19 friends and similarly you cannot have 19 friends and no friends.
So, there are only 19 options for the number of friends and 20 people, so we can use
pigeonhole.

They prove it by contradiction, I think their proof is stronger than mine

I also arrive at a contradiction but its flawed in the sense that I don't consider 0 friends as an option

[scarlet orchid]

i ended up figuring out the question, but thanks! also, it means adjacent to

[haughty garden]

If someone knows 0 people, then by symmetry, there can’t be anyone who knows n - 1 people

We assume that “knowing” is symmetric -> if A knows B, then B knows A

[vital flume]

yea

have u seen any pigeonhole problems that require similar reasoning or can u generate one

i want to be able to solve any challenging pigeonhole problems on my quiz tmrw and that one was a challenge problem from my textbook

[haughty garden]

Consider 5 points inside a square of side length 2. Prove that there’s a pair of points whose distance is at most sqrt(2) units apart

[vital flume]

You can put 4 points in squares of 1 cm width within the larger square

If you add a 5th point it will be within sqrt(2) of those 4 points

I think thats the reasoning but I dont feel confident in it

[haughty garden]

Yep the idea is to divide the square into four smaller squares of length 1

The distance of the diagonal is sqrt(2) by Pythagoras, so any two points inside a unit square has to be at most sqrt(2) units apart

PHP problems are all very similar, you just have to determine what the pigeons and the pigeonholes are

[vital flume]

im doing a lot of them in my textbook but i dont get the reasoning of this onehttps://media.discordapp.net/attachments/903481105888452609/1043995670165594183/image.png

here is question
An inventory consists of a list of 115 items, each marked “available” or “unavailable.” There are 60 available items. Show that there are at least two available items in the list ex- actly four items apart.

there's like 4-5 of this style in my textbook that confuse me but all the other problems i have an idea of how to attempt

[next canopy]

I'm glad someone had an actual example. My mind instantly went to "you have 21 people now..."

[rustic harness]

Hi there! I have a question about graph theory:

It's about a problem that I guess is an application of the chinese postman problem, but in a weighted undirected graph. Doing some research I found an algorithm for finding Eulerian cycles in a graph and it probably solves my problem, it's the Fleury Algorithm. But my question is:

In the case of the graph I mentioned, I'll probably have to turn it into an Eulerian Graph, adding or removing edges to make all nodes even, am I right? But should I consider the weights in that equation? I mean, I guess I can just ignore the weights since I think they just add the idea of cost to travel across an edge. Is that way of thinking correct?

I can attach a draw I made to better visualise my problem

[haughty garden]

I imagine they want you to appeal to Fermat’s little theorem since your modulus is prime, which makes it not too bad to actually list out your inverses

[desert ibex]

Isn't there a theorem here?

The solution for chinese postman theorem is just the sum of weights of all edges + the minimum weight matching between vertices with odd degree in the reachability graph

[rustic harness]

hmm, thanks! I guess I got it, googled it and found a detailed explanation

thanks a lot

[weary tiger]

Is it just x^1 = 1 mod 17, x^2 = 2 mod 17, x^3 = 3 mod 17?

[haughty garden]

Since you know that $1 \leq x \leq 16$, $\gcd(x, 17) = 1$. Therefore, Fermat's little theorem tells you that [ x^{16} \equiv 1 \pmod{17}.] More generally, for prime $p$ and $a$ coprime to $p$, we have that [a^{p - 1} \equiv 1 \pmod p.]

[haughty garden]

Therefore, for $k \in {1, 2, \dots, 16}$, you can write [x^{16} = x^k \cdot x^{16 - k}]

[weary tiger]

When simplifying congruences it it legal to take sqrts? Say=> x^2 =~ 36 mod 397 .... so x ~= 6 mod 397 ?

[unreal stump]

Wdym by =~36

[unreal stump]

Only if the base is prime

[sudden minnow]

even then no because x can also be congruent to -6, as what would happen when dealing with square roots in general

[weary tiger]

rip ok

[sudden minnow]

can consider very simple examples

1 and p-1 when squared are always congruent to 1 mod p

[weary tiger]

$x^2 * 20^{396} \pmod{397}\equiv 4800 \pmod{397}$

[unreal stump]

Well yea you need the positive and negative roots

[vital dew]

OA

[weary tiger]

Not sure how to simplify this further then 😦

[peak vine]

since i dont have access to the combinatorics channel, is anyone here familiar with automatons and the nerode-relation?

[unreal stump]

Use ||Fermat's little theorem||

[weary tiger]

It'll be $x^2 \equiv 4800$ yeah

[vital dew]

OA

[unreal stump]

Yes

[weary tiger]

So I can use positive and negative?

it simplifies to -6 and 6 then

[unreal stump]

Since 397 is prime yes

[weary tiger]

awesome so it works then. Thanks

[sudden minnow]

x^2 congruent to 36 means x^2 - 36 congruent to 0

by difference of squares, (x-6)(x+6) is congruent to 0

primality of 397 is important here, since this is what guarantees it has no zero divisors

say, if this was mod 6

2*3 is congruent to 0

but for prime you cant multiply two nonzero integers and get something congruent to 0

so, x has to be congruent to 6 or -6 for this relation to hold

[stiff fossil]

hey can anyone help me with these questions

i can't get part a, b or d

[vital flume]

im also taking discrete so ill try to help

[stiff fossil]

thankyou i appreciate it

[haughty garden]

It might help to reduce both sides modulo 22

[weary tiger]

Oh interesting, so I get 2s = 2t mod 22 then... assuming I did it correctly @haughty garden

[unreal stump]

So you get 22 | 2 (s-t) which means 2(s-t)=22k

Which means (s-t)=11k or s=t mod 11

[dire stag]

Any good ways to prepare for discrete math?

I'm a college freshman

hello

[oak yacht]

Can you prove that in a 7x3 board filled with black and white tokens, there will be at least a rectangle whose vertices have the same color?

With the dirichlet principle

[weary tiger]

I can suggest the book: An Invitation to Discrete Mathematics by Matousek and Nesetril. It's written in a friendly way and assumes as little as possible.

[weary tiger]

Assuming you mean Dirichlet's "drawer" principle, also known as the pigeonhole principle, I invite you to consider nx2 boards and the same question. Clearly you can fill a 2x2 board avoiding monochromatic rectangles, can you do 3x2? 4x2? etc.?

[weary tiger]

So I have $a_n = 3(a_{n-1}) - a_{n-2}$ as a recurrence relation that I want to express in the closed form

[vital dew]

OA

[weary tiger]

I can't use the Linear Homogemous Recurrence relation as I get $r^2 - 3r + 1$ which has an unidentified root

Could anybody tell me why this basis step isn't valid? I thought they did this exact same thing in theorem 5.2.3 in the book.

[vital dew]

OA

[weary tiger]

I don't see the difference here:

[unreal stump]

What's an unidentified root

You get 2 real roots

[weary tiger]

Never mind I solved it, using quadratic equation lol

[unreal stump]

Well you can't just assume the identity for base case

[weary tiger]

How do you mean?

[unreal stump]

I mean this is an annoyingly small distinction here

You are supposed to take LHS of P(0) and RHS of P(0) and evaluate them separately and finally conclude they are equal

[weary tiger]

right

[unreal stump]

In the first case they assumed the identity holds automatically for case 0

And just plugged 0 in the equation

[weary tiger]

I don't get what you mean. They plug 0 into the actual theorem itself aswell for the basis step?

Do you mean that they don't also do the inductive step?

[unreal stump]

Ok, actually I have no idea

[weary tiger]

And prove it for K+1 aswell?

[unreal stump]

Both are equivalent

[weary tiger]

mhm, okay

thanks anyway

[weary tiger]

yo. having troubles proving my relation. \
{1, 5, 19, 65, 211, 454} ... \
Recurrence Relation: $a_0 = 1, a_n = 2*a_{n-1} + 3^n$ \
My closed form solution is $a_n = 3(n-1)+2^{n-1}$ \
Base Case: n = 1, 1=1 Checks Out. \
Inductive Step (n+1): \
$a_{n+1} = 2a_n + 3^{n+1}$ \
$a_{n+1} = 2(3(n-1)+2^{(n-1)})+3^{(n+1)}$

[vital dew]

OA

[weary tiger]

Not sure how to continue from here

[unreal stump]

Your solution is not correct

Like the guess itself is not correct

3^n=3^{n+1}-2 * 3^n

Think how this can be used to reduce to the problem to the form of b_n = 2 b_{n-1} doing some substitution b_n = f(a_n)

||a_n = 3^{n+1} + 2^n (a_0 -3)|| should be the closed form

[weary tiger]

What's the (a_0-3) mean?

Ahh damn, my solution was initially 3(n) + 2^n if a_0 = 1, but I am not sure you can have a base case in a closed form....

[unreal stump]

Well 1-3=-2

That expression just reduces to a_n =3^{n+1}-2^{n+1}

[weary tiger]

anyone here

[weary tiger]

Wow, you're great at this. Thanks so much, I genuinely appreciate it

[weary tiger]

Guys what does this mean?

Please help

[south snow]

Which part

[weary tiger]

What does this line mean? l

such that ?

In the a,b l a=b or a= -b

[weary tiger]

That’s what it means?

(a,b) such that a=b

yes

What is such that?

(a,b) where the following property holds

(a,b) where a =b or a=-b

Ah I thought such that meant something like multiplication or dividing thingy now it makes a bit sense to me

So the r1 r2 r3 are rules right? Like condition where if this set is that than it’s r3

Am I correct? @weary tiger is that what it is supposed to mean

yes i think you got it?

its more like R1..R3 represent sets

so like R1 = { (1,1) , ( 2,2) , (3,-3) , (-4,4)...}

and if it meets that rule defined after the | then the ordered pair is in the set

Oh makes sense man thanks for the help when I looked at it looked complicated and weird looking because of weird signs I never seen why is math looks hard but is easy

relatable, i just learned this like on saturday so im in the same boat

Oh neat

Is there websites that make math be fun and easy to learn?

[weary tiger]

Also is the division sign in r4 and r5?