discrete-math

[coral raven]

then on day 1

they've played 14 games

so we're done

[weary tiger]

28 + 28 = 46

but they cant play more than 45

you see what i am trying to say? it doesnt make sense for me

[coral raven]

?

you don't have to play 1 game per day

some days you can play 0

[weary tiger]

no it says at least once a day

[coral raven]

ah crap

[weary tiger]

"at least one game a day"

[coral raven]

ok well in that case it's impossible to play 14 games on both day 1 and day 2

it's never going to happen

[weary tiger]

i mean doesnt matter what days

if they play twice its already impossible

[coral raven]

what do you mean 'play twice'

[weary tiger]

"Show that there must be a period of some number of consecutive days during
which the team must play exactly 14 games."

consecutive means twice or more right?

[coral raven]

not necessarily

[weary tiger]

😩

[weary tiger]

alright I'm doing something silly feel free to point it out:

$\sum_{k=0}^{m} {n \choose 2k+1} = \sum_{k=0}^{2m+1} {n \choose k} - \sum_{k=0}^{m} {n \choose 2k} = 2^{2m+1} - \sum_{k=0}^{m} {n \choose 2k} = 2^{2m+1} - \sum_{k=0}^{m} {n+1 \choose 2k+1}+ \sum_{k=0}^{m} {n \choose 2k+1}$

wait lmao texit moment

[vital dew]

zd

[weary tiger]

cancel right term on extreme right with original expression to get

$2^{2m+1} = \sum_{k=0}^{m} {n+1 \choose 2k+1}$

[vital dew]

zd

[weary tiger]

and, this is false

what happened?

for example, sum from k=0 to 2 of (7 choose 2k+1) is (7 choose 1) + (7 choose 3) + (7 choose 5) = 7 + 35 + 21 = 63

[weary tiger]

figured it out in vc

[vital dew]

zd

[weary tiger]

when n > 2m+1

otherwise the original formula actually does worth, the example I chose had 7>2(2)+1

[north dust]

I hope my combinatorial explanation of why the Stirling Cycle Number s(n,n) is equal to 1, is correct.

[jagged junco]

Help? An is a recurrence relation.
n is the length of series that consists of {0, 1, 2} where all the occurrences of 0 must be before the occurrences of 2.
Find An

[stray reef]

your teacher wants a minimal spanning tree so you give him a minimal spanning tree. minimizing individual paths is not a concern you have.

[rich siren]

If in a graph the number of vertices is one more than the number of edges, then the graph is a tree?

I can't seem to come up with a counter-example, but it could be because I'm peanut brain

[cerulean wind]

@rich siren take a cycle graph

and then just keep adding vertices until you get more vertices than edges

[north dust]

Ahh, Bell Numbers...

[frosty bay]

broad question, not sure where to ask it

is a function a specific case of a relation?

[last flicker]

yes.

[north dust]

I have to deal with exponential generating functions, AHHH

[elder steppe]

i'm struggling to understand if this is transitive or not

i don't think it is but i'm not sure what the counterexample would be

[elder salmon]

It is transitive right? Cus transitive means if aRb, bRc exist, then aRc should also exist. Here, (a, c) is there so it should be transitive. Er.. right? 🤣

[quaint raft]

whats the fastest way i can find a c-admissable s-t flow of a diagraph?

is running ford-fulkerson the best option or is there a shortcut ?

[weary tiger]

Hi guys

Let S be the subset of the set of ordered pairs of integers defined recursively by
Basis step: (0, 0)∈S.
Recursive step: If (a, b)∈S, then (a, b+1)∈S, (a+1, b+1)∈S, and (a+2, b+1)∈S.
a) List the elements of S produced by the first four applications of the recursive definition.
b) Use strong induction on the number of applications of the recursive step of the definition to show
that a≤2b whenever (a, b)∈S.
c) Use structural induction to show that a≤2b whenever (a, b)∈S

I am stuck at b part

I did it like this so far but dont know where to take it from here

[stray reef]

that is not how they expect you to word it, i think.

[weary tiger]

yeah i mean i just quickly did it paint

i am writing it in my paper

too lazy to take a pic of it

but what do you mean how should i word it?

[stray reef]

you should begin your proof like this:

Let n ∈ N and assume that a ≤ 2b is true for all (a,b) ∈ S such that (a,b) can be achieved from (0,0) by strictly less than n applications of the recursive step.

Let (a,b) ∈ S be a point which can be achieved in exactly n applications of the recursive step. We aim to show that this point satisfies a ≤ 2b.

[weary tiger]

right, okay

[stray reef]

since (a,b) ∈ S, there must exist (a', b') ∈ S such that (a',b') can be achieved in n-1 applications of the recursive step, and one of the following holds: (a,b) = (a', b'+1), or (a,b) = (a'+1, b'+1), or (a,b) = (a'+2, b'+1).

[weary tiger]

okay i got it to so far

[stray reef]

by the induction hypothesis, a' ≤ 2b'.

[weary tiger]

but how do we actually show it, thats what i am most confused on

[stray reef]

go through every case one by one and show that a' ≤ 2b' implies a ≤ 2b

[weary tiger]

okay so lets say in the first case

(a, b + 1)

[stray reef]

and one of the following holds: (a,b) = (a', b'+1), or (a,b) = (a'+1, b'+1), or (a,b) = (a'+2, b'+1).

[weary tiger]

can i write it as a + b + 1?

[stray reef]

no, (a, b+1) is not the same thing as a + b + 1.

[weary tiger]

i have no clue

can i write (a', b' + 1) as

a <= 2b <= 2(b+1)

so a <= 2b <= 2b + 2

which means its true?

[stray reef]

you're not sticking to my notation here, which will make it hard or even impossible to properly communicate

[weary tiger]

I am sorry, what didn't you understand?

Anyone that can help me explain this question for me?:
Assume that h(x) is a w-bit value, and h has properties similar to a fully random one function. How large can the length n of the sequence be if the assumption that there are no collisions to hold? An answer in big-O notation is sufficient.

[stray reef]

@weary tiger your use of "write ___ as ___" is a bit hard to decipher sometimes.

that is all i will say. please do not question me any further on this.

[weary tiger]

okay

[weary tiger]

a binary operation as defined in my textbook is an operation that maps each pair of elements that can be made in a set onto another element of that same set

then the division operator on the set of real numbers isn't a binary operation right? since division by 0 (which is part of the real numbers) is not possible ?

[dim marten]

hey i was given a bunch of practice problems for class.
if anyone can show me how to do this one that would be nice.

[pale epoch]

correct

[pale epoch]

show you how to do it? did you not do an example problem in class?

[dim marten]

probably did but its a bit hard to pay attention the whole class time

[pale epoch]

i don't think it's possible to explain the whole concept of induction via discord, you should work through your material and/or search for other explanations (youtube, ...) of the concept first and actually attempt the question

[dim marten]

ok

[weary tiger]

anyone

help

[wheat leaf]

Can someone help with this

[meager prairie]

How would you go about generating the binary code given an encoding matrix?

I am tasked to list out the (6,3) binary code for this matrix:

$\begin{bmatrix} 1 & 0 & 0 & 0 & 1 & 1 \ 0 & 1 & 0 & 1 & 0 & 1 \ 0 & 0 & 1 & 1 & 1 & 0 \end{bmatrix}$

[vital dew]

jan Niku

[meager prairie]

so im anticipating 8 words? since its binary and its a 3 dimensional subspace

do you just pick one at random and see if its order divides 8?

[pale epoch]

🤔

the code is just the subspace of F_2^6 spanned by the rows?

[meager prairie]

F_2^6?

damn this stuff is confusing

oh, yea

F_2^6

how would you know the span though

[pale epoch]

well, there are only 8 possibilties

[meager prairie]

we know there are 8 just by it being binary and messages of 3 length right

or are you getting 8 in another way

[pale epoch]

the span of 3 elements over any F_2 vector space can have at most 8 elements

all the elements in the span are linear combinations of the 3 elements with coefficients in F_2

the span is $\lambda_1b_1 + \lambda_2b_2 + \lambda_3b_3$ where $b_i$ is the $i$th row vector and $\lambda_i \in \mathbb{F}_2$

[meager prairie]

I guess im confused, 3 is our message size, right?

the words will still be 6 digits long

[vital dew]

Lochverstärker

[pale epoch]

been a while since i used that lingo lmao

but words should be elements of F_2^6 and thus be 6 digits long

[meager prairie]

sorry im sorta confused we had our first lecture on this, and our teacher switched two variables halfway through (n,k) code to (k,n) code

yea, thats what i thought

so why are you looking at the span of something 3 long?

[pale epoch]

the 3 rows of your matrix generate the code i think?

[meager prairie]

they do?

[pale epoch]

what is the definition of encoding matrix

[meager prairie]

an n by k matrix which encodes a word

[pale epoch]

and what does encode mean

[meager prairie]

im not sure we didnt define that word further

[pale epoch]

i know what a generating matrix is

and that is just collect a basis of the code in a matrix

so then you can write every word of that space as the matrix multiplied by some vector

[meager prairie]

oh these are the bases?

[pale epoch]

which i would read as encoding

[meager prairie]

that makes way more sense than whatever my teacher was talking about

[pale epoch]

so i would assume that the rows of your encoding matrix are a basis of your binary code

[meager prairie]

so you'd just take uhh

take each pair in turn i guess and operate them

then all 3

then each row

thatd give you the 8

is that really it

[pale epoch]

you look at this

there are 8 possibilities for (\lambda_1, \lambda_2, \lambda_3)

[meager prairie]

I'm not sure how to parse what you've written

oh

[pale epoch]

you calculate them all

they are just 0 or 1

[meager prairie]

okay

[stray reef]

you could multiply [000; 001; 010; 011; 100; 101; 110; 111] by your encoding matrix

[meager prairie]

thats a much nicer way to write what i was thinking of doing lol

[stray reef]

by this i mean an 8 by 3 F2-matrix

[pale epoch]

i mean this is all simple linear algebra, you just have to translate the lingo

[meager prairie]

this also would have been a good idea

[meager prairie]

idk really linear algebra

[pale epoch]

that is unfortunate then

[meager prairie]

yea

wasnt a prereq for this course though

so i thought id be fine haha

[meager prairie]

or i guess im still confused, how do you know taking things of length 3 will work out

since arent our words in the end gonna be 6 long

[stray reef]

the codewords are 6 bits long

[meager prairie]

are you just figuring since the actual message is gonna be 3

[stray reef]

but the messages are 3 bits

[meager prairie]

ok

thanks you two 😊 it makes a lot more sense

🙇‍♂️

[weary tiger]

I have to prove whether or not there exists a number n element of the natural numbers for which every natural number is a dividor.

the only expression that can be divided by every natural number is the product of (p_i)^r, with i from 1 to infty and r tending to infty. p_i here is the i-th prime number.

however, this product tends to infty, and so it is not an element of the real numbers I would think, thus the first statement is false

Is there any fault in this reasoning?

[pale epoch]

the only expression that can be divided by every natural number is the product of (p_i)^r, with i from 1 to infty and r tending to infty. p_i here is the i-th prime number.
why?

[weary tiger]

well, each natural number can be represented by a product (p_i)^(r_i) with r_i the specific exponent for the prime number p_i (r_i can be 0 too) and i from 1 to infty (basically the fundamental theorem of arithmetic)

so, every number for which an i exists with a finite r_i will not have the natural number p_i^{r_i+1} as a divisor.

thus, a number can only be divisable by all natural numbers if it is equal to the product of p_i{r} with r tending to infty and i from 1 to infty

[pale epoch]

thats not quite correct

whats the definition of "divides" @weary tiger?

(there is no reason to use such heavy machinery here)

also the original argument is kinda weird, since it seems to conclude that the only "number" dividing every number is "infinity" and that infinity is not a number, so it can't exist

so, every number for which an i exists with a finite r_i will not have the natural number p_i^{r_i+1} as a divisor.
this is a better formulation as to why most numbers have a non-divisor, but you also get this by just considering any greater numbers and dont need a prime factorization

notice that i say most numbers, considering the actual definition of divides you should easily see the exception

[weary tiger]

If b divides a, then a modulo b = 0

[pale epoch]

what does modulo mean

[weary tiger]

Mod

Remainder after division

[pale epoch]

eh, thats a bad definition, but you should still be able to see which a works always

[weary tiger]

No im saying that the only number which can be divided by all natural numbers is infty

[pale epoch]

infinity is not a number

[weary tiger]

Yeah that was my point

[pale epoch]

yes, hence that argument is bad

[weary tiger]

I need to prove that there isn't a natural number n which can be divided by all natural numbers

[pale epoch]

saying "the only number which can be divided by all natural numbers is infinity and that is not a number" is not an argument

[weary tiger]

Since every natural number can be written as a product of primes (or power of primes), there can't exist one, because for every natural number, say it has in its product 2^(r_i), then 2^(1+r_i) won't be a divisor of that number

[pale epoch]

that works in most cases

[weary tiger]

The only case in which that doesn't work is if r_i is infty, but then we don't have a number anymore?

[pale epoch]

r_i cant be infinity

you just construct a number that doesnt divide any given number, so you are done

well, except this argument only works for strictly positive numbers

[weary tiger]

Thats what im saying, since it can't be, there will always be a 2^a that doesn't divide a given natural number

[pale epoch]

only positive numbers, but yes

"except when r_i = infinity" makes it wrong though, as this does not make any sense

[weary tiger]

Yeah that was the doubt I had in the beginning and why I asked here, if that infinite product of primes can be considered a natural number
I thought it wouldn't but I wanted to be sure

[weary tiger]

0 isn't necessarily considered a natural number

[pale epoch]

bad definition, but ok

[weary tiger]

We include 0 as a natural number in our textbook discrete math, but not in all textbooks

However I know I should have specified

[pale epoch]

well, the point is that 0 is indeed divisible by any number

and that's kind of important

[weary tiger]

But I thought it was clear because if we included 0 the problem would be too easy xD

[weary tiger]

Yes of course

Thank you for your time

[restive surge]

How would I find where this polynomial is rational? I know it’s not really a polynomial, but that’s why I can’t find rational solutions. The polynomial is sqrt(4a^4b^2-8a^3b^3+4a^2b^4+b^2d^4-4abd^4+4a^2d^4) and I want there to be two separate values of d that work with the same a and b and no values to be equal or 0.

Also maybe important to note that I only need one nontrivial solution, but I’d definitely prefer infinite.
a cannot be twice b.

I tried asking in the help channels but nobody responded

[cerulean wind]

why tho

[quaint raft]

any hints on where i should start for this problem ^

[quaint raft]

<@&286206848099549185>

[narrow sorrel]

Anyone knows how to prove (a*b)+a=a in Boolean Algebra?

[grim citrus]

Can someone help me with this

How many people must be present to guarantee that :

at least three of their birthdays are in one of the months January, February, March, April or at least four of their birthdays are in one of the remaining months?

<@&286206848099549185>

I am very confused

I figured that we need atleast 4 people for the first case and then 5 people for the second case??

[round tulip]

Just starting my first lessons on discrete math here and learning logical equivalences...can someone clear something up for me? I get how to go from 1. to 2. using the rule I've added, but is going from 2. to 3. using also the same rule? I think I might be thinking about the rules too literally. Thank you!

[north dust]

These exponential generating functions are (figuratively) killing me.

[bitter spire]

hii

please help me

[limpid fern]

so, like if you were to describe a function $y = f(x)$ in the form $f:X \to Y$ would there be a special word for the representation $f: X \to Y$

like I have the function $y = x^2$ if x is an integer, then we can describe this function as $f: \mathbb{Z} \to \mathbb{Z}^+$

[vital dew]

ChubbyMuffins

[limpid fern]

is there a special word for the representation $f: \mathbb{Z} \to \mathbb{Z}^+$

[vital dew]

ChubbyMuffins

ChubbyMuffins

[limpid fern]

I would appreciate a response 😅

[cerulean wind]

a function

[limpid fern]

just that?

a function?

not like a word that represents "a description of a function"

anyways

thanks

I'll look more into it

[stray reef]

i have seen the notation f: X->Y specifically called a signature

[limpid fern]

I see

tysm

[floral field]

So, I'm trying to understand the proof that if we have
$$ A(x) = \sum_{n \geq 0} a_nx^n, $$
$$ B(x) = \sum_{n \geq 0} b_nx^n $$
then the coefficient of the nth term of $A(x)B(x)$ is
$$ \sum_{i=0}^n a_ib_{n-i} $$

[vital dew]

beeswax

[floral field]

I tried to expand both series and looked at each term when multiplying out, and only thing I noticed was that the sum of the subscripts of a,b equal exactly the power. Could someone guide/talk me through what is going on?

[pale epoch]

thats exactly that

you have to ask "when is x^i*x^j = x^n for some fixed n?"

turns out this is the case precisely when i+j=n

so now you want to group together all the terms a_i, b_j such that i+j = n

those are a_0 and b_n, a_1 and b_{n-1}, ..., a_n and b_0

so the expanded sum will have a_0b_nx^n + a_1b_{n-1}x^n + ... + a_nb_0x^n as summands and those are precisely all terms where x^n appears

@floral field

[floral field]

Ah

So basically the number of terms in the coefficient of $x^n$ corresponds to the number of ways we can sum $i$ and $j$ to $n$ and each $a_ib_j$ will have $i+j=n$. Looking at the first three terms of $A(x)B(x)$ as an example, we have
$$ (a_0b_0)x^0 + (a_0b_1+a_1b_0)x^1 + (a_0b_2 + a_1b_1 + a_2b_0 )x^2. $$

[vital dew]

beeswax

[pale epoch]

indeed

[restive finch]

Hello, I was wondering how to find a closed form expression for an algorithm

I understand how to do it for an equation or summation, but this is confusing me

[pale epoch]

this is basically a summation

[restive finch]

what numbers are being used in it?

[pale epoch]

you think of the for loops as two sums

the outer one goes from i=0 to n and the inner one from j=0 to i

and you sum up the "work" done inside, i.e. the work done by bar()

[restive finch]

So my teacher set up the answer at the bottom for us. How is he getting 243?

The bottom table just doesn't make sense to me

I don't think thats right but that's the closest I can get

[pale epoch]

why the j after the 2?

bar should be doing constant work

i have no idea how anyone would be getting 243, considering the result has to depend on n

[restive finch]

is bar not doing constant work in the drawing?

[pale epoch]

is 2j a constant?

[restive finch]

I was setting it up like this. 2j isnt a constant

[pale epoch]

"like this" doesnt tell me anything

what you sum up (in this case) should just be the work done by bar(), and it does a work of 2, not 2j

also the loops start at 0, not at 1

eh nvm, thats actually fine

except it isnt

is this code purposely written badly ...

well, check how often exactly the loops run and adjust your bounds accordingly

[restive finch]

would the closed form expression then be 2n^2?

[pale epoch]

,w sum(sum(2, j, 1, i), i, 0, n)

[vital dew]

Results provided by WolframAlpha

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

Requested by Lochverstärker#5585

[pale epoch]

apparently not

[candid gorge]

what rule of inference law is used to get A->B given A and B

or do i need more information

like

I've proven A and B

the conclusion i need to meet is A -> B

can i conclude A -> B knowing A and B

[pale epoch]

would be weird if A -> B depended on anything other than A and B

[candid gorge]

thsi is the problem

i did

1. assume A
2. get AvB from step 1 with v elimination
3. get C^D from step 2 using MP
4. Get C from step 3 with simplification
5. Get BvC from step 4 with v elimination
6. Get A^B from step 5 with MP
7. Get A and B from step 6 with simplification

[pale epoch]

how did you define A -> B?

or do you know that A -> B is equivalent to not A or B

[candid gorge]

i'm not sure how to get from step 7 to A->B

ohh

wait

ur right

[pale epoch]

i mean then its just v introduction or something

from B to not A or B

and you still have to consider the case not A

but that's just 1 step then

[ripe sierra]

You don't have to consider ~A actually

To derive A -> B, you assume A and derive B

[crystal scarab]

can someone help me with this? I dont understand how all three events can be independent of each other until they are all combined

[haughty garden]

The classic example can be found in Probability Essentials by Jacod and Protter. Consider the set of 4 points: S' = {1, 2, 3, 4}. We define the sample space to be the set of all subsets of S'. That is, S = 2^(S').

Let A = {1, 2}, B = {2, 3} and C = {1, 3}. Finally we define P({i}) = 1/4 for each i = 1, 2, 3, 4. It's easy to see that P(A) = P(B) = P(C) = 1/2. And we can see that P(A and B) = P({2}) = 1/4 = 1/2 * 1/2 = P(A) * P(B). Hence, A, B, and C are pairwise independent (i.e. they satisfy the first three properties). We also see that P(A and B and C) = P(empty set) = 0 =/= P(A) * P(B) * P(C)

[crystal scarab]

got it ty

[floral field]

Why is the sum of infinitely many power series defined if and only if for each $n$, the coefficient of $x^n$ is zero in all but finitely many terms?

[vital dew]

beeswax

[floral field]

Actually, let me just send the statement

I am not quite understanding the paragraph below that equality and I was wondering if someone could help me in understanding that

[stray reef]

@floral field still here?

[floral field]

Yes

[stray reef]

alright so here's how i personally view it

[floral field]

The book also mentioned something about G(x)^n being divisible by x^n?

Sorry, go ahead

[stray reef]

when you add up infinitely many formal power series, normally to get the x^n coefficient of the result you add up all the x^n terms from each summand

but if there's a certain power of x such that every summand contains a nonzero term of that power, bullshit might start happening

bullshit such as the sum of the coefficients accidentally diverging when you didn't mean for it to do so

like if you tried to add 1 + (1+x)/2 + (1+x+x^2)/3 + (1+x+x^2+x^3)/4 + ... and so on, and tried to look at the constant term

you would find that the constant term ends up as the sum of the harmonic series, which diverges. which is bad.

so you DON'T want that happening.

and hence you require that for any power of x, there have to be only finitely many summands that contribute a term with that power.

[floral field]

Sorry, just processing it real quick

Ahh, okay that clears things up. Thank u

[stray reef]

for a series like the one in your picture in particular, by requiring G(x) to have a zero constant term, you will get that G(x)^n does not contribute any terms below x^n

and hence that the x^n term in the sum is affected by at most the first n summands

[floral field]

Wait, in the specific case you gave, what's the composition there?

I'm just trying to see it in terms of the composition of power series

[stray reef]

...F(G(x))?

[floral field]

yes

[stray reef]

sorry, i'm not sure what you're asking here.

[floral field]

Wait actually nvm

[reef tapir]

What’s the minimum project time, I said 45 not sure

@stray reef

[stray reef]

???????

why are you pinging me?

[reef tapir]

Help :/

[stray reef]

why me specifically???

[reef tapir]

Smart person

Reliable

[sudden knot]

[stray reef]

heard that excuse a million times

just because im smart and help other people (of my own volition!!!) does not entitle you to ask for my help unprompted like this

so honestly no, you can get lost. im not helping you

[surreal sand]

is the empty set a subset of the set of the empty set?

[quaint star]

The empty set is a subset of every set, so yes

I assume by the set of the empty set you meant ${ \varnothing }$

[vital dew]

Lunasong the Supergay

[stray reef]

"is the empty set a subset of-" yes

[weak lodge]

Hey everyone. This is my first time using this server.
I've got two questions that the support center at my university couldn't answer for me today. Can anyone help me?

[quaint star]

Ask your questions and you will find out

[weak lodge]

ah ok cool.
So i get how derangements work. But i don't understand derangements with duplications?

in part (i) each grade is different so that's D4. But when two are the same what happens?

[pale epoch]

so you know how to count those assuming that you could distinguish the 80s somehow?

[weak lodge]

part (i) was 70, 80, 90 and 100

so i know how to do that

[pale epoch]

i will take that as a yes

so like, if you could distinguish the 80's in a way, say you have 80_1 and 80_2, then there would be two permutations for what is really just one
i.e. (70, 80_1, 90, 80_2) and (70, 80_2, 90, 80_1) would be indistinguishable (both correspond to (70, 80, 90, 80)) and you are overcounting by a factor of 2

i don't actually know if this is a good explanation

(also you should post the complete question as well...)

[weak lodge]

no that makes sense alright

that's the entire question

I'm not sure but are we just dividing the answer from part (i) by factor of 2 when there's 2 elements the same?

[pale epoch]

reading the full question that doesnt work i think, sorry

[weak lodge]

no worries. i get a derangement of 9 for the first part

[pale epoch]

how so?

[weak lodge]

2 secs i can take a picture of my workings

[pale epoch]

yeah, so division by 2 makes no sense

[weak lodge]

I have notes on how to do permutations of a set with non distinguishable elements. But we covered nothing on derangements of duplicates and i can't seem to link the ideas together

[pale epoch]

think about how many ways there are to give the students with 80 the wrong score and how many ways there are to give the other students the wrong score

[weak lodge]

something like
(4C2)2! ?

[pale epoch]

seems like a lot

well, say person 1 and person 2 both scored 80

for them to get the wrong scores what are the possibilities? just for them

[weak lodge]

2 possibilities. either grade 70 or 90?

[pale epoch]

yeah

but then 70 and 90 are "used", so only 80 is left for the other two guys

so that seems to be it?

[weak lodge]

so the answer is 2?

[pale epoch]

seems like it

[weak lodge]

that seems so straightforward!

[pale epoch]

or do you disagree?

[weak lodge]

not at all.

[pale epoch]

the people with 70 and 90 both have to get a 80

and then there isnt much choice left

[weak lodge]

i was in a math center today and they couldnt figure it out. thanks for your help

i've got one other question that we couldnt figure out. if you want to cast an eye over it?

[pale epoch]

just post it, maybe i do, maybe someone else will

[weak lodge]

ok thanks

If anyone can help me this part (b), it's last the question in 3 past exam papers that i haven't solved.

[pale epoch]

probably just do induction

[weak lodge]

i dont know what to say for it

i think that works for the (a) part? I'm lost how to word part (b)

[pale epoch]

i think that works, yes

but dont think i can come up with a combinatorial argument for b

[weak lodge]

that's ok. thanks for your help with the first one.

[stray reef]

i know how to do a combinatorial argument for b

$\binom{n}{3}$ is the number of ways to pick three numbers from $1:n$.

the middle number can be anywhere between $2$ and $n-1$ inclusive. call it $k$. there is one number in our choice to the left of $k$ (there are $k-1$ ways to pick it) and one number in our choice to the right of $k$ (there are $n-k$ ways to pick it)

[vital dew]

Kanga Gang Annihilator Ann

[stray reef]

@pale epoch @weak lodge

[pale epoch]

oh, nice

[weak lodge]

thanks to both of ye for helping me 🙂

[tepid bay]

Not sure if this is the place for this, but it is part of my final year discrete module:

how do I do the LIFO method to calculate the modelset of a boolean function? my lecturers notes are wild

for example this:

this is the process but the notes explaining the method are quite bad

does anybody know of this?

[simple nova]

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

Does anybody know what can be generated by a PDA?

I'm thinking its between B and C

[bronze basin]

Prove that if there is a function from N onto a set A, then A is countable.

N being the natural numbers

[gusty star]

I need help....

[keen python]

#prealg-and-algebra

[bronze basin]

is a set in bijective correspondence with its preimage?

[ember obsidian]

prove if u think its true, if not give a counterexample

[ashen tapir]

Does anyone know the answer

[lean loom]

Hey all, I've been studying discrete math lately, but I have a question about Complete Partial Orders (cpo) and Continuous functions. I understand why the function not: B -> B is a continuous function, but according to a friend of mine, the following function f: B -> B is not continuous and I don't understand understand why. I thought this function f is monotonous because xRy and f(x)Rf(y) holds.

[stray reef]

do you know the definition of a hasse diagram

@placid cairn

....

no that's just bad

the hasse diagram of a partial order $\leq$ has an edge $x \to y$ iff $x \leq y$ and there does not exist any $z$ such that $x\leq z \leq y$

[vital dew]

Kanga Gang Annihilator Ann

[stray reef]

IN PARTICULAR the existence of an edge $x \to y$ in the hasse diagram implies that $x \leq y$

[vital dew]

Kanga Gang Annihilator Ann

[stray reef]

so IF you had a cycle $x_1 \to x_2 \to \dots \to x_{n-1} \to x_n \to x_1$ THEN you would also have $$x_1 \le x_2 \le \dots \le x_{n-1} \le x_n \le x_1$$

[vital dew]

Kanga Gang Annihilator Ann

[stray reef]

and thus you would get that all points in your cycle are the same

which cannot be

[turbid swallow]

In this Mating Ritual, if n different men went to n different women the first day, will the ritual be over?

2. If a particular woman(X) has only one man(Y) serenading her, but at least one of the women has more than one man serenading her, does this mean X will still be serenaded by Y the next day?

Therefore, when the day arrives, that every man is serenading a separate woman, this means the ritual ends, right?

[vernal thorn]

I'm not too sure what the for each d part means. Do I have to list all vertices 1 for each d or just overall?

[iron marsh]

So I know the answer is no, but I am not sure how to explain it.
The issue is the edge v4v5 in G2 has nothing it can map to in G1

It is a bit wordy, but I think this is sufficient.

[stray reef]

it means there exists one vertex of degree 3, one vertex of degree 9, one vertex of degree 10, one vertex of degree 11, and one vertex of degree 12.

[dim marten]

can anyone explain how

they turned 4^(2m+1) into that (15a...)

this was the original question

[pale epoch]

they used the induction hypothesis

by that $4^{2m+1} + 5^{2m+1} + 6^{2m+1} = 15a$ for some $a$ and thus $4^{2m+1} = 15a - 5^{2m+1} - 6^{2m+1}$

[vital dew]

Lochverstärker

[coarse cave]

im correct right? idk why but someone said this was wrong and it's weakly connected

[stray reef]

you are right this graph is not connected at all

it has two connected components: {a,c,e} and {b,d,f}

there does not exist a path from a to b for example

[coarse cave]

awesome thank you

[fresh venture]

Help

[fresh venture]

<@&286206848099549185>

Anyone there?

[coarse cave]

is this graph possible

with that degree sequence

[hard cape]

I’m interested in learning discrete mathematics. Does anyone know any good learning material or sources where I can learn?

Also what are the requirements before learning this subject?

[vernal thorn]

Are all of these part of 1 tree as it says the tree only contains 1 vertex of degree d?

[stray reef]

???

i mean yes those five vertices are all part of your tree

[fresh venture]

No one knows this?

D:

[vernal thorn]

Oh so its just saying that it has those 5 distinct values of d as degrees of vertices

Thanks

[fresh venture]

What does even number of odd integer mean?

[pale epoch]

the product has an even amount of factors

and every factor is odd

[gritty pumice]

rosen discrete math

no prerequisites

[dim marten]

what is that letter after re

[gritty pumice]

maybe its "let"

[vernal thorn]

would the top vertex have a degree of 2 or 3?

[pale epoch]

$re\vdash$

[vital dew]

Lochverstärker

[pale epoch]

(i also think its let)

[pale epoch]

what do you think and why

[vernal thorn]

i think 3 cos it the degree counts itself and then its children

[pale epoch]

itself?

[vernal thorn]

the point itself and then the ones below it

[pale epoch]

oh, i dont think thats how degree is defined

it counts the number of connected edges

[vernal thorn]

If i extend it like this would the top vertex now have a degree of 3 or would it still be 2?

[pale epoch]

still 2

it just counts the incident edges

[vernal thorn]

ok thank you

[fresh venture]

Ok thanks

How can I solve this?
I only know how to do for smaller numbers

45 will make too many calculations

Is there any easier way to solve?

[gritty pumice]

what does it mean highest power?

to what power does 45 have?

[fresh venture]

It mean if you expand it what will be the power of 45

[dim marten]

am i allowed to send my completed hw assignment in here

[fresh venture]

Answer is 4

[dim marten]

to see if anyone is willing to check it over

[gritty pumice]

just write out the definition of choose

[fresh venture]

45^4 will divide it without giving decimals

[gritty pumice]

you dont need to compute it

[fresh venture]

How?

Can I do like how many 45 powers for 53
Then how many for 27 and 26 and then subtract them

Will that give me the answer?

[gritty pumice]

yes

isnt it 0 though?

[fresh venture]

No

[gritty pumice]

we can see 45^2 on the top and 45^2 on thebottom

[fresh venture]

I used a calculator

It was giving 4

[gritty pumice]

you want so see what power 45 has yeah?

[fresh venture]

Yeah

Power of 45

You know any way?

[gritty pumice]

53 choose 26 / 45^4 is not a whole number ?

[fresh venture]

It is a whole number

But it was too big

[gritty pumice]

ur calculator is cutting it to a whole number

[fresh venture]

Is that so?

[gritty pumice]

i believe so

if we write it as a fraction

we can see 45,5,9 on the top

and on the bottom 5,9,5,9

so should be 0 no?

[fresh venture]

Aah I see

Maybe my calculator round off and did it

Lemme check

[fresh venture]

Ohh wait I don't get where did you got that from

[gritty pumice]

$53C26 = \frac{53 \times ... \times 45 \times ...\times 9\times ...\times 5 \times ..\times 1}{26 \times ... \times 9 \time .. \times 5 \times .. \times 1 \times 27 \times ... \times 9 \times .. \times 5 \times .. \times 1}$

[vital dew]

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

[fresh venture]

Won't we also count 15x3?

[gritty pumice]

oop

you do

so -2?

[fresh venture]

Yeah

Ig that won't be the answer

Ig 0?

Right?

[gritty pumice]

no

45 still has -2 power

[fresh venture]

Ig it's 45 power -1

[gritty pumice]

yeah 😅

[fresh venture]

Nah something doesn't seems right tbh

I am confused

[gritty pumice]

about?

[fresh venture]

I mean if we say remove all 27! From 53!

Then we only need to worry about 26!

There it will generate 45 idk how many times

[gritty pumice]

wym

[fresh venture]

Like 9x5
15x3
Then break 18 into 3x6 and 25 into 5x5
It will give more

[gritty pumice]

oh yh ur right

[fresh venture]

I mean removing.... Like dividing so only 53x 52.... 28 are left

[gritty pumice]

so youll need to be factor into primes

[fresh venture]

Yeah

[gritty pumice]

all of the numners

and count them

[fresh venture]

Idk how many will cancel out

For 45

And how many will remain

[fresh venture]

That will take a lot of time in exam

I don't think that's how we are supposed to do

[gritty pumice]

we can simplify it

to 53 x .. x 28 / 26! right?

[fresh venture]

Yeah

[gritty pumice]

then you count from there

there is probably no better way other than seeing which numbers will factor to a 5 and 3

[fresh venture]

Yeah ig

So we need 5 x 3^2

Form

[gritty pumice]

yea

but collect all 5 and 3's

[fresh venture]

Yeah

I got an example

So I was thinking if I just calculate how many 45s for 53! And subtract those for 26! And 27!
Will that work?

[gritty pumice]

ye

its the same thing

[fresh venture]

That seems easier

[fresh venture]

But idk what this dude is doing in there

[gritty pumice]

but then u also have the case if 26 has a 3 left and 27 has 15 left, you add combine the left overs if u do it like that

[fresh venture]

Can't understand

[fresh venture]

Won't those be counted as well?

[gritty pumice]

depends if u count 26 and 27 seperatly or 26! x 27!

at once

imo i think its easier to simply first

[fresh venture]

Ok

[fresh venture]

I did it

It's coming out to be -1

Ig

[gritty pumice]

sounds right

[night gust]

This is wrong... Right?
S is a relation between two sets, defined by: X >= Y
With X and Y into the set of real numbers.
Question is: X S Y if X = -1 and Y = -2 ?

[urban mantle]

Question about discrete random variable.

If I have a X - set of events and probabilities, and I need to compute mathematical expectation of X => M(X), then I just need to find mean event of set X.

M(X) = x1p1+x2p2...xn*pn.

But what about something like this?

M(2+2X)

How do I compute this one? What operation defines sum of number with set X and multiplication of set X to number? I just don't understand.

[vapid torrent]

you could use linearity of expectation

That would be equal to 2+2M(x)

using the same notation you are

but note, X is not a set of events and probabilities, it's a random variable

it assigns probabilities to events

[urban mantle]

What about M(X^2) ?

[urban mantle]

Oh, you mean that xi and pi are different things. It is not like pi depends on xi, so multiplication inside of M(X*N) just gonna result in changing xi variables, but if forwarding the same thought we must conclude that M(X+2) is gonna change every input of M to be bigger on two

M(X)=x1p1+x2p2...+xn*pn

M(X+2)=(x1+2)*p1+(x2+3)*p2...(xn+3)*pn

But you said that I could just take away const values from M function

@vapid torrent

Sometimes I really regrets that I just understand things entirely different from most people so I had to ask a lot of questions to figure out how something works

Otherwise I most likely do something wrong

My brain just built differently

Wait. It just works. It is really true that M(X+2) will change terms inside of equation, but it still works that I can just take away const variables

wot

Anyway thanks

[sand cipher]

how do i prove this, i thought i had something to do with compliments that could make the problem easier to solve, but my professor said that there is no use of compliments in this problem

[pale epoch]

you take an element of the LHS, show its in in the RHS and vice versa

(you can also just make a truth table)

[sand cipher]

ye that's what i wanna proof, but idk how
also my professor did say that I will need to use DeMorgan law

[pale epoch]

ye, this is demorgan's law

what does it mean for an element to be in the LHS?

you will have to "translate" what that means into logic

[sand cipher]

LHS is the Premise and RHS is the conclusion?

[pale epoch]

LHS is $X - (Y \cup Z)$

[vital dew]

Lochverstärker

[pale epoch]

(left/right hand side)

[sand cipher]

that it will be in X but not in Y or Z?

[pale epoch]

yes, but you will have to write it down more formally

because you then get a statement of the form $a \in X \land \dots$ which you can apply demorgans law to

[vital dew]

Lochverstärker

[sand cipher]

how would i do that like what variable i use,
a exist in x but does not exist in y and z

yep that but what can i say about a, like is it ration an integer or is it just x

[pale epoch]

i mean just look at how set difference and set union is defined

in my example a is just an element of a set

[sand cipher]

so i can say $a \in U where\ a \in X \land \dots$

[vital dew]

Centrous

[pale epoch]

U is some universe?

[sand cipher]

U is some Universal set

[pale epoch]

well

ok

you can do that, but you don't have to

[sand cipher]

so i can skip the part about $a \in U$?

[vital dew]

Centrous

[pale epoch]

yes

X, Y and Z are sets so $X - (Y\cup Z)$ is a set and we can talk about elements of it

[vital dew]

Lochverstärker

[sand cipher]

ok so after defining what X Y and Z how do we turn that into X-y n X-Z,
do we like multiply the x- in there or something like that?

[pale epoch]

i told you how here

read up the definitions of set difference, union and intersection

[sand cipher]

so set difference = in X but not in Y or Z like what we just talk about
union is set ... ^(and) ....
Intersection is the one in common

[pale epoch]

,?

[sand cipher]

a is in x & a is not in y or z?

[pale epoch]

check the definition of $\cup$

[vital dew]

Lochverstärker

[pale epoch]

, means nothing to me

[pale epoch]

eh, that doesnt work

you applied set difference wrong

or distributed it wrong

the statement is $a \in X \land a \notin (Y \cup Z)$

[vital dew]

Lochverstärker

[sand cipher]

so this is U rite

[pale epoch]

yes

well, the "=" here is wrong, but that's what it means kinda

[pale epoch]

do you see how this is applying the definition of set difference?

[sand cipher]

so set difference is A is in X and A is a subset for Y, is what i got(for X-Y)

[pale epoch]

i can't parse this

[pale epoch]

thats not correct

the subset symbol really has no place there

[versed frost]

"A relation R on a set X is said to be reflexive if for all a, b
∈ X, it is true that aRb and bRa." Rough translation from Spanish, but - it'd be false considering aRb and bRa is transitive.

[sand cipher]

what bout this?

[pale epoch]

yes, thats what i used here

now notice that $a \notin Y \cup Z$ is equivalent to $\neg(a \in Y \cup Z)$

[vital dew]

Lochverstärker

[sand cipher]

yep

[pale epoch]

then you can apply the definition of $\cup$ and finally demorgans.

[vital dew]

Lochverstärker

[pale epoch]

that is not what reflexive means
also i fail to see a question?

[versed frost]

What's in quotation marks, it's a true or false question - which I'm pretty sure is false. Since what's denoting is basically transitive.

It's a bit hard translating the nuances in Spanish to English.

I'm legit having a hard time since the professor gave us an assessment to study with no answers to correlate with, so I am basically trying to figure out if I am right - or not. Asymmetrical classes are a pain.

[pale epoch]

oh, then if you translated correctly, the statement in quotation marks is indeed false

but it has nothing to do with transitivity

[versed frost]

Is that so? Huh. The only thing that's asking me out of the assessment is if it's true, or false - but I want to know more beyond that, and even my tutor struggled to make of what my professor wrote in the modules.

So I'm just stumped figuring it out for myself, and my 12 other classmates are just silent on our group.

[pale epoch]

well, if aRb for every a and every b, then every element is related to every other element

this relation is reflexive and transitive, but that's not how either of those things are defined

[versed frost]

Well, that's a pain.

I also have these three other questions that weren't even brought up in the module at all - and I know it's got to do with algebra, and set builder notations, but I don't know how to apply it here.

1. If the relations R and S are symmetric, then R ∩ S is symmetric
2. If the relations R and S are symmetric, then R ∪ S is symmetric.
3. If the relations R and S are symmetric, then R ◦ S is symmetric

Intersection, union, and composition - I think?

[weary tiger]

Hi! Im having a bit of trouble on my homework about graph theory and I read the rules about asking questions and it says that these types of questions should go in the discussions. It's about Kruskal's Algorithm, may I post it?

[pale epoch]

yes

[coral raven]

what does the composition of relations mean

[pale epoch]

you need to have the first on like X \times Y, the second on Y \times Z and then you get the obvious one on X \times Z

you probably didnt ask me...

[coral raven]

oh

no i'd just literally never run into that before

seems pretty awful

and niche

[pale epoch]

no idea if it appears in nature

[pale epoch]

also yes, but i don't want to answer two questions in parallel

also i have to go to bed

[versed frost]

Goodnight.

[sand cipher]

BTW thx @pale epoch

[weary tiger]

Hey no worries! I just figured it out too!

Definitely get some sleep 😂

[rotund delta]

suppose that s is a subsequence of length 7 of distinct characters. how many different length 4 subsequences does s have?

[coarse cave]

How would I do part 2? The translating to postfix

[stray reef]

none of these are proper parenthesizations.

the order of the letters should be w, x, y, z in all of these, and the parentheses must indicate the order of operations unambiguously

remember we are talking about associativity and NOT about commutativity

this is what you should have had:

((w*x)*y)*z
(w*(x*y))*z
(w*x)*(y*z)
w*((x*y)*z)
w*(x*(y*z))

@coarse cave

do you understand why what you have written is complete nonsense?

[weary tiger]

Hi! Im a little confused on this problem on my nearest neighbor graph theory hw, I feel like I followed the algorithm correctly and I've been at this for 20 minutes now and im not really sure what im doing wrong. I put the answer as the path I followed, as what this requires is following the smallest number and ending at the starting vertex, but im just a little confused as to why because I feel confident in my answer (Nevermind! I figured it out, im blind XD)

[latent reef]

Is this question does not have answer

[stray reef]

it does

[latent reef]

bruh wrong channel

[signal basin]

What does usually this notation means: $i=1, \ldots, I$. Does it mean for all $i \in {1\dots,I}$ ?

[vital dew]

baan

[stray reef]

yes

[coarse cave]

yes i do!

ya that makes a lot more sense

I was just confused bc the examples they gave us were with 3 variables

could you by chance know how to utilize the trees to get a postfix?

[stray reef]

[answered in help channels]

[austere musk]

For when is $P(A-B) = P(A) - P(B)$? \\
I have: \
If $A=B$, then $P(A - B) = \varnothing$ and $P(A) - P(B) = \varnothing$ \
If $A \neq B$, then $\varnothing \in P(A - B)$ and $\varnothing \notin P(A) - P(B)$

Is this reasoning correct

Is this correct?

Or have I dungoofed

[pale epoch]

P is powerset?

[austere musk]

Yes

[pale epoch]

powerset of empty set is empty?

[austere musk]

Hmm

O shoot

P({}) = { {} }

[pale epoch]

yes

[austere musk]

Ok the second part is also wrong

[pale epoch]

why?

[austere musk]

Well surely it's equal at some point

[pale epoch]

i think your second argument works

[prime parcel]

Yeah the second seem to work

[austere musk]

When P(A-B) = P(A) - P(B)
If A = B, then P(A-B) = { {} }, and P(A) - P(B) = { }
If A != B, then {} in P(A-B) and {} not in P(A) - P(B)

So it's never equal?

[pale epoch]

no reason to consider cases

seems so

[austere musk]

Enderton is being cheeky I guess

He asked "When is it true?"

[austere musk]

Wdym, is there a nicer proof for this?

[pale epoch]

your second argument works for A=B as well

[austere musk]

Ah right

[open glacier]

I have to show if its injctive, surjective or bijective.
What exactly am I looking for? Set of integers (s,t) so that 2s+1=s+t or that 2s+1= integer and s+t=integer?

It is mapping set of integers to integers, so I'd assume I'm looking for integers

[pale epoch]

"looking for"?

look up what injective, surjective and bijective means and then check if its true or false

[open glacier]

Sure, thats cool, but I'm just asking to know what answer I'd be looking for. Do I select random integers and test or should I first do something with the equations or ...

[pale epoch]

testing is always a good approach

just plug in about 10 different tuples, see what happens

[open glacier]

Okay heres a question: with injectivity definition, would f(x1) be a set (s,t) or just s?

[pale epoch]

notice anything not mapped to? try to find a preimage
notice a "collision"? its not injective! try to force collisions

there is no f here

the function g takes in tuples of integers and spits out tuples of integers

g((0, 0)) = (1, 0) for example

[open glacier]

Okay so you're saying that its not injective because it is possible to find set of imaged integers that are mapped by multiple different sets of g(s,t)

[pale epoch]

no

set is the wrong word

and im saying that if that is the case, then its not injective

if you find say $(s_1, t_1)$ and $(s_2, t_2)$ with $(s_1, t_1) \neq (s_2, t_2)$ but $g((s_1, t_1)) = g((s_2, t_2))$ its not injective

[vital dew]

Lochverstärker

[open glacier]

Got it, thank you. I did kind of understand the definition, just wondering if I should find tuples to find a collision

[pale epoch]

well, you should try

doesnt mean you will find any

[open glacier]

Cant say its injective just because I dont find any either

[pale epoch]

true, but looking for it you might notice a reason why it must be injective

so if you dont just see a reason why its (not) injective, you have to do something

[open glacier]

Question is, what is that something ^^

I do see that 2s+1 is always odd number

That most likely has something to do with it

[pale epoch]

yes, you can use that to show its not surjective

injectivity will be a bit more tricky i think

[open glacier]

Yeah surjectivity is quite easy, I suppose I'll try finding a collision. Otherwise i'd have to start doing some matrix equation stuff

Saw it done on google..

[pale epoch]

matrix equation stuff

take like g((0, 0)) = (1, 0), can you find another element mapped to (1, 0)? why / why not?

[open glacier]

Quite an obvious example to bring as its quite apparent it would be easiest way to show its not injective.

It is not possible to find another pair of integers so that we'd get (1,0)

[pale epoch]

yes, but why not

[open glacier]

Because s has to be 0 to have (0,) and t has to be 0 in order to get (,0)

Best I could come up with.

There is no other pair of integers (s,t) besides (0,0) to get (1,0)

Pardon if I'm being stupid but I honestly don't see any other way of proving it without just stating the obvious

[pale epoch]

t doesnt have to be 0 to get 0 in the second coordinate of the image

g(1, -1) = (3, 0)

is there any other way you can get 1 in the first coordinate though?

[open glacier]

There is not.

I suppose that there is the answer that you've been directing me towards so patiently.

[pale epoch]

yes, now you just need to figure out if 1 is special in this regard, or if it works for any first coordinate and formulate the argument

[open glacier]

Just to be clear - we've concluded that indeed it is. Is the conclusion what you meant by "figuring out"?

All I see is left now, as you mentioned, is building the argument based on data.

[pale epoch]

the conclusion is injective

in particular you cant "fabricate collisions" in the first coordinate

for the argument you can just consider an arbitrary point like (1, 0)

the same argument will apply to any point in the image

with maybe minimal alterations

[north dust]

Exponential generating functions and Lucas numbers, ahh

[north dust]

I can't believe I had to figure out how to do partial fractions in order to find the closed form for a formula for Lucas numbers, ahhh

[rich siren]

Determine the smallest maximum number of comparisons needed to merge sorted lists with 5, 6, 7, 8, 20, and 29 elements?

How would I start with this problem?

[north dust]

I can't seem to get the exact formula for Lucas numbers via exponential generating functions

[cerulean wind]

coolest way to do this is linear algebra imo

[versed frost]

"The relation R at {1, 2, 3, 4} defined by (x, y) ∈ R if x^2 ≥ y" - question is, how would I be able to write this as a table?

[pale epoch]

row and column entries for the set elements and then some marker to show if the pairs are in R or not

[versed frost]

Sorry, what I meant to say was - if I have x^2 that means I would have to set all values in the domain to the power of 2? And in which case, what would the y values be? Would they be the same? In which case, it'd be (1,1) (2,1) (2,2) (2,3) (2,4), etc. (?)

[stray reef]

you're overthinking it.

[versed frost]

That's my biggest sin.

[stray reef]

if you want to write this as a table, then you just... yknow

write a table

and check every pair (x,y) against the inequality x^2 ≥ y

that's it

[twin narwhal]

def seperator(lst):
    """
    lst is a list of integers
    returns a list of odd and even numbers from lst
    """
    odd = []
    even = []
    for i in range(len(lst)):
        if lst[i] % 2 == 0:
            even.append(lst[i])
        else:
            odd.append(lst[i])
    return even, odd

anyone got any tips to find the loop invariant(s) and the variant(s)? im trying to prove this algorithm is correct

for the variant i was thinking len(lst[i::]) because it gets smaller with each iteration until its 0

[pale epoch]

a loop invariant is either true or false

and it gives you correctness at termination

[twin narwhal]

yeah

[pale epoch]

how does len(lst[i::]) satisfy any of this

oh wait you said variant

nvm me lmao

i dont know what a variant is but reading the definition rn this probably works

[twin narwhal]

hold on lemme make the function a bit easier invariant wise

a variant is basically a termination condition that is always decreasing and the loop guard and invariant imply that v >= 0

[pale epoch]

it should work after a sufficient amount of reformulations

yeah with your edit its better

[twin narwhal]

coz loop guard is i < len(lst)

so i was thinking that the invariant should be 0<=i <= len(lst)

that way i can get that my variant V = len(lst) - i(i changed it just now lol) is >=0

[pale epoch]

sure i think

you need to add more info to the invariant though

[twin narwhal]

like len(odd) + len(even) <= len(lst)?

[pale epoch]

thats not true though?

but i meant you need to state things about what the algorithm actually does

[twin narwhal]

whoops looks like i forgot

[pale epoch]

so that when i is whatever value it is at termination (len(lst) i guess) you get correctness of what your algorithm actually does

[twin narwhal]

so this algorithm just seperates the integers into two lists one of odd numbers and one of even numbers

[pale epoch]

yes, so your invariant probably needs to talk about odd and even

and well, the original list

[twin narwhal]

so then this doesnt work right for an invariant?

[pale epoch]

its not even true, right?

the length of odd and even change with each iteration

but the length of list is static

oh

<=

i should probably go to bed or sth

i mean you can add that

[twin narwhal]

what time is it where you are rn?

[pale epoch]

unimportant

[twin narwhal]

true

[pale epoch]

i dont think you need this in the invariant

but adding it doesnt hurt

[twin narwhal]

the <=?

[pale epoch]

the whole statement

with <= its correct (i read ==)

[twin narwhal]

so rn it would be i<= len(lst) and len(odd) + len(even) <= len(lst)

[pale epoch]

you still need to talk about what the algorithm actually does

[twin narwhal]

yeah in the proof

[pale epoch]

otherwise you wont get correctnes

the invariant has to give you correctness for i = len(lst) + 1

[twin narwhal]

wait why len(lst) + 1?

[pale epoch]

thats when the algorithm terminates?

[twin narwhal]

doesnt it terminate when i = len(lst)?

[pale epoch]

it depends where you start counting, if 0 or 1

[twin narwhal]

0

[pale epoch]

then you probably need i < len(lst) in the invariant i think

[twin narwhal]

alright thanks

[pale epoch]

then it terminates at i = len(lst)

but you still need a statement about what the algorithm is supposed to do

do you have some example of a loop invariant?

[twin narwhal]

for like a different piece of code?

[pale epoch]

ye

[twin narwhal]

without lists yes, with lists no

[pale epoch]

look at wikipedia: https://en.wikipedia.org/wiki/Loop_invariant

the example invariant for finding a maximum in a list is something like
"m stores the maximum of list[0..i]"

you need something like this

so that when the algorithm terminates (and your invariant is always true), you get correctness

[patent fulcrum]

Hi. Can you give me an example of non-computable subset of naturals?

[stray reef]

the set of turing machines that halt

(under some encoding of turing machines)

[patent fulcrum]

Is the set of all turing machines isomorphic to naturals?

[stray reef]

it's isomorphic to a subset of N

exactly which subset depends on exactly how you encode turing machines, of course

[patent fulcrum]

Turing machine is N -> N, so there are N^N turing machines which is bigger than N

I'm not getting this

N^N ~ R ~/~ N

[stray reef]

??

do you think every function N -> N has a turing machine which calculates it

[patent fulcrum]

[stray reef]

there are N^N turing machines

[patent fulcrum]

Considering the fact that there are non-computable subsets

No

But then I'm not getting this

Also how do you prove that fact

Ahhh because to get if an algorithm halts is impossible

Makes sense

But how do you prove that there are N turing machines?

[stray reef]

the description of any turing machine is finite

[patent fulcrum]

Heh

Interesting pov XD

We can even say that a turing machine is no more than a word in some language with finite alpahbet

Whcih obviously making it ~ N

Thanks

[autumn horizon]

which one is which

[gritty pumice]

you just want a path between every node i believe

in ur picture, they are all connected except the top right

[restive surge]

If a multivariable diophantine polynomial has at least one nontrivial zero, Will there be more nontrivial zeroes that aren’t just multiples of the first?

The one i’m looking at specifically is a 4d quartic with no combatants and the last term is just -n^2. I’ll post the full thing and the solutions I found when I have time.

It is 4x^4y^2-8x^3y^3+4x^2y^4+y^2z^4-xyz^4+4x^2z^4-n^2=0 and the solution is x=18 y=25 z=35 n=14875
and subsequent multiples by just multiplying all of them by some constant.

[split drum]

The line in front of the first interval is a negative. It's meant to be $(-\infty, 0]$. I'm struggling to come up with a proper bijection between these sets to prove their numerical equivalence. Does anyone have any tips on how to do this beyond just playing around with random functions until one works? I know I could also form a bijection between each set and $\mathbb R$ individually, which would also show that they are equal (numerically). I'm not sure which approach to take.

[vital dew]

Umiguess4000

[split drum]

<@&286206848099549185>

[proven silo]

probably easier to just construct two injective functions if allowed

otherwise probably easier taking a detour around [0,1) or smth than a bijection between those 2 sets, so create bijections from the 2 sets to [0,1)

[restive surge]

I’ll ask in a help channel

[graceful nimbus]

anyone

i cant find the set of integers

[austere musk]

Guess em

What numbers are congruent 6 mod 13 @graceful nimbus

So if this was set of numbers congruent 3 mod 7

I would think:
3 mod 7 = 3
Whats the next number:
p mod 7 = 3?

And after trying a few I'd get 10

10 mod 7 = 3

And so on, and so on until I have the list:
3, 10, 17, 24...

And if you notice they're all numbers: 3 + ? + ? ...
So I'd write my set S recursively as:
Let 3 ϵ S, (start with 3 is in S)
Then n ϵ S ⇒ n + ? ϵ S, (if a 'number' is in S, add ? will also be in S)

[split drum]

Ooh, I didn't even think of that!!

Thank you 😭

[graceful nimbus]

damn that helped a lot

tysm

hey @austere musk sry for the ping but if ur familiar with congurences can you help me out with 1 more exercise 😓

[austere musk]

i might not be able to but if you post it here someone else may be able to

[sour arrow]

Solve 497x + 121y = 23 using Euclidean algorithm GO

@graceful nimbus

[graceful nimbus]

x = -115 and y = 28

[sour arrow]

Oh you actually did it haha. Okay, well, your answer is then -115

@graceful nimbus

[graceful nimbus]

oh alright

[sour arrow]

As once you take mod 121 of the equation I gave, you get the equation you're trying to solve

[split drum]

Can someone confirm this function definition for me? For $f: (-\infty, 0] \rightarrow (0, 4]$, we can define $f(x) = \frac{4}{1-x}$.

[vital dew]

Umiguess4000

[autumn horizon]

does anyone know how to solve this?

[sharp ledge]

Anyone could help ?

[signal basin]

What does this mean "the nodes are ordered so that i < j for all arcs (i, j) ∈ A"?

Does it mean that (i,j) is a forward arc?

[stray reef]

wym by forward arc

if you mean "an arc whose end has a higher number that its start" then yeah

@signal basin

[signal basin]

Is you stand at node s you look at node t, and what you seee is "s ---> t" — this is what i call a forward arc

i'm not sure what that means, still

it could be that the nodes in the graph are denoted by a,...,e.

what sense does i < j then make?

[stray reef]

can you show the whole paragraph or section where you saw this phrase

[stray reef]

the nodes are ordered, and it's implied they are ordered by numbering them from 1 to n

[marsh cliff]

Asking here too 🙂 Anybody aware of a longer list than 212 terms of https://oeis.org/A132581 (https://oeis.org/A132581/b132581.txt)

[neon fulcrum]

Hello

Given: If you do not do your laundry, your parent will not be happy with you.

Lets say that the above is p -> q

then what is this? You do your laundry because your parent will be happy with you.

~p -> ~q ?

[proven breach]

Do I go into a help channel if I need help ?

[neon fulcrum]

yes

or to one of the subject channels like this one

Many schools are doing finals this week and next so it might be hard to get help though just FYI

[proven breach]

Very true. That's what I'm doing right now. ✅ I'll post my question and just come back to it. Thanks for the reply.

[weary tiger]

Could there be a simple graph with 12 vertices of 3 degrees each?

[quaint raft]

any hints, I can only show <12

[narrow sorrel]

Can anyone explain what does Id+ stand for in boolean algebra? tia

[last flicker]

assumedly the identity under +

[narrow sorrel]

Thanks!

[ornate cliff]

What does a path of length 0 look like? Is it just one node/vertice? Or no nodes/vertices?

[last timber]

what is your definition of path and length?

but presumably empty path or just somethink like {v1}

[ornate cliff]

Path: sequence of nodes where no edge is traversed more than once
Length: edge between 2 nodes

[ornate cliff]

Okay thank you!

[last timber]

ok yes then {v1} or {}

[sharp ledge]

A country uses as currency coins with values of 1 peso,
2 pesos, 5 pesos, and 10 pesos and bills with values of
5 pesos, 10 pesos, 20 pesos, 50 pesos, and 100 pesos. Find
a recurrence relation for the number of ways to pay a bill
of n pesos if the order in which the coins and bills are
paid matters.

[outer hinge]

I have an exam in about two hours and I barely know anything about our proofs

It’s my final

[kindred raptor]

there are 3 red ball / 4 blue ball / 5 green ball
a) how many combination for picking 3 redball together 4 blue ball together and 5 green ball together
b)how many combination for picking 3 redball together 4 blue ball together

i think
answer for a is 12C3 + 9C4 +5C5...... i guess

but idk how to do b

7C5+(12C3 + 9C4)???????

[grave totem]

yes, domain is not R

R\{5}