discrete-math

[prisma lily]

sure

[random sparrow]

,, \begin{cases} d \mid 7 \cdot 3^n-5 \cdot 5^n\
d \mid 3 \cdot 3^n+6 \cdot 5^n \end{cases}

[prisma lily]

anyways you don't have to use induction

one idea is to treat 3^n and 5^n as symbols kinda

so you have 7x - 5y and 3x + 6y

[random sparrow]

yeah exactly

[coral parcel]

What does it mean for d to divide a non-integer?

[random sparrow]

dude

[prisma lily]

now you can find linear combinations of these two expressions that amount to some multiple of x and some multiple of y

[random sparrow]

. is cdot

[vital dew]

Renato

[random sparrow]

help

[prisma lily]

hint: let A := 7x-5y and B := 3x+7y

try looking at 7A+5B and -3A + 7B

you should be able to do the rest

[random sparrow]

help

[prisma lily]

?

[random sparrow]

7R1+5R2

[prisma lily]

what's that..

anyways let me know what you get for those

[neon harbor]

try "SOS" or "mayday mayday" if you wanna switch it up

[random sparrow]

why is that

[prisma lily]

why is what

[random sparrow]

7a+5b

i was thinking 6A + 5B

[prisma lily]

there's a typo in your expressions

B is 3*3^n + 7 * 5^n

you wrote 6

[random sparrow]

True thanks

,, \begin{cases} d \mid 7 \cdot 3^n-5 \cdot 5^n\
d \mid 3 \cdot 3^n+7 \cdot 5^n \end{cases}

[vital dew]

Renato

[random sparrow]

@prisma lily

[prisma lily]

yeah, simplify it more

[random sparrow]

49+15=64

[prisma lily]

and then compute their GCDs

anyways yeah you were on the right track earlier so if x is the gcd of A and B then x | 64 * 3^n and x | 64 * 5^n and so x | 64

[coral parcel]

The very first thing to do would be to concretely compute the gcd for n=0, 1, 2, 3, in the hope of getting an idea of what the two values the problem speaks about are, and how they're distributed in the sequence.
Perhaps the gcd has one value for n=0 and another for all other n?
Perhaps the two values alternate strictly for odd versus even n?
Know what it is you're going to prove before you get bogged down in how to prove it.

[random sparrow]

in my class n startsfrom 1 but yeah good tip

[random sparrow]

yeah, x divides 64 and x divides 3^n and x divides 5^n, but i think i did a mistake in my calculations

idk how to continue though

d must be a positive divisor of 64

where d is the gcd(left, right)

but there are like 7 positive divisors of 64

also, odd + odd = even

well trying out different n i get that the gcd is either 2 or 4

[scenic mesa]

yeah i got that too

then i looked at stuff mod 8

[cunning plank]

||if both are divisible by 8 u get that 5^(n+1) + 3^n = 0 (mod 8) and 3^(n+1) = 5^n (mod 8) i think||

||(3^n, 3^n+1) = (1,3), (3,1) (mod 8) and (5^n, 5^(n+1)) = (1,5), (5,1) (mod 8)||

oop lemme spoiler

mb

[scenic mesa]

if both what are divisible by 8?

[cunning plank]

||you get that 3^(n+1) = 5^n = 1 (mod 8) and 5^(n+1) = 5 (mod 8) and 3^(n) = 3 (mod 8)||

||but this leads to a contradiction, since 3^(n+1) = 5^n = 1 (mod 8) implies both n and n+1 are even. Thus, it is impossible for this system of congruences to hold and for 8|gcd(7*3^n-5^(n+1), 3^(n+1)+7*5^n)||

pretty simple finish if you js look at residues of 3^n and 5^n mod 8 i think

[scenic mesa]

7*3^n-5^(n+1) and 3^(n+1)+7*5^n ?

[cunning plank]

uh

is this not it?

[scenic mesa]

that's the problem, yeah

[cunning plank]

yeah

that should be done then

[scenic mesa]

how did you get 5^n = 1 (mod 8) ?

this fails if n = 1 for example

[cunning plank]

5^n = 1,5 (mod 8)

3^n = 1,3 (mod 8)

we have the system of congruences 5^(n+1) = 7*3^n (mod 8) and 3^(n+1) = 5^n (mod 8) right?

[cunning plank]

this basically says that the possible values of 5^n (mod 8) are 1 and 5

[scenic mesa]

oh 1 is common

[cunning plank]

yes

so this forces 3^(n+1) = 5^(n) =1 (mod 8) right?

[scenic mesa]

yes

[cunning plank]

in order for 5^n = 1 (mod 8) --> n is even

in order for 3^(n+1) = 1 (mod 8) --> n+1 is even --> n is odd

contradiction

[scenic mesa]

that works

[cunning plank]

wdym that works

you can't simultaneously have n being even and odd

[scenic mesa]

i mean i agree that your solution is correct

[cunning plank]

oh alr mb

[scenic mesa]

no worries

[cunning plank]

is htis what they coverin discrete math?

feels more like quite elmeentary nt

[scenic mesa]

idk i guess it has overlap

check the channel description

[cunning plank]

oh alr

[tardy tangle]

I'm working on developing a branch of mathematics around the combinatorics of NOR gates. The magical thing about NOR gates is that, given enough of them, they can be used to compute anything that is computable. They can also be used to store "state", by cross-coupling a pair of them. I'm trying to figure out the math needed to calculate how many possible ways there are to create a circuit from a given number of NOR gates, excluding symmetries. It's a really interesting problem. I also need to find a way to iterate over the set of all possible ways.

The starting point is to determine how many different ways there are to subdivide a set of a given size. That is tricky though.

If I can figure all this out, it might help in solving P=NP.

[lunar delta]

its js basically making a supercomputer out of nor gates
https://www.claymath.org/millennium/p-vs-np/
Read this problem statement again, there can be possiblities even greater than the atoms of the universe( so basically ur approach is brute force, which wont work) even if you figure out there are n possibilities, lets consider the set A,where A BELONGS TO N so basically even if u figured out the n ways/possiblities, and you keep on dividing them, it will eventually lead to a reminder of 0. What are you actually trying to do here? Maybe learn some proving techniques first.

[odd garden]

So when we found that 0 < t <= n, how was |x| = 0 ? Does this proof only work with the case where x is epsilon?

[humble nova]

|x| may be 0 but it might not be. It's just saying that y is some number of 0s in the range of more than 0 and less than or equal to n.

well... i should add that $|xy| \leq n$ which means that $|x| \leq n$ too. but not much else is said.

[vital dew]

thyrgle

[odd garden]

And |y| can at most be n, which means |x| is 0. But if x was not zero then “ t” has to be even smaller?

[humble nova]

Yeah, but you don't really know what t is exactly. Just that $0 < t \leq n$. But it's fine. The whole string has length $n^2$ so you know $xyyz$ is $n^2 + t$ in length. You're just giving a name to the length of y.

[vital dew]

thyrgle

[dire bough]

#chill

[terse quartz]

Can i have a vague hint here? I think the answer is yes, there always exists such a path, but I tried proving it by induction, which collapsed it into a bunch of cases, some of which i’m not sure how to prove and i feel like there must be a simpler approach. Im not sure how id do contradiction

[little prism]

if you have a path that works you can easily switch the colors around so that it doesnt anymore. I am unsure about why such a recoloring should produce a new path that works

so at least I dont share your feeling that the answer is yes

[weak stirrup]

u can assume there is no path with all k colors and then consider a path P that is maximally colorful meaning it has the most distinct colors possible lets say m<k. think about the properties of the endpoints of this path specifically of what colors must their neighbors have, given that P is maximal? key step is to then take a color j thats missing from P and look at the subgraph of vertices colored with j and the color of an endpoint of P by cleverly swapping these two colors in just one of that subgraph's connected components (a Kempe chain) you can create a new valid coloring that forces a contradiction
the idea is that extremal argument involves selecting an object that maximizes or minimizes some property ( the longest possible path or the smallest counterexample etc etc) to analyze its rigid structure anyways Kempe chain argument is then used as a tool on this extremal object it cleverly swaps two colors within a specific connected component to create a new valid coloring that contradicts the assumed properties of the extremal object !
https://en.wikipedia.org/wiki/Kempe_chain

[little prism]

(it didnt only ask about a path that contains all colors. it asked about a path that contained all colors in order. that feels much harder)

[terse quartz]

thank you! 🤗

[weak stirrup]

hmm yeaa i didnt notice that .. proof for that requires a specific counterexample and the extremal/Kempe chain argument doesn't apply then It turns out that you can construct a k-chromatic graph and give it a valid k-coloring where a path with colors in that specific ascending order is impossible i think counterexamples are a bit tricky to build but ig they do exist

yea i think stronger "in order" would be false too @terse quartz as denascite said

[terse quartz]

hmm

this is a mandatory q on a 3rd year UG sheet im not sure it should be

i'll try proving the non-ordered case for now

[little prism]

if its wrong then there is a decent chance that there is a small counterexample which you could find

[pulsar matrix]

looks like it

[little prism]

given that its in an UG sheet

[weak stirrup]

ok i am thinking of using this somehow https://en.wikipedia.org/wiki/Gallai–Hasse–Roy–Vitaver_theorem
@terse quartz
theorem more formally states that the chromatic number of any graph G, χ(G), is less than or equal to the number of vertices in the longest path of any of its acyclic orientations maybe call the number of vertices on the longest path in your DAG D as m. The theorem says
χ(G) <= m

lemme think about it

maybe we can use idea like to convert the undirected graph G into a Directed Acyclic Graph (DAG) by making every edge point from the lower colored vertex to the higher colored one GHV theorem guarantees that the longest path in this DAG must contain at least χ(G)=k vertices by the very way we directed the edges this long path is forced to have its colors appear in a strictly increasing sequence, giving you the required path of colors 1,2,…,k maybe

but i havent thought about it much its just crude statement

[coral thunder]

Does binomial theorem come under discrete mathematics? I have a question

Well this is the question

[jagged sun]

I'm still wondering the exact cause of the discrepancy between TREE(2) and TREE(3). It seems like some combinatoric explosion happens, resulting in TREE(2) having 3 nodes and TREE(3) having an extremely large finite amount of nodes, far beyond human comprehension.

[coral parcel]

As the example here suggests, the color of the single node in T1 cannot be used in the rest of the sequence, so all the rest of a sequence for TREE(2) need to use just one color, which doesn't leave much room for what happens in the first few steps where there are tight limits on the size of the trees.
TREE(3) gives us two colors to play with in the rest of the sequence, which is enough to survive that initial bottleneck where the trees have to be small.

[lethal laurel]

Hello everyone, I just starting my first class in Discrete Math, and I’m learning propositions. I have a question asking if these are propositions and what the truth values are of those that are propositions. Here are some examples that I’m stuck on:

• Do not pass go.
  This isn’t a proposition because it isn’t either true or false, right?
• 4 + x = 5 (another similar example is: 2^n is greater than or equal to 100)
  I’m not sure what this one is, because it’s not necessarily true or false again
• The moon is made of green cheese.
  This one is a proposition because the statement is clearly false. But what do I put for the “truth value”?

-# Please ping whenever replying!

[spare slate]

"Do not pass go." is not a proposition.

"4+x=5" is also not a proposition because it is not definitively true or false. Similar for "2^n is greater than or equal to 100." You could say that they're open sentences though.

"The moon is made of green cheese." is a proposition. You also said the truth value yourself - it's false.

[lethal laurel]

Ah I see, so it has to be definitely true or false without adding in extra factors

And the truth value makes sense, I thought it was like part of the sentence or smth 😂

Thanks for the help!

[spare slate]

[primal grove]

Created this fun algorithm that builds a set of all valid UPC numbers, check it out :

[grim wave]

How do you guys find practice problems for theory slides that a professor might give?

I have been trying to find decent NFA practice problems for my theory of computation class but can't seem to find anything that's on topic (simple enough for me to understand with what I currently know)

I guess more practically I need practice with converting an NFA to a DFA

[terse quartz]

this might be a bit of a longshot, but has anyone seen a probabilistic methods problem involving vertex transitivity in a graph anywhere? It was available on this sheet https://n.ethz.ch/~ywigderson/math/static/Probabilistic_method_HW.pdf but that link is now broken :((

i couldnt find it in alon/spencer

[weak stirrup]

Let G be an n-vertex, d-regular graph.
(a) Fix some parameter p ∈ [0,1] that we'll pick later. Let S be a random subset of V(G) obtained by taking each vertex independently with probability p. Let X = |S|. Prove that E[X] = pn.
(b) Let Y denote the number of edges in the subgraph induced by S. Prove that E[Y] = p²nd/2.
(c) Pick p to maximize E[X − Y], and conclude that G has an independent set of size at least n/(2d)

I can open the link lol

it looks it involves vertex transitivity to me

[terse quartz]

Wait what

[weak stirrup]

yes

[terse quartz]

I'm not sure what's going wrong on my end then

Thanks though! Any chance you could send the pdf perchance?

Maybe I'll try using a vpn

[weak stirrup]

use screenshots cuz pdfs wont open again ig ?

[terse quartz]

ok cool. Tysm !!

[weak stirrup]

can u open it ?

[terse quartz]

yep

[cunning plank]

Number one is cool it relates to like information theory and Huffman codings and stuff

[tired summit]

I love the 4th one

[scenic stone]

can somebody help me with my combinatorics homework? i tried using desmos but i couldn't figure it out

[sharp sundial]

Desmos uses nCr()

nCr(3,2)

[north pilot]

nCr(=,1).6 didn't work for me

[cloud rampart]

what would "equals choose 1" even mean

[coral parcel]

(Equals choose 1) point six, even.

[random sparrow]

guys, how does this property work?

where (a:b) denoted gcd(a,b)

[warm summit]

say that again

[coral parcel]

I'm saying I don't know what the postfixed .6 in the screenshots is supposed to mean.

[random sparrow]

help please

[warm summit]

six _even

[north pilot]

desmos doesnt work idk

[weak stirrup]

please screenshot specific thing u r asking about

[random sparrow]

I already did that? 🥀

[weak stirrup]

i dont get it what r u asking first of all screenshot isnt in english write out ur problem statement maybe ?

is it what it is ?

[random sparrow]

ye

how does this work?

the translation is this ^

[vital dew]

Yuxuan Wang

[weak stirrup]

@random sparrow what u dont get specifically here

[random sparrow]

its the fact that beta is smaller than alpha for each i

something related to fta, it seems?

well, otherwise the number m would be greater than n

something like dat?

[neon harbor]

Ah yes, $n = pp \underset{written}{its} \overset{k}{\underset{i=1}{prime}}$ factorization

[vital dew]

sheddow

[weak stirrup]

reason for $\beta_i$ of a prime in a divisor $m$ must be less than or equal to the exponent $\alpha_i$ in the original number $n$ stems directly from the definition of divisibility and the uniqueness of prime factorization guaranteed by the FTA as u said . by definition, if $m$ divides $n$ (denoted $m|n$), then there must exist an integer $c$ such that $n = m \cdot c$. Expressing each integer by its unique prime factorization over a common set of primes ${p_i}$ gives us $\prod_{i} p_i^{\alpha_i} = (\prod_{i} p_i^{\beta_i}) \cdot (\prod_{i} p_i^{\gamma_i})$, which simplifies to $\prod_{i} p_i^{\alpha_i} = \prod_{i} p_i^{\beta_i + \gamma_i}$. due to the uniqueness of this factorization, the exponents for each corresponding prime base $p_i$ on both sides of the equation must be equal, which yields the relation $\alpha_i = \beta_i + \gamma_i$. Since $c$ is an integer, its prime exponents $\gamma_i$ must be non-negative (i.e., $\gamma_i \ge 0$), which forces the necessary conclusion that $\beta_i \le \alpha_i$ for every prime factor $p_i$

[vital dew]

Yuxuan Wang

[weak stirrup]

n = pp is killing me

[odd garden]

Write a regular expression for the following languages . Note that ∑ = { 0,1 }
L = { w = 01 ∈ Σ * | i is even and j is odd }

Is (00)^* 1 (11)^* the correct regular expression?

[weak stirrup]

looks correct

[lusty steppe]

can someone help me with this, I do not know if am doing it right

here is my working:

can anyone confirm if I am doing it right so far and if so, how do I do the rank proportionate ?

[coral parcel]

There seems to be a lot of context missing here. It's not clear what "minimize x², x is between [-4,4]" (which has the obvious answer x=0) has to do with the rest of the text which doesn't even mention x or squares or anything.
I suppose this might be about some particular optimization algorithm where somehow 0100, 1101, 0001, 0010 have been chosen as candidates for the minimizing x (even though, perplexingly, the correct answer 0000 is not among them), and then apparently something probabilistic happens ... but since you're not describing what that algorithm is or how it works, it would be pure guesswork to say whether what you're doing is right.

[coral parcel]

This sheds some light on what you're doing, at least the first part where you're implicitly selecting 16 equidistant values with the first one being -4 and the last one 4 (but then only choosing four apparently random "individual" points among those sixteen to deal with?). However whether "what you're doing" is the same as what you're supposed to be doing is anyone's guess.
In the second part it appears your conclusion is four "probabilities" that don't sum to 1, which can hardly be right.
Perhaps the answer to that is that the 12 other possibilities other than #4, #13, #1, #2 contribute the rest of the probability up to 1? However, that can't be -- if one does the analogous as you did for I_1 with #8 (1000) instead, that would yield a "probability" of 14.063, which is absurd.

[native wind]

I'm taking logic and algorithms I'm having difficulty concentrating its just so incredibly uninteresting to me the content is really boring.
is this math topic supposed to feel this way?

for example I found calculus 1 and 2 very interesting yet hard but I did really good in that subject. I didn't struggle as much as I am in logic right now.

does logic get any better further on?

[cerulean wind]

what subjects are you covering in your class?

[native wind]

We just started proofs

I'm just not feeling that satisfaction after solving something like in pervious math subjects so far anyway.

[paper scaffold]

Discrete maths mentioned

They forced me to take this shit against my will

I'm not even a math major

Cs major

[coral parcel]

That's the typical audience for a "discrete mathematics" course. In some institutions, taking enough actual math courses can substitute for the discrete-math course.
Those courses generally consists of "the minimal amount of math CS majors need to know, but it's scattered across a lot of different courses if you follow the actual math curriculum, so here's a quicker way to get just the minimum".

[paper scaffold]

I guess discrete maths has dijkstra and graphs lmao thas all

And set logic

If they trim the whole course to just those 3 I would never complain

[solid ibex]

Or just learn everything to have a deeper understanding of the stuff that is useful to you

[slim geode]

Hi guys, is it possible to approximate the number of restricted integer partitions?

Using normal distribution

The question is, what is the number of partitions of k into n distinct parts such that each part is in [1, m]?

From what I found, there isn't a closed form solution for this, but fortunately I think there is a possible way to approximate it (which is enough for my use case).

So what I can do is I can flip the question around. Instead of asking how many of these partitions exist for k, I ask how many partitions can exist regardless of what they sum to. This means I want n distinct addends between 1 and m. This means the total number of partitions is mCn.

Out of these partitions (or combinations), the smallest number they can add to is n(n+1)/2 and the biggest number is nm - n(n-1)/2. But of course, there will be only one way to sum to the smallest or the biggest number. The more the number is in the middle between the two extremes, the higher number of the partitions will sum to that number.

If we plot the number of partitions that sum to a given number, we'll get something which resembles normal distribution. For example, this is what it would look like for n=3 and m=9:

Then if I wanted to know the fraction of these partitions that sum to let's say 15, I could maybe approximate it as the blue area here?

And so I have a few questions:

• for given n and m, what would the parameters σ and μ in the normal distribution function
• for a given k, is it then possible to get the blue area as a closed form solution, at least approximately?

[rotund swan]

I need help understanding pummping lemma for regular languages

[paper scaffold]

I'm not quite sure with transitivity help

I lowkey brute forced that shit

[random sparrow]

transitivity is x R y, y R z => x R z

[paper scaffold]

I mean with self loops and shit

[random sparrow]

what about the self loops

[paper scaffold]

how is the 3rd one transitive

[random sparrow]

1 R 1, 1 R 2 => 1 R 2

check for all x,y,z such that x R y, y R z

[random sparrow]

4 R 1, 1 R 2 => 4 R 2

check for all x,y,z such that x R y, y R z

[random sparrow]

intuitively it should be a shortcut path between the three numbers

[paper scaffold]

I'm referring to this one btw how is it 4 R 1

[random sparrow]

oh fuck i misread again

[paper scaffold]

2 R 1, 1 R 1

[random sparrow]

2 R 1, 1 R 1 => 2 R 1

[paper scaffold]

oh yeah that acc make sense

[random sparrow]

3 R 1, 1 R 1 => 3 R 1

[paper scaffold]

how bout this I assume the same shit happens

2 R 3, 3 R 3 => 2 R 3

then

4 R 3, 3 R 3 => 4 R 3

[random sparrow]

yeah

nice job

[paper scaffold]

think there are some other cases that I can't fool proof yet lmao

[random sparrow]

also 4 R 4, 4 R 1 => 4 R 1

[random sparrow]

wdym?

[random sparrow]

4 R 1, 1 R 2, but not 4 R 2

[random sparrow]

try to find a counterexample

[paper scaffold]

oh i see

this one's transitive cause there's no "double path" to begin with?

whats the term again

[random sparrow]

this one is transitive because x = y = z

3 R 3, 3 R 3 => 3 R 3

[paper scaffold]

imagine the dots as is no arrow no self loop

would that be transitive?

[random sparrow]

no self loops?

[paper scaffold]

like just dots

[random sparrow]

so basically not even a relation?

[paper scaffold]

no path no circular arrow

[paper scaffold]

yes

would that be transitive

how bout this

how do you disprove that this is not transitive

3 R 4, 4 R 1, 3 R 1 ✅

1 R 2, 2 R 2, 1 R 2 ✅

[random sparrow]

i think the empty relation is transitive

[random sparrow]

https://math.stackexchange.com/questions/690482/is-the-relation-r-emptyset-reflexive-symmetric-and-transitive-why

[paper scaffold]

these 3 are transitive

[paper scaffold]

which confirms that

[paper scaffold]

now moving on to this☠️

[random sparrow]

3vR 1, 1 R 2, but not 3 R 2

[paper scaffold]

oh yeah totally overlooked that

make sense

[random sparrow]

you made quite an interesting question with the empty relation question dude, i appreciate it

[paper scaffold]

imma try to make my method as fool proof as possible lmao

[random sparrow]

it's not reflexive but it's transitive by vacuous truth

[random sparrow]

yeah, i think so

[random sparrow]

for me its transitive unless you find a counterexample

and i can't find a counterexample for this

[random sparrow]

just try to find a counterexample

it's faster than checking all the pairs

ideally you would check all x,y,z to follow x R y, y R z => x R z

[random sparrow]

for me i go like, trying to find a counterexample, otherwise i go to check all the pairs

[paper scaffold]

this shits also correct

transitive

[random sparrow]

yeah

4 r 4, 4 r 4 => 4 r 4

[paper scaffold]

for this one tho, 2 R 1, 1 R 4, 2 not going to 4

[random sparrow]

yeah that is not a transitive relation

[random sparrow]

nice, good job

[paper scaffold]

I'm getting good at ts

@random sparrow do you happen to know this uni called unsw lmao

[random sparrow]

no, from where is it

[paper scaffold]

australia

[random sparrow]

is it the unfamous waterloo?

[paper scaffold]

nope

[random sparrow]

you attend there?

[paper scaffold]

why are these symmetric???

[paper scaffold]

ofc

yes

[random sparrow]

symmetric definition is x R y => y R x

can you find a counterexample for symmetry?

[random sparrow]

2 R 2 => 2 R 2

[paper scaffold]

if there's no relation at all?☠️

would it be symmetric?

[random sparrow]

what? you mean the empty relation on a nonempty set

for example R = {} on the set A = {1,2,3}

[random sparrow]

if none of the elements on A relate, x R y => y R x, is a tautology

[paper scaffold]

symmetric and transitive but not reflexive

[random sparrow]

thought for 18 sec lol

[paper scaffold]

4 R 3, 3 R 1, 4 R 1 ✅
4 R 2, 2 R 2, 4 R 2 ✅

think thas all to prove transitivity?

[paper scaffold]

thinkin model, the instant model would prolly thought for 3 seconds

[random sparrow]

well ideally you try all x,y,z

but yeah i can't find a counterexample

this must be transitive

[random sparrow]

in order to prove it you need to check all of x,y,z

[paper scaffold]

3 doesn't go to 1 therefore not transitive

3 R 4, 4 R 1, nope

[random sparrow]

yeah 3 doesn't relate with 1

nice job

[paper scaffold]

allat just for 2 marks

2/20

[random sparrow]

well the empty relation on a nonempty set is not symmetric, but it's symmetric and transitive, but a empty relation on a empty set is an equivalence relation (reflexive, symmetric and transitive )

[paper scaffold]

@random sparrow I skipped all the lecs are you familiar with euclid algo and modular congruence

[random sparrow]

actually, i have exam tomorrow about it (congruence and euclid) but i think i will fail

sorry i can't be of any help, maybe ask your question and someone will help

[paper scaffold]

I'll have an exam about graphs (the ones we've been discussing), congruence and euclid, power sets, and gcd lcm thang all in one

[random sparrow]

same, I'm giga cooked

gcd lcm aswell there's just so many properties

[paper scaffold]

think I can reliably get 10/20 now with the question bank

they are recycling the questions at least

[random sparrow]

yeah same for me

but like, my exam comsists of 4 problems for 4hr

[paper scaffold]

exam in 2 days

[random sparrow]

is it a final or a midterm?

[paper scaffold]

mid term

[random sparrow]

same lmfao

[paper scaffold]

my uni has trimesters

@random sparrow wats ur uni

[random sparrow]

it's not known, i go to University of Buenos Aires in Argentina

[random sparrow]

mine works in semesters of 4 months

[paper scaffold]

javier milei reference

btw is he in good terms with stem education funding and shit

javier milei

[random sparrow]

he is the devil

[paper scaffold]

oh yeah we prolly shouldn't discuss politics in this server lmao

imma just say that he's a funni man

[random sparrow]

good luck btw 🤞

[paper scaffold]

how is this not transitive?

[lone bridge]

2→3 is present
3→2 is present
but 2→2 is absent

[ebon spruce]

Hey everyone, i think this fits here because its DSP. I understand why in the DT complex expontentials, frequencies only map to [0. 2pi], and everything outside is the same. What I don’t understand is why this doesn’t apply to the CT case. I intuitively understand that the reason is that “n” is an integer and “t” is a real number, but my algebra just isn’t matching up.

[weary tiger]

In the end, if t = 0.25, then the term which you wrote as 1 in the multiplication becomes e^jpi/2, which is not 1.
This does not work like this for real numbers — you have to use the definition e^{jtheta} = cos(theta) + j*sin(theta).

[timber elm]

Can anyone help me with finding all solutions of the deck? I can see that I have 7 vertices, 6 edges, three of the vertices have degree 1, three of the vertices have degree 2, and one vertex has degree 3.

[coral parcel]

What does "solution" mean in for you here?

[timber elm]

I believe it means the original graph.

[coral parcel]

Could you show the entire problem description?

[timber elm]

this one is the entire question

[coral parcel]

Thanks.

"Solution of a deck" is not standard terminology, but the problem text clarifies.

Card 2 must be what results when the degree-3 vertex is deleted, and there's only one way to connect the three fragments to the missing vertex without creating another degree-3 vertex.

[odd garden]

Hello

Give a context-free grammar for the following language

{a^i b^j c^k d^t : i + j = k + t}

How can I approach this problem. I have no clue how to start

[coral parcel]

Well, if it were { a^i d^t | i = t } the standard solution would produce parse trees of the form

  S
 /|\
a S d
 /|\
a S d
 /:\
a : d
  S
 /|\
a S d
  0

We need to let some of the a become b and some of the d become c, and some mechanism to ensure these variations happen in an allowed pattern. A strategy for this could be distinguish several different nonterminals in the "spine" other than just S, encoding what is allowed at each level.

[solid shuttle]

hello! struggling to get a good start on this
i was thinking if we set X(G)=m, then we can say that when we add in 1 vertex of H to this graph, we now need m+1 colors. adding in another vertex of H, if this vertex is connected to the first, then we need m+2 colors, otherwise we can still use m+1. I tried to continue this for all of H, but I realized this is using the greedy coloring algorithm, so I don't think it helps.
a hint / push in the right direction would be nice

[cunning plank]

consider a vertex of G, which is connected to all vertices of H. If you consider the set of colors across all colors of H, the colors invovled will be c_1, c_2, .., c_(x(H)). Essentially, the size of this set will be x(H) (chromatic number for H). Therefore, we must color this vertex of G some color that is not any of these colors. Try extending this idea for all vertices in G.

oh its basically what you said

just consider coloring the vertices of G in such a way where ||none of the colors used are in the graph H||

[solid shuttle]

i understand coloring them in a way where none of the colors used are in H, since otherwise it wouldnt be properly colored
what i dont know how to formally state is that we can do this with exactly the chromatic number of colors of G

[weary tiger]

Let's say chromatic number of join graph is c3 .
chromatic number of G is c1 , chromatic number of H is c2 .
Just show c3 >= c1 + c2 and c3 <= c1 + c2 .

1.  c3 <= c1 + c2  ,        it is easy just use different colours for H and G and colour the join graph . 
   

2. c3 >= c1 + c2 , show by contradiction . Let us say you can colour join graph using c1 + c2 - 1 colours , then you should be able to colour the vertices of either G by <= c1 - 1 colours or H by <= c2 - 1 colours inside the join Graph . Let's say for G this is true , then remove all the vertices of H from join graph , you will get a coloring of G using <= c1 - 1 colors which is a contradiction.

[cunning plank]

You can formally do it by definition I believe

For example, let chromatic number of H be 3

Then when coloring the graph of H, we use up 3 colors

And none of these colors can be used when coloring G

As stated above

Let the chromatic number of G be 4

Then, 4 colors are needed to color this graph

But none of the colors used can be from graph H

So we must use 4 new colors

The join graph can basically be viewed as a sort of bipartite graph, where instead of joining graphs with chromatic numbers of both 1, the chromatic numbers are x(G) and x(H)

[wind jetty]

hello guys i will have a exam at my college this saturday can anyone give me recommendation source for learning discrete math, i'm still learning about logical proposition, basic inference,sets, algorithm, numbers and counting. I don't know where i can find place to learn it more deeply

[coral parcel]

If your exam is on Saturday, then it's a little late to be looking for sources to learn from.

[wind jetty]

really?

i think i can chase it

by all in at friday

[verbal pewter]

u can learn from MIT ocw at youtube

[wind jetty]

i am a little bit understand about the topic, but just wanted to learn it deeply

do the more question and reference to know the question type

[wind jetty]

if i learn it then i want to do the question where can i find it?

[verbal pewter]

u can find in the resources they have attached

[wind jetty]

and i want to know is it the course teach the topic i needed right now if i start watching from the beginning

[wind jetty]

ohh okey then

so this course will need at least how many video until my topic finish?

i'm afraid i can't chase it

[verbal pewter]

what all topics u need to cover ?

[verbal pewter]

if it is only the topics u mentioned here , u can watch first 3 4 lectures

[wind jetty]

yeah this topic only that i mentioned

oh okey then 3-4 lectures maybe i can chase it start from now

thanks for the information

[verbal pewter]

yea go ahead

[flint lynx]

i'm currently studying theory of computation and was kinda stuck so idk why this question kinda motivated me to go ahead

[final shard]

How can we identify whether a function is total or not?
I looked at some examples and my reading says:
Relation R on A is total if for all x,y in A either x = y or xRy or yRx.
I put this in chat gpt and got even more lost

[wheat leaf]

can someone explain how (p^q)v ~(pvq) is not tfft

[spare slate]

I think they meant to make the last column
$$(p \land q) \lor \sim (p \land q)$$

You are correct that it would be $T, F, F, T$ for
$$(p \land q) \lor \sim (p \lor q)$$
though.

[vital dew]

Civil Service Pigeon

[paper scaffold]

can a relation be not symmetric while being antisymmetric at the same time?

does a relation have to be symmetric to be antisymmetric

does one negate the other

[cerulean wind]

yes. consider the identity relation on a set X with more than two elements and add (a,b) to the relation with a != b. then the relation is antisymmetric since aRb = bRa => a = b but is not symmetric since not bRa

[pale epoch]

all four cases should occur, you can just look at examples <=, <, = etc. on your favorite sets

another worthwhile exercise might be classifying all relations that are both symmetric and antisymmetric on a given set

[terse quartz]

what is the highlighted bit actually asking when it says classify? Ive got the bit before that

[cerulean wind]

it is asking: if a tree has exactly three leaves, what does it have to look like?

@terse quartz

[past rivet]

idk close to the end of autumn

[terse quartz]

oh fair enough? seems like a strange question

[terse quartz]

yeah its almost snowing by that point

[past rivet]

depends on where you are ig

also global warming

[cerulean wind]

that tree has two leaf nodes

[paper scaffold]

https://tenor.com/view/vietnam-vietnam-flashback-gif-27530600

Trees are also a big thang in data structures and algorithms

[paper scaffold]

Bruh wtf thas only 2 leaves

Bro's a fraud

[gusty wedge]

i hope its right channel to ask for a question of game theory

can someone help me understand this

i understood grundy value calculation

the last para

i did not understood

[cerulean wind]

#game-theory

[gusty wedge]

oops

sorry

did not saw the channel

[gusty wedge]

also what after aops vol 2 ?

which book of discrete maths should i pick up

to solve

[cerulean wind]

what are your goals?

[gusty wedge]

i am from a bad clg so i h ave to self taught myself cs

like someone at top clg level

and i guess discrete math is imp for cs

[cerulean wind]

a walk through combinatorics is a good text. it is the combinatorics and graph theory book that my class used

[gusty wedge]

so should i pick a solo book for each topics ?

or something Like Mit ocw book

btw i skipped the geometry section in vol2

as it was not aligned with my goals

I might go for masters

thats why i am taking math seriously

sorry if it sounds dumb

i can only rely on internet for guidance i have no good peers

[gusty wedge]

Ok with the help of reddit

I picked book for each topic

Thanks for recommendation

[cunning plank]

its more directed towards comp math i feel

but the combo chapters might be useful

[random sparrow]

gcd(20,16) = gcd(4,16) = gcd (4,8) = gcd(4,4) = gcd(4,0) = ?

[quick folio]

gcd(0,n) = n

[random sparrow]

according to what theorem?

[quick folio]

its not a theorem you can prove it yourself

this is because any number divides 0

[random sparrow]

care to elaborate?

[quick folio]

can you state the definition of divisibility?

[random sparrow]

a | b => b = a.k, k ∈ Z

[quick folio]

so set b = 0

and see what happens

[random sparrow]

n | 0 => 0 = n.k , k ∈ Z

[random sparrow]

i dont follow

[quick folio]

you seem to have gotten the definiton the other way around

if there exists a k in Z such that b = ak, then we say that a divides b

[random sparrow]

wdym?

[quick folio]

so because 0 * n = 0

n divides 0, where n is any integer

[paper scaffold]

@random sparrow r u majoring in compsci

[random sparrow]

yes

[paper scaffold]

Wait software engineering is a thing huh

Which I assume is way less theoretical and maths

[random sparrow]

ye, i still prefer cs

[random sparrow]

how did it went in intro to proofs exam?

[paper scaffold]

Midterm ya mean

I got 88/100

It's called a lab test in my uni

[random sparrow]

good

[random sparrow]

well in here we call it midterm, but maybe we are talking about different things, we get 4 problems in 4 hours, so I cant see a lab test lasting 4 hours

[gusty wedge]

wait should not be
gcd smaller than or equal to smaller number in gcd(a,b)

[quick folio]

It is true as long as neither of them are 0

(And negative numbers)

[gusty wedge]

yeah i did ot more cuz of competitive programming perspective

[gusty wedge]

oh did not knew that

thanks

[grand crown]

what’s your progress so far?

[untold kraken]

If $a_n =\sqrt{n}$ , $a_n \geq 1$ and let $s_n = a_1+a_2+...$ \ then find $\lim_{n\to \infty} \frac{\frac{a_n}{s_n}}{-\ln\left(1 - \frac{a_n}{s_n}\right)}$

[vital dew]

ᔕᑭOOKY ᔕᕼᗩᗪOᗯ

[weary tiger]

Seems like 0 to me

that’s just sqrt(n) / (sqrt(n) + sqrt(n-1)…sqrt(1))

an/sn would become 1

Wait

This is cooked nvm

[random sparrow]

if they are true propositions you can simplify left side until you get to right side

at least for the ones that are equalities

for the inclusions you need to grab an arbitrary element from the left side and show its included in the right side

recall that there are multiple definitions for the symmetric difference, for example A Δ B = (A∪B)-(A∩B)

another one is A Δ B = (A-B)∪(B-A)

simplify either right side or left side of the equality until you get to the other side

for the equalities

[cunning plank]

U get 0/0 so u can do lhopitals right?

And then you could probably let s_n be the integral of sqrt(n) from 1 to n as when n goes to infinity there wouldn’t be much of a difference

[coral parcel]

Not when the functions are only defined at integers. (It makes no sense to differentiate them then).

[cunning plank]

Just like rewrite s_n as the integral

[coral parcel]

If you mean an integral of a step function, that's still not differentiable enough for L'Hospital to apply.

[odd heart]

First note that a_n/s_n converges to 0; then use the fact that as x converges to 0, ln(1+x)/x converges to 1

(also why is this in discrete math? seems like more of a calculus problem)

[untold kraken]

It was under series of real number so yeah...

I got ur help
Thanks

[cunning plank]

I was saying like approximate s_n as an integral of sqrt

[coral parcel]

Well, then we'd need to estimate how much of an error that creates.
Possibly doable, but I wouldn't call it a straightforward L'Hospital application.

[elfin crown]

best channel

i love graph theory

[paper scaffold]

Is there like a coding program in uni without theoretical math lmao

I got no problem when it's applied maths when I actually need it

If I can't do it then it's entirely on me

[grand crown]

that doesn’t really mean anything

I doubt any cs program is making you do real analysis

Discrete math and algorithms is basically just applied math

if you just want to avoid doing formal proofs, that’s basically only ever going to be your algorithms class

and maybe a discrete math type class

[coral parcel]

Some "computer science" programs distinguish themselves from "software engineering" programs by wanting their graduates to have more theoretical depth than mere programmers, which will entail some proofy math, at least in the form of a "discrete math" course.

[paper scaffold]

I find my algorithms class to be way more fun and digestible than watever they throw at me in discrete maths lmao

[grand crown]

as long as you don’t take automata electives or whatever you probably don’t have to look at discrete math again after the class

You’re implicitly using it a lot in algorithms though

Mostly because “discrete math” is itself incredibly broad

I wouldn’t avoid cs programs just because they make you take a discrete math class

[paper scaffold]

which I'm getting the impression of em being like way simpler

and most importantly no moar essays

[sleek owl]

yo this has to be brainrot wtf

[fossil mural]

that's a bit of an unnecessarily symbol-pile way of putting it but under a reasonable interpretation this is in fact a reasonable definition of Q

``$[(\varnothing, \varnothing)]{(\mathbb{N}^2, \sim{\mathbb{N}^2})}$'' is the integer $0$

[vital dew]

bee [it/its]

[fossil mural]

so it's saying $(\mathbb{Z} \times (\mathbb{Z} \setminus {0}))/(\sim_{\mathbb{Z} \times (\mathbb{Z} \setminus {0})})$

[vital dew]

bee [it/its]

[sleek owl]

it makes sense but still

[true willow]

what

[sleek owl]

basically $0$ in the integers is the collection of all pairs$ (a,a)$, where $a$ is in the natural numbers (but $0$ in the natural numbers is often defined as the empty set $\varnothing$

[vital dew]

Julian

[north pilot]

And an ordering. A photograph of C is a graph. Yeah, I don't know.

[analog hound]

Are there any tricks for producing a double-counting argument from an inductive proof?

Let's say I have an identity that I get from unrolling a recurrence, and I want to interpret both sides combinatorially

Also, the recurrence is proven with double-counting

Like this (for instance). I'm not just asking how to prove 5.9 with double counting, but how to do it in a way that leverages the derivation given here, and which hopefully generalises

[sacred fern]

Is there a nice way to see how many natural number solutions (including 0) we have for $\sum_{k=1}^{N}kx_k = P$

[vital dew]

Khush

[sacred fern]

I have an idea with generating functions but that seems horrible

[spare slate]

yeah idt you're getting a nice closed formula

generating functions is what I'd do

recursion could also theoretically work, but that's even worse

[little prism]

https://math.stackexchange.com/questions/30638/count-the-number-of-positive-solutions-for-a-linear-diophantine-equation

yeah doesnt seem particularly nice

[sacred fern]

Ok thank you guys for this

I'm gonna have to do my problem another way then

[fossil mural]

you can interpret this entire derivation as being, not just a proof by double-counting, but an explicit construction of a bijection

like taking their example of 5 choose 3

if we have a set $S \subseteq {0, 1, 2, 3, 4}$ of size $3$

[vital dew]

bee [it/its]

[fossil mural]

we can ask, is 0 an element of S? if it isn't, then it's a subset of {1, 2, 3, 4} of size 3 (i.e. 4 choose 3), and if it is, then the remaining elements of S are a subset of {1, 2, 3, 4} of size 2 (i.e. 4 choose 2)

then we take the second case and break it apart again - is 1 an element of S? if it isn't, then it's a subset of {2, 3, 4} of size 2, otherwise, the remaining elements are a subset of {2, 3, 4} of size 1

if you think about where this is going - we keep asking "is the first object an element of S" until it isn't, and then stop

so now, generalising out to the entire identity

we have $\binom{r + n + 1}{n}$, meaning a subset $S$ of size $n$ of a set of $r + n + 1$ things

[vital dew]

bee [it/its]

[fossil mural]

and we set $k$ to the size of the largest initial segment of the set of $r + n + 1$ things which is in $S$ - so, the $k$ for which $i \in S$ for all $i < k$, but $k \not\in S$, assuming that our set is ${0, 1, 2, \dots, r+n}$

[vital dew]

bee [it/its]

[fossil mural]

we have $k \leq n$, because a set of $n$ things can't contain an entire initial segment of length $> n$

[vital dew]

bee [it/its]

[fossil mural]

and for each possible value of $k$, each set contains the first $k$ things, then doesn't contain the next one, then it's some subset of size $n - k$ of the remaining $r + n + 1 - (k + 1) = r + (n - k)$ things

[vital dew]

bee [it/its]

[fossil mural]

in retrospect i should not have used the variable $k$ for this value, but i hadn't realised yet that it was going to end up inverted like this

[vital dew]

bee [it/its]

[fossil mural]

but still, what we've done is rearranged our initial set into $\sum_{k \leq n} \binom{r + (n - k)}{n - k}$

[vital dew]

bee [it/its]

[fossil mural]

and then you just have to reindex it to get the original identity 5.9

[weak stirrup]

[charred mantle]

In case anyone is interested.

It is not directly stated however the answer must also be given in terms of n

Feel free to ping or DM for the answer key

[deep merlin]

I am following Hopcroft the diagram shows how he did it, but I would like to know whether there are algorithms for a direct construction of,
regex iff epsilon-NFA, NFA (epsilon-free), DFA, please point me to the appropriate term and if possible recommend some texts on it

[coral parcel]

Is he really showing a separate NFA->DFA construction, other than "view the NFA as an epsNFA that happens to have no epsilon-transitions, and use the epsNFA->DFA translation we already have"?

(Perhaps I'm misunderstanding what eps-NFA means).

[deep merlin]

Yes the NFA is defined in general to not expect epsilon inputs, while the epsilon-NFA accept epsilons and generalise NFA essentially a bottom up approach, that is how he approach them.

I am interested whether there are algorithms from regex to the other automata and vice versa directly because in practice you wouldn't convert them via an intermediary automaton if there is a direct algorithm for it

[stable wren]

is there a formula to determine all self-avoiding walks between some pair of points in a 2-by-N lattice graph?

[final cliff]

I don't know the answer off the top of my head, it might help to look through a dedicated compilers book like torczon or the dragon book (or something newer) for this if you're concerned with what folks do in practice (as opposed to automata theory specific stuff).

If you already considered this though, then just ignore me

[autumn stone]

hello can someone give me some help about discrete math (i'm new at the university and having hardship to catch up since i missed first a few weeks because of some visa problems)

[hoary solstice]

Hot take but discrete time signals is so ungodly boring compared to continuous time

[quick folio]

signal processing has some really fascinating stuff happening on the applied end

for discrete time signals

[coral parcel]

You probably won't get anyone to commit to "give you some help" in general before they even see your question.
However, if you have particular questions about things that confuse you, then just ask those, and the chance of someone picking them up and writing an answer will be significantly better.

[cosmic lake]

guys

can any one tells me about any channel explain discrete math

[ancient river]

dft! dft! dft!

[quick folio]

hell yeah

[novel ore]

Am I trippin or if n > 2 then the euler totient function is always even

I think it's true I kind of assembled a proof in my head

[coral parcel]

Yeah.

n>2 will either have an odd prime factor or at least two factors of 2.

[novel ore]

Thanks

Why is this true? I've been meditating on it and for some reason I thought of the Sylow Theorems but I don't think it's that lol

I guess this is equivalent to asking for solutions of x^2 \equiv 1 mod m_1 which are not 1

The criteria of which I am uncertain

[coral parcel]

Sylow does the job: a group of even order contains a nontrivial Sylow 2-subgroup, so by Lagrange a nonidentity element of that subgroup must have order 2^k for some k>0, and the 2^(k-1)th power of that element will have order 2.
However, more low-tech you can also say: There's an even number of elements of each order > 2, since each such element pairs up with its inverse, and and odd number (namely one) of elements of order 1, so in order to make an even number of elements in the group in total, there needs to be an odd number of elements of order 2. In particular there cannot be none of them.

[novel ore]

Thanks!

[hard citrus]

trying my luck here, i forgot what's the process to formally find the explicit form of recursive formulas, i just plug it back once or twice and then see the pattern, but i remember there were some mathematically formal ways to do so.

like i have the following recursive expression $$\alpha_{n}=P\alpha_{n-1}+\left(1-Q\right)\left(1-\alpha_{n-1}\right)$$ where P, and Q are probabilities (unrelated to each other) which means they're both between 0 to 1, i also know that $\alpha_0=1$.

by plugging it back in a few times i got that $$\alpha_{n+1}=\left(P+Q-1\right)^{n+1}\alpha_{0}+\left(1-Q\right)\cdot\sum_{i=0}^{n}\left(P+Q-1\right)^{i}$$ and since P+Q<2 i can simplify the sum, and simplify the entire expression into:

$$\alpha_{n+1}=\frac{\left(P+1\right)\left(P+Q-1\right)^{n+1}+Q-1}{P+Q}$$

but the way i do it doesn't feel right.

[vital dew]

Henry_quite_hungry

[coral parcel]

A systematic approach would be to homogenize the recurrence by adding a new variable that will always be 1:
$$ \alpha_n = P\alpha_{n-1} + (1-Q)(\beta_{n-1}-\alpha_{n-1}) \qquad\qquad \beta_n = \beta_{n-1} $$
Then we can write down the solution in matrix form
$$ \begin{pmatrix}\alpha_n \ \beta_n \end{pmatrix} = \begin{pmatrix} P+Q-1 & 1-Q \ 0 & 1 \end{pmatrix}^n \begin{pmatrix}1\1\end{pmatrix} $$
and diagonalize to find an exponential closed form.

[vital dew]

Troposphere

[hard citrus]

I've never seen this way, this is new to me and i don't think i can do it, sorry.

[coral parcel]

Sorry, was the only systematic exact procedure that came to mind.

[hard citrus]

thanks anyway, this looks interesting does it have a name so i can look a bit more into it?

[coral parcel]

Hmm, I'm not aware of any particular name. Googling for something like "solving recurrences by diagonalization" seems to turn up at least some material.
Beware that it will probably require you to have at least a semester or so of linear algebra under your belt.

[trim meteor]

any good recommendation to understand DM more? especially DM that is more computer science oriented

like ressources similar to the Organic chemistry tutor

[pine marlin]

what kind of topics

also #book-recommendations might interest you

[trim meteor]

more like an in general ressource especially when it comes to forming proofs or deciphering english to logical formulas

[pine marlin]

so you are looking for an introduction to proofs and logic

I don't know any resources myself

[random sparrow]

I need some help with this exercise, idk how to begin

"Determine all the tuples (a,b) in Z^2, such that it is satisfied simultaneously "4|a", "8|b" and "33a + 9b = 120"

[random sparrow]

ok, so for example if 4 | a then a = 4x for some x in Z

similar with 8 | b then b = 8y for some y in Z

I place this in the last equation and we get

33(4x) + 9(8y) = 120

and we get

132x + 72y = 120

and if you divide by 12 both sides

we get

11x + 6y = 10

after this is where I get stuck

we might need to use fubini

like, first solve 11x + 6y = 1

so

gcd(11,6) = 1

11x + 6y = gcd(11,6)

11x + 6y = 1

this is where I get stuck

I forgot how to solve linear diophantine equations

ok. now I remember

just, first find a particular solution

then after we found one particular solution we can find all the solutions to the linear diophantine

so for example

11(-1) + 6(2) = 1

because -11 + 12 = 1

so we got that one solution to the linear diophantine is (-1,2)

now, its simple

11(-6) + 6(11) = 0

so

all the solutions to 11x + 6y = 1

are of the form

11(-1 -6k) + 6(2 + 11k) = 1

where k in Z

so all the soltuions to 11x + 6y = 1 are (a,b) = (-1-6k, 2 + 11k)

the issue is that we were trying to find all the solutions to 11x + 6y = 10

[random sparrow]

Si se sabe que cada unidad de un cierto producto A cuesta $39$ pesos y que cada unidad de un cierto
producto B cuesta $48$ pesos, ¿cuantas unidades de cada producto se pueden comprar gastando exactamente $135$ pesos?

If its known that each unit of a certain product A costs 39 pounds and that each unit of a certain product B costs 48 pounds how many units of each product can we buy having exactly 135 pounds?

[vital dew]

Renato

[weak stirrup]

[nimble tangle]

idk if thats it but

can someone show me a or b?

[south sable]

Hi can anyone recommend me a good resource to learn computational (applied) graph theory

[charred ingot]

google

[weary tiger]

hm is this
39x + 48y = 135?

how do one even solve such a equation

lol

dude tf

okay, i gotta start doing discrete mathematics as well

this stuff too powerful

[pine marlin]

Number theory is more related to this stuff

[slim geode]

Look and see.
"So x and y are counts of something, meaning they will be positive integers. 135 is just slightly greater than 39 and 48 so they will not be very big. Since 39 and 135 are both odd, let me try x=1, and yup, that works when y=2."

Unfortunately you can't do this when the numbers get very big

[pine marlin]

The Euclidean algorithm is very good for this

[random sparrow]

yes

[random sparrow]

its a linear diophantine eq

[random sparrow]

39X + 48Y = 135
gcd(39,48) = gcd(39, 9) = gcd(3,9) = gcd(3,0) = 3
so we divide the equation by gcd(39,48) we get
13X + 16Y = 45
so gcd(13,16) = gcd(13,3) = gcd(1,3) = gcd(1,0) = 1
using bezouts lemma we know that
13X + 16Y = gcd(13,16) exists and is solvable
so we find the solutions to 13X + 16Y = 1
to find all the solutions we just need to spot one and then we can use that 13(16) + 16(-13) = 0
so
basically since gcd(13,16) = 1 the multiplicative inverse of 13 (mod 16) exists
13X + 16Y = 1
13X = 1 (mod 16)
13, 26, 39, 52, 65
16, 32, 48, 64
bingo! 13*5 = 1 (mod 16)
because 13*5 = 16*4 + 1
so, 13(5) -16(4) = 1
so, 13(5) + 16(-4) = 1
so one solution to
13X + 16Y = 1 is (X,Y) = (5,-4)
now that we have one solution, we multiply them by 45 so we can get a solution to
13X + 16Y = 45
so a solution to the linear diophantine
13X + 16Y = 45 is (X,Y) = (225, -180)
now that we got that, out of the way, we use that 13(16) + 16(-13) = 0 to get all the solutions
so (X,Y) = (225 + 16k, -180 -13k) represents all the solutions to 13X + 16Y = 45
but we want all the positive integer solutions
so we want k in Z such that
225 + 16k >= 0 and -180 - 13k >= 0
so 16k >= -225 and -13k >= 180
so k >= -225/16 and k <= -180/13
so k >= -14.06 and k <= -13.84
so since k in Z
and -14.06 <= k <= -13.84
we get that k = -14
then we go back to
(X,Y) = (225 + 16k, -180 -13k)
(X,Y) = (225 + 16(-14), -180 -13(-14))
(X,Y) = (225-224, -180+182)
(X,Y) = (1,2)

if you don't want to use multiplicative inverse of 13 (mod 16) you can

write some multiples of 13 and 16 and see which of them are apart by 1

but in more complicated examples you might need to use extended euclidean algorithm

13, 26, 39, 52, 65
16, 32, 48, 64

[gentle sandal]

hi guys i've got graph theory problem could you help me?

almost hamiltionian = hypohamiltionian

[paper scaffold]

Is this the infamous comp3821 tutor

Was

@haughty garden are all the math1081 exam questions seen

Will there be unseen ones

[burnt terrace]

,tex(maths)
Let $C = (v_1, v_2, \ldots, v_{\abs V-1})$ be a Hamiltonian cycle in $G-u$. Take the subsequence $(u_1, u_2, \ldots, u_{d(u)})$ by only keeping those vertices that are a neighbour of $u$. Now consider the cycles formed by taking the arc from $u_i$ to $u_{i+1}$ and adding the edges $uu_i$, $u_{i+1}u$, for $1\leq i\leq d(u)$. Then $\ldots$

[tardy ravine]

This seems pretty diabolical

[tired summit]

Unrelated but what’s that color omggg

[weary tiger]

RIGHT

so cooool

[gentle sandal]

Thanks

[dusk sierra]

my bad

[cloud igloo]

What's the F_1? First Fibonacci number. 0 or 1? Coz it'll affect indexing afterwards.

[little prism]

wikipedia starts with F_0=1. but its not like there is a single correct answer. you can always modify every formula

[lucid jay]

i need help with the third one and the fourth one

[past rivet]

what have you tried so far?

[lucid jay]

for the third one ik that its abvieous that (If A⊆B, then A∪B=B) but i couldnt prove the other dircetion

[past rivet]

oh there's a cool argument you can give for the other direction

can you show $A \subset A \cup B$?

[vital dew]

Pseudo (Cat theory #1 Fan)

[lucid jay]

no

i dont understand

[past rivet]

this result is always true is the thing

$X \subset X \cup Y$

[vital dew]

Pseudo (Cat theory #1 Fan)

[past rivet]

i would recommend trying to prove this

[lucid jay]

but whats the point of proving it?

i dont get it for now

[past rivet]

oh!

well, the idea is

if you can show $A \subset A \cup B$

[vital dew]

Pseudo (Cat theory #1 Fan)

[past rivet]

then you can prove the other direction of part 3

because $A \cup B = B \implies A \subset A \cup B = B \implies A \subset B$

[vital dew]

Pseudo (Cat theory #1 Fan)

[lucid jay]

ooh i get it

this another way

what about

if x∈A, then x∈A∪B. Since we have the hypothesis A∪B=B, this implies that x∈B. Therefore, A⊆B.

is it correct like that?

[past rivet]

yep, that's essentially the same argument

by showing "if x in A, then x in A u B", you've shown

$A \subset A \cup B$

[vital dew]

Pseudo (Cat theory #1 Fan)

[lucid jay]

got it

and

about the first direction

Let x∈A∪B. Then x∈A or x∈B.
If x∈B, then x∈B.
If x∈A, since we have the hypothesis A⊆B, then x must also be in B. In both cases, x∈B. Thus A∪B⊆B.

is this a good argument?

[past rivet]

yep!

[lucid jay]

oh thanks

emm do u have any good resouces for it?

i mean set theory

[past rivet]

hm...

[lucid jay]

cuz my college doent offer good things and they dont explain it that good

[past rivet]

none come to mind, but you could ask in #book-recommendations

i think venn diagrams help a lot when doing set theory

it's quite easy to get lost in the notation otherwise

also, it can be helpful to have different perspectives on sets than "a set is a collection of things"

for example, if a ball is in a bag, and that bag is in a box, then the ball is in the box

but this doesn't work in set theory

$x \in y$ and $y \in z$ doesn't necessarily mean $x \in z$

[vital dew]

Pseudo (Cat theory #1 Fan)

[lucid jay]

emm

how can i understand more about it?

[past rivet]

these and more general diagrams

also understanding the basics of logic could help too

and, or, implies

[lucid jay]

i did

i mean i already studied them in chapter 1

i got a problem with proving things

i cant visualise the problem

or get an idea how to finish proving it

[past rivet]

Yeah that’s why I suggested Venn diagrams

[lucid jay]

yes thank u for it

[past rivet]

[delicate vault]

can someone help me how to understand how to get a recursive relation and solving it using ordinary generating functions

im struggling with basic problems

is there some good resources to practise

[grand totem]

<@&268886789983436800>

[cerulean radish]

<@&268886789983436800>

[little latch]

which tutorial is this?

https://www.instagram.com/p/DG-pBGdxoLc/?igsh=OWg2Z2UxOHBlOGpp

jaypaslay

Good morning from DC!

Instagram

[gusty wedge]

do anyone have video lecture recommendation on enumerative combinatorics ?

[brisk spear]

hello !

so for this question

i actually solved the homogeneous first

and then got the generating function for n²

why is that wrong and if the approach is wrong, how are we supposed to do it

my professor actually didn't even teach this in class so im so lost

[analog hound]

This was ages ago, but thanks for answering my question. Your writeup was helpful (and well-written), sorry I didn't reply

[lofty cloud]

Show your work, and if possible, explain where you are stuck.

[prime quiver]

theres only 2 zeros at the end of 100, why are u so dramatic

[weary tiger]

[weary tiger]

Nice joke

😭

[prime quiver]

😎

[small shard]

♾️

[robust monolith]

Many zeros

[unreal apex]

24?

[flat grotto]

hi all

how come this is wrong? or is it right?

I know AI is not the best especially at these things but my book seems to differ a lot from reality and i need some confirmation sometimes, is line 10 incorrect?

[quick folio]

what is your justification for introducing a universal quantifier?

[flat grotto]

To use exists-elimination

[quick folio]

but why can you do it?

we don't know anything about every element in X

we only know something about some specific x inside X

so how can you tell me out of nowhere that you suddenly know something about everything in X?

you may want to double check the rules for when universal introduction is allowed

[flat grotto]

You are right i understsnd

I’m not sure how else i’d do it then

[quick folio]

line 11 also looks weird

P is a statement whose truth value is dependent on x

[flat grotto]

Well snything sfter domething weird will look weird

[quick folio]

so I don't see why it is possible for a contingent statement to be true or false

[flat grotto]

Of that makes sense

[quick folio]

for instance P might be something like "____ is a dog"

and so you're telling me that "____ is a dog" is a true statement without filling in the blank, which doesn't really make sense

[quick folio]

but you are basically done, already

[grand totem]

a lot of stuff here certainly doesn't look like one would usually expect it to. but it's hard to say whether that is because your proof is wrong or because the proof system you're given to work with might be a little odd

so it would be very helpful to see an outline of all the rules in your system

[flat grotto]

Sorry had a lecture

[flat grotto]

I understand that makes sense in hindsight

[flat grotto]

Can you explain? As in the structure is there just need to reformat it?

[flat grotto]

Yes sure, we use from a specific book but these are the rules more or less verbatim:

What about this?

Here would this not be better?

[grand totem]

what an odd style of natural deduction

may i ask what book this is taken from?

[flat grotto]

Well if its the one i sent last maybe its me

Definitely one moment

[flat grotto]

Ah okay, this seems to be a book specifically for my university

"Mathematics of Discrete Structures" by Gordon J Pace

[grand totem]

Okay, one second

the author actually defines existential elimination in terms of \forall and disjunction elimination and negation introduction in terms of implication that's all rather scuffed but that explains why your proofs look so nonstandard

[flat grotto]

well that makes sense as to why it would look odd

Forgive me for the fact that I don't necessarily comprehend why they are odd, since this is all I am used to

[flat grotto]

here i tried explicitly referring to the quantifiers

so im not sure if that is more correct than my other one

[grand totem]

usually you'd only have one connective per inference rule so that they can function on their own
which is what for example HChan's question here stems from. the problem statement didn't include a universal quantifier so one wouldn't expect it to show up in the proof either

[flat grotto]

i see okay

I do not see another way of doing it though

I need the universal quantifier to infer existential elimination

[grand totem]

this proof here would be fine if the problem statement included the assumption that x isn't free in P since that's a necessary side condition for the instance of existential-elim in line 5

but i'd assume the problem statement didn't include that side condition since the theorem still holds if x is possibly free in P

so your first subproof here requires an adjustment

a hint would be that x isn't free in ∃x:X. P, so you should aim to derive ∀x:X. (Q -> ∃x:X. P) in that subproof

[flat grotto]

hmm i see

i think I understand

[flat grotto]

but i know it isn't, no?

since I have the statement on line 3

[grand totem]

similar problem here in line 11 since \neg P may contain x

[flat grotto]

or do I know it isn't free in Q=>P?

[flat grotto]

hmm you've lost me somewhat

wait maybe i get it

so I need to try not use pure propositional logic

if I have quantifiers with variables, it means that variable is bound and not free for a given P

[grand totem]

this is your existential-elim rule, the antecedent in your forall should not contain the quantified variable freely

[flat grotto]

hold on

How is the precedence in the second condition?

(For all x of type X such that P) => Q or For all x of type X such that (P => Q)

[grand totem]

its forall (p -> q)

[flat grotto]

exactly

[fossil mural]

presumably the second one, because the first one isn't true

[flat grotto]

yes exactly thats why

so

wait but then not exactly i don't understand it properly for sure. my understanding is that if I have:

this means that x is not free in ¬P

[grand totem]

you don't know that though unless the problem explicitly states that (which I doubt it does in this case)

[flat grotto]

Is a variable not bound in the scope of its quantifier?

[grand totem]

P here presumably stands for any first-order formula

[flat grotto]

understood yeah

[flat grotto]

but can you not say that forall.x:X.(P=>Q) says that any occurence of x in (P=>Q) is not free?

[fossil mural]

no

for instance "forall n : nat. (n is even or n is odd)" is true, but there are free occurrences of n in the statement "n is even or n is odd"

[bleak berry]

Is there a specific computer logic book I should study or is the best way to study problem solving skills for coding just discrete math

[grand totem]

x is not free in forall.x:X.(P=>Q), it may certainly be free in P -> Q

[fossil mural]

although yeah it does mean that the occurrences of x in P => Q don't count as free occurrences of x in "forall x:X. (P => Q)", because they're bound by the "forall x:X"

[flat grotto]

I understand this

there is a good example in the book I have which explains this

[fossil mural]

but the thing is, the inference rule doesn't say "x must not be free in forall x:X. (P => Q)", it says "x must not be free in Q"

[flat grotto]

P -> Q is implies?

[grand totem]

yes

[flat grotto]

hmm

oh 🤔

ohhh

so

[grand totem]

yeah I'm aware, I think the confusion here stems from not recognizing the fact that P and Q (being arbitrary formulas) may contain x freely

at least that was their mistake in both proofs

[flat grotto]

if I get ∀x:X(P=> (∀x:X(Q)) )
and I have ∃x:X(P)
Then I can safely infer
∀x:X(Q) ?

[grand totem]

Yes!

that works

[fossil mural]

(yeah i know you're aware of that, i was addressing that to the person getting help, i only replied to your message because it's my reference for what the inference rule actually is)

[grand totem]

because ∀x:X. Q doesn't contain x freely since it's bound by the quantifier

[flat grotto]

that makes sense now

[grand totem]

even if Q itself might contain x

[flat grotto]

exactly

i get it i get it

so that lets me say with certainty that x is not free in Q

[grand totem]

(Oh sorry, my bad)

[flat grotto]

exactly

i see ok

so in a way, the proof format will remain somewhat similar but I will need to reformat how to use certain rules with these side conditions?

The issue was as you mentioned that P and Q i was not really individualizing them, if that makes sense

[grand totem]

well as they currently stand both proofs just aren't right, but both of them may be fixed once you've recognized that mistake

[flat grotto]

yes exactly

[grand totem]

ok well granted I haven't looked at the first one in-depth I just scrolled up to check if you made the same mistake there

but the second proof you sent only requires that one adjustment

[flat grotto]

yes practically

The first one gets invalidated because of that issue, more or less

[flat grotto]

I am still somewhat stuck on now how to explicitly state x is not found free in P, i can see a way of doing it but I think it is overcomplicating a simple situation

[grand totem]

x may be free in P, that was the entire point of why your usage of existential-elimination in line 5 of the proof is problematic
i'd suggest rewriting that particular subproof from scratch (the rest of the proof is fine)
ideally the subproof should in the end look something like this

m      | ∃x:X. Q
       | ...
n      | ∀x:X. (Q -> ∃x:X. P)
n + 1  | ∃x:X. P

where line n + 1 was obtained by using existential-elimination on lines m and n, which we can do because x is not free in ∃x:X. P

[primal grove]

can someone help me understand where I am going wrong with the surjective proof? the y + 2 term specifically is what is throwing me off this should prove to be surjective however I have an error in my logic somewhere.

[spare slate]

,w solve for x if y=-2x-1

[vital dew]

Results provided by WolframAlpha

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

Requested by civil_service_pigeon

[primal grove]

OH i got it thanks !

[spare slate]

[wary falcon]

Is Cartesian product of Reals and Imaginarirs = Complex?

[flat grotto]

I still cannot get this but this seems to be a one off

Like I was stuck on that for quite a while. but it was just that others I think I got to them fair enough

Here specifically, in line 12, my statement that x is bound in the only open assumption in line 1 is valid right?

[flat grotto]

Here too I think this is correct entirely though. I tried using what you told me yesterday that Q=>P cannot have a free x, so no "mays" so I did exists intro within the subproof/assumption

[flat grotto]

<@&268886789983436800>

pls so my thing doesnt get overrun

thanks

[cerulean wind]

you can check these with online propositional proof checker

https://proofs.openlogicproject.org

it may be easier than writing everything by hand

[flat grotto]

thanks ill check it out

a note is that apparently my rules are weird though

so im not sure if that makes a difference?

or rules of inference* rather

[cerulean wind]

how so?

[flat grotto]

i think my existence elimination is trying to be independent whilst other systems do it in a different manner. this is it:

I formally & logically understand it now, but apparently it can make some trouble with proof checking

[grand totem]

this one is fine now

[flat grotto]

Yep I got it now :D

Thank you you really helped genuinely

I was stuck on the understanding of x must not be found free in P or Q or such

[grand totem]

this one seems to be fine too

good job

[manic wedge]

Would anyone say that discrete maths is a necessity for data science?

Debating if I should enroll

[coral parcel]

"Discrete math" is an umbrella concept that is too vaguely defined to really be "necessary" for anything. If worst comes to worst you can always learn the appropriate topics under their own names.

On the other hand it might me the umbrella that your institution happens to teach something actually essential under. You'll need to seek advice from someone familiar with the particular curriculum at your place.

[paper scaffold]

prolly just for graph theory and dijkstra lmao

[thick coyote]

Anyone here good at discrete

Or like not even good

Js able to like help me learn some stuff that I struggle w

[odd garden]

Can someone explain to me Problem 1? I am not able to solve it

[main spade]

8 red balls , 6blue, 5 green. How many ways to Select 4 balls (order doesn’t matter)

[prime quiver]

accurate

[slow tangle]

LOL

[spare slate]

In the future, please show what you've done so far when asking for help. \ \

Suppose that you choose $r$ red balls, $b$ blue balls, and $g$ green balls. Then, there are $\binom{8}{r}$ ways to select the red balls, $\binom{6}{b}$ ways to select the blue balls, and $\binom{5}{g}$ to select the green balls. This yields a total of $\binom{8}{r}\binom{6}{b}\binom{5}{g}$ possibilities. \ \

It remains to figure out what to sum this over. I'll leave that to you.

[vital dew]

Civil Service Pigeon

[compact canopy]

I need help with discrete 😭

i got 4 hours left of the day need to learn proof of induction to be able to make a program in python

im cooked

[lost helm]

don't people usually mean by discrete math combinatorics, graph theory and related stuff?

[coral parcel]

Yeah, but in different amounts and with different senses of "related stuff".

The one constant is that it seems to be where CS students who don't take math are supposed to learn about mathematical induction.

[lost helm]

cs students who dont take math? im seriously rethinking my understanding of the cs field now lol

[main spade]

Sorry I forgot to attach my working here, but why do 8Cr . Like okay for example:
I have 5 red balls. I am to pick 2 balls. Would I do 5C2? Cuz they all 5 red balls, so isn’t the pick always going to be just 2 red balls leading the answer to be 1

[spare slate]

I was going with the assumption that every ball is distiguishable. Although in hindsight, $\binom{19}{4}$ would be faster - not sure how I missed that. \ \

If you want the balls to be indistinguishable except for color, then stars and bars yields $\binom{4+3-1}{2}=15$.

[vital dew]

Civil Service Pigeon

[spare slate]

For your second question, the answer is yes if you assume that the balls are indistinguishable

although the question is trivial if that's the case so whether or not you choose that interpretation is up to you

[main spade]

Stars and bars…never did this concept before, any idea where I can get a better idea about this?

[spare slate]

https://brilliant.org/wiki/integer-equations-star-and-bars/

[main spade]

Okay looking at my question , why did u assume all are distinguishable

[spare slate]

cause I felt like it ig

[main spade]

[spare slate]

very good answer ik

my brain obviously wasn't very alive when I wrote that

as I missed the simpler route of 19 choose 4 under that interpretation

so um

yeah

[main spade]

Yeah that’s what I was thinking

But this is

Thing is*

Prof said the answers 19C4

😀😀😀😀😀

[spare slate]

oh so ig they did want them to be distinguishable

answer: cause they felt like it

[main spade]

NOOOOOO

[spare slate]

well worded questions will specify whether your things are distinguishable or indistinguishable

questions that are not as well written

make you play guessing games

especially in combinatorics where being precise and thorough is very important

[main spade]

Okay questions fault

[spare slate]

yeah either interpretation could be fine

[main spade]

A good way to some ease to my brain

[spare slate]

honestly most people would go with the indistinguishable except for color version tbh

since why would they bother specifying colors otherwise

but alas

sometimes people just aren't good at writing

[main spade]

But noticed smth

Let’s say if more balls of similar color added, It’s going to be 15 all the time