discrete-math

[valid wave]

i was trying to look at examples but im totally stumped

[pale epoch]

so two graphs are related

and you dont have to look "inside" a specific graph

[valid wave]

oh

so what about the bijective functions portion

[pale epoch]

the simplest example of isomorphic graphs is just renaming the vertices

well

[valid wave]

ah so

if thats the case would I have something like u, v e V and u~v so theres a path

[pale epoch]

a graph isomorphism is a map between the vertices of two graphs

[valid wave]

so i dont have to specify which graph

[pale epoch]

there are no paths here

[valid wave]

ohh crap

so i wouldnt use reflexive transitive etc

[pale epoch]

what do you mean by use

here is a simple example of a graph isomorphism

[valid wave]

so I have to show that each vertex "maps" onto another vertex

[pale epoch]

f is a bijection between the sets of vertices

in this case {1, 2, 3} and {A, B, C}

and it preserves adjacency

so {x, y} is an edge if and only if {f(x), f(y)} is

for example {1, 2} is an edge in LHS and {f(1), f(2)} = {A, C} is an edge on the RHS

you have to show that this relation is an equivalence relation

so that there is such a map f from every graph to itself

that if a graph G is isomorphic to a graph H, then H is also isomorphic to G

and that if G is isomorphic to H and H to J, then G is also isomorphic to J

[valid wave]

wow that makes sense

so that there is such a map f from every graph to itself
that if a graph G is isomorphic to a graph H, then H is also isomorphic to G
and that if G is isomorphic to H and H to J, then G is also isomorphic to J

this is how i would apply the bijection

instead of the transitive, reflexive etc

[pale epoch]

well

the corresponding terminology for bijections i guess is

inverse of bijection is bijective

and composition of bijections is bijective

[valid wave]

so that still holds

the

transitive, reflexive etc

but just being applied to the whole graph

and the idea of isomorphic

🤯

another sub noob question

how do i know to apply that equivilance relation to the idea of isomorphic

[pale epoch]

(if you wanted you could interpret this as a graph but the vertices are other graphs)

[valid wave]

also how would a formal proof of that work

seems like i wouldnt have to put much

[pale epoch]

you get existence of bijections for free, but you have to verify that they are actually graph isomorphisms

and well, we want isomorphisms to be equivalence relations

an equivalence relation is a generalization of equality (=)

[valid wave]

ah ok

[pale epoch]

and we dont want to consider graphs with i.e. differently named vertices as separate objects

[valid wave]

but i guess my question is more so

so that there is such a map f from every graph to itself
that if a graph G is isomorphic to a graph H, then H is also isomorphic to G
and that if G is isomorphic to H and H to J, then G is also isomorphic to J

this explanation here

how isnt this already the answer

i dont see how i would detail this in a proof

[pale epoch]

you have to show that such maps exist

[valid wave]

ahhh

using properties of

isomphism

[pale epoch]

like

the easy case is reflexivity

a graph is isomorphic to itself

you can just take the identity map on the vertices

then symmetry is you take two graphs G and H

and a graph isomorphism f: V(G) -> V(H)

[valid wave]

ahhh

🤯

[pale epoch]

and you have to (more or less explicitly) find a graph isomorphism g: V(H) -> V(G)

[valid wave]

so i have to use my graphs as the like testing sets

omg

that makes sense

okok

last question

😳

[pale epoch]

(this will just be the inverse of f, but you have to verify that is a graph isomorphism and not just a bijection between the sets of vertices)

[valid wave]

so that there is such a map f from every graph to itself

this proves reflexitivty?

[pale epoch]

it shows that the relation defined in the question is reflexive

where two graphs are related iff they are isomorphic

[valid wave]

gotcha

ok my mind expanded

so the idea of bijection always changes based on what im applying it to

so here isomorphic

im showing how isomorphic is equivilent

then using the graphs in my set to prove it

gotcha gotcha

ok i think i got it

Because an isomorphic graph maps to itself, V(G) -> V(H) so let v e V v~v so it is reflexive (empty path) @pale epoch

is this correct way to think about it?

[weary tiger]

does anyone know what step to take after this to simplify the expression to n+1/k bin(n/k-1)?

[obtuse lance]

,rotate

[obtuse lance]

you could think of the (n+1-k)! term as being (n - (k-1))!

now it should be more clearly binom(n,k-1)

[weary tiger]

yeah, i don't see that clearly

[obtuse lance]

work backwards

write out binom(n,k-1)

try to match terms up

[weary tiger]

ah

i see

it's late here haha... thank you

i wouldn't have seen that

[spare patio]

Is my proof valid?

<@&286206848099549185> pleasehelp me hehe

[pale epoch]

this is written down really weirdly

why do you assume a or b > 1 not true?

[spare patio]

so that i can inverse my hypothesis

[pale epoch]

what hypothesis

[stray reef]

"Assume that n = ab where a, b > 1 is not true"
a, b > 1 not true == either a or b is 1, and your factorization is no factorization at all

[spare patio]

that any 3 digit composite numbers has a prime factor less tha or equal to 31

[stray reef]

that's your goal

not a hypothesis

[spare patio]

yeah my conclusion

I need it to be greater than 31

[quaint star]

Le sigh, I answered in #proofs-and-logic but you moved for no apparent reason. Read. The. Rules. #❓how-to-get-help...

[stray reef]

you need what to be greater than 31?

[quaint star]

Ann seems to helping now though, so it's fine.

[spare patio]

i need the a,b >31

so that there is contradiction

[stray reef]

what even are a and b?

[spare patio]

a and b are the factors of n which is a 3 digit composite number

[stray reef]

'the' factors

okay, so you are factorizing n in some way.

notably, you cannot assume both a and b are prime, as you seem to be doing fsr

[spare patio]

sorry bro I'm really panicking right now

[stray reef]

oh you're panicking?

go calm yourself down.

[spare patio]

yeah I'm really bad at math

[stray reef]

deep breaths, drink water, make sure your needs are met, etc. then we can talk.

i will not continue until i am 100% certain you have calmed yourself down from your state of panic

[spare patio]

I want to contradict 100lessthan or eqaul n less than or equal 999

[stray reef]

calm yourself down.

[spare patio]

i'm good now

[stray reef]

...okay

[spare patio]

since there is already a helper

[stray reef]

you can write <= for ≤ in plaintext, by the way.

anyway!

ok

you have n = ab

[spare patio]

oh ok

[stray reef]

and you need to require a and b to both be greater than 1, so as to exclude the trivial factorization n = n*1 which is entirely unhelpful here

[spare patio]

n = ab where either a or b is a prime

[stray reef]

oh, so you're requiring one of them to be prime.

[spare patio]

yeah

that's why i do a or b >1

[stray reef]

why or?

[spare patio]

because the question only wants a prime factor that is <=31 for n

100<=n<=999 such that a or b <= all primes <= 31

[stray reef]

you read me saying "you need to require a and b to both be greater than 1"

and you replace the and with an or as if they are interchangeable somehow

[spare patio]

oh so i need to write a and b > 1?

[stray reef]

if you wish to put it that way, yes...

i mean, really, your requirement for one of the factors to be prime is a little extraneous.

[spare patio]

extraneous?

[stray reef]

extraneous.

unnecessary.

[spare patio]

oh so what should i put here?

[stray reef]

it will be enough to show that if n = ab with a, b > 1 (with no assumption on which one of them, if any, is prime), then at least one of a and b will have to be ≤31.

well, almost enough. there's still a little work to be done afterward.

[spare patio]

is the , red as or?

[stray reef]

no

[spare patio]

omg

[stray reef]

a, b > 1 is shorthand for (a>1) AND (b>1)

[spare patio]

i though commas are ors

[stray reef]

commas are context-dependent symbols

we know that n ≤ 999 and that n = ab with a and b both greater than 1. we wish to show that at least one of a and b is less than or equal to 31.
if the conclusion were false, i.e. if a and b were both ≥ 32, then ||we would have ab ≥ 32^2 = 1024.||
||and that would contradict n ≤ 999.||

[spare patio]

oh ok what i meant is that 100<=n<=999 wherein n=ab where a,b>1(so that they are considered prime or composite). Then by inversing a,b>1 I can say that a,b<=allprimes<=31 is not true giving me the inverse a,b>=32 =1024 that will contradict my first statement 100<=n<=999. Therefore, it must be true that a,b<=allprimes<=31

[stray reef]

your wording is kinda wack

what even is "allprimes"

[spare patio]

all primes <= 31

[stray reef]

are you saying a and b have to be less than or equal to 2, 3, 5, 7, 11, 13, 17, 19, 23, 29 and 31 all at once?

(i.e. that a and b both have to be at most 2?)

[spare patio]

no just 1 of them need to be at a time o that n has a factor <=31(primes)

[stray reef]

you're running yourself in circles

seriously

[spare patio]

what if i do this wait

100<=n<=999 wherein n=ab where a,b>1(so that they are considered prime or composite). Then by inversing a,b>1 I can say that a or b<=all primes<=31 is not true giving me the inverse a or b>=32. Thus ab >=32^2=1024 that will contradict my first statement 100<=n<=999.

[stray reef]

do you just use wherein to sound fancy

[spare patio]

no i just use it so that there is a condition

[stray reef]

"(whatever) ≤ all primes ≤ 31" is still bullshit. being less than or equal to every single prime under 31 means being less than or equal to 2 !

i don't know why you're in denial about that.

[spare patio]

ok so i will remove it

[stray reef]

and the (so that they are considered prime or composite) is also completely unnecessary and adds nothing

and why "inversing a, b > 1"? do you want to run up against someone factorizing n as n*1 on purpose?

you're making this way more complicated than it needs to be

way way way more complicated

the argument is simple:
write n as the product of two factors. the claim is that one of the factors must be at most 31. why is that?
if they're both 32 or greater, then n ≥ 1024. but n can't be greater than or equal to 1024, since it's a three-digit number. and we can't have that.

there is no need nor reason to twist and stretch it to fit bureaucratic language standards

[spare patio]

n<=999. n=ab where a,b>1. We need to show that at least a or b <=31. If a or b < 31 then ab < 31^2 = 961, if a or b = 31 then ab=31^2 = 961, if a or b > 31 then a or b >=32 where ab >= 32^2=1024. a or b <= 31 satisfies n <=999 but a or b >31 does not. This means that any three digit composite number must have a prime factor that is less than or equal to 31.

@stray reef

[stray reef]

If a or b < 31 then ab < 31^2 = 961, if a or b = 31 then ab=31^2 = 961, if a or b > 31 then a or b >=32 where ab >= 32^2=1024
this case analysis is pointless, non-exhaustive, and incorrectly written.

[spare patio]

Oh my pardon me

[stray reef]

you say "a or b < 31" but then just pretend a and b are both less than 31

[spare patio]

so can i say both of them are <=31?

[stray reef]

does it even matter

you literally don't need the case analysis here

[spare patio]

ok letme try again

ab=n<=999 where a,b>1. If a,b>31 then ab >=32=1024 which is a contradiction to the first statement. Therefore, a,b <= 31 and any 3 digit composite number must have a prime factor that is less than or equal to 31.

@stray reef

[stray reef]

better but not by much

[spare patio]

Is it correct?

[stray reef]

no there are still issues with it but i'm too tired to point out every single one

[spare patio]

Let n=a⋅b≤999 with 1<a≤b. Then a2≤a⋅b≤999, hence 1<a≤31. It follows that a, and therefore n, is divisible by a prime ≤31

[pale epoch]

this is unrelated but quite interesting that the correct idea is present in the original proof but it still took Ann a very long time trying to remedy all that is wrong with the writeup

[spare patio]

what should i write?

[pale epoch]

this is more or less fine

but you should write what you think is correct

is this homework?

[spare patio]

yup

[pale epoch]

is it graded?

[spare patio]

yea but just bonus

[pale epoch]

im just asking if you will get feedback

[spare patio]

I'm at the bottom of the class so pardon me

[pale epoch]

all good lol

as i said your latest attempt is fine

there is a few things

i.e. there is no reason to assume a,b > 1

you can start with an arbitrary factorization

and then assume that no factor is <= 31 and arrive at a contradiction like you did

[spare patio]

oh ok can i try again?

[pale epoch]

what you could (maybe should) do is think about why it suffices to consider a factorization into a product of two factors

[stray reef]

wait what? don't you want to show n has a prime factor ≤31? if you allow a or b to be 1 then someone could apply the argument to n=199 or something by factoring it as 199*1

[pale epoch]

oh yeah sorry, you are right

i guess i would assume one factor prime

[spare patio]

ab=n<=999 where a,b>1 . Assume that a,b is not <= 31 . This will give us a,b>31 which is a,b>=32. This means that ab>=1024 which is a contradiction. Therefore, a,b <= 31 and any 3 digit composite number must have a prime factor that is less than or equal to 31.

[pale epoch]

but yes, Ann is right, i didn't think enough

[spare patio]

Thank you @stray reef and @pale epoch

[past swift]

if 2 sets, set A {1,2} and set B {1,2} would the difference of 2 sets be just empty?

is that a thing

[unreal stump]

Yes

[past swift]

thanks a lot

[hybrid tendon]

How do I find the number of factors of a number N that are less than some number x?

[pale epoch]

you compute all the factors and check which are less than x

[hybrid tendon]

Any other way other than computing all the factors? and checking every factor

[pale epoch]

exact values i doubt

in special cases you can give estimates, but in general it seems hard

like, if your number consists of a lot of small prime factors you can throw logarithms at it to get an estimate

[weary tiger]

Could anyone help me out in this problem?

I feel like i have to use inclusion/exclusion but can't really figure out how

[prime parcel]

We get 7350

Ways

[stray reef]

@prime parcel don't just give out answers

also that number looks out of the blue, how did you get it

[weary tiger]

Hmm I ended up distinguishing 6 cas

[stray reef]

6 cases based on where the ambidextrous players go?

[weary tiger]

Yup exactly

[stray reef]

sam's answer doesn't match mine

what'd you get laïka

[weary tiger]

I have just left it in this form

[stray reef]

aight

lets see

this looks right-ish

,calc choose(7,5)

[vital dew]

The following error occured while calculating:
Error: Undefined function choose

[stray reef]

damn ok

well luckily i have some binomial coefficients precomputed on paper

,calc 21 * 28 + 21 * 56 * 2 + 21 * 70 * 1 + 35 * 2 * 28 + 35 * 56 * 2 * 1 + 35 * 1 * 28

[vital dew]

Result:

11270

[stray reef]

yup checks out

i did the same calculations

[weary tiger]

I haven't bothered calculating

Cool

[stray reef]

so either we're both right, or we're both wrong in the exact same way

[weary tiger]

I'm looking on this question now but not sure whether I'm doing the right thing here

I've done polynomial division

and got something like

$-1 + \frac{5}{2(1-2x)} + \frac{3}{2(1-2x)^{2}}$

[vital dew]

Laïka

[weary tiger]

ye

can't get the -1 in the sum tho

wdym

[stray reef]

it'll affect only the first term

constant generating function = sequence with a nonzero first term and everything else zero

[weary tiger]

so the above thing becomes $-1 + \frac{5}{2}\sum_{n=0}^{\infty}(2x)^{n} + \frac{1}{2}\sum_{n=0}^{\infty}(n+3)(2x)^{n}$

[vital dew]

Laïka

[stray reef]

yeah sure

[weary tiger]

Wow that completely went off my mind so -1 is just the gen func of a0 = -1 then the rest 0?

[stray reef]

yes

[weary tiger]

Thanks!

[prime parcel]

Yes that's the answeri got

[stray reef]

and this is not equal to the 7350 you blurted out

[prime parcel]

Oh wait I see I forgot that I was going to write the addition of ways 7350 was just the thing I got form 4 cases

I was going to write like 7350+3920=

Mb I just wrote half and didn't see it

[weary tiger]

Ann could i bother you to check my graph theory question in #combinatorial-structures @stray reef

[stray reef]

nyeh... i guess

[exotic warren]

i have a question about truth tables if someone can help

@stray reef ye?

[stray reef]

.-.

you should post your question instead of asking for someone and/or pinging random ppl

[exotic warren]

nvm its 4th

[weary tiger]

Suppose we have a sequence of n-2 elements from the set {1,2....,n} (repetition allowed)where n>2021

How many such sequences are there with 2020 repetitions of 1?

[last timber]

@weary tiger it is basically the same as saying how many sequences of length n-2020 without ones there are BUT you then have to check possible permutations

[latent galleon]

krieg

listen buddy I will love you forever

if you can tell me how to write this sentence using quantifiers

There is a man who came to the meeting, and there is a man who is absent from the meeting

[weary tiger]

you mean n-2020-2 right?

cuz we had n-2 elements initally

Actually i'm trying to figure out a wider question

About the number of trees with vertex set {1,2...,n} such that vertex 1 has degree 2021

I basically went down the prufer code route

if vertex 1 has degree 2021 then it appears 2020 times in the prufer code

so i'm trying to figure out how many prufer codes there are with 2020 repetitions of 1

[vital dew]

Commander Vimes

[last timber]

@latent galleon

[latent galleon]

thank you sir

[exotic warren]

i picked the first and last, was i wrong or right? thats all i wanna know

[marble gull]

HI everyone, I need some help with stat exercise

[latent galleon]

Are logic gates actually useful programming wise. What are the real life applications of them?

[coral raven]

every single computer ever

lol

[latent galleon]

I understand that but programming wise

For circuits I understand that logic gates are used

[coral raven]

oh, well

[latent galleon]

Everything I've learned so far in my class I can see a correlation to programming but for logic gates I'm struggling to see

Maybe it's more of a computer architect ordeal

Also I have a quick question

If we have p-->q and q-->p is it false to say that therefore p and q

[coral raven]

yes

both p and q could both be false while satisfying those conditions

[mint bane]

this has been bothering me all morning

is b just [n] and [n+1]

[mint bane]

<@&286206848099549185>

[coral raven]

what do you mean [n]

[mint bane]

well i started by thinking about the equivalence class of 1

and thats just all odd numbers i think

the equivalence class of 2 is just all even numbers

[coral raven]

yes

[mint bane]

and then the equivalence class of 3 is the same as the equivalence class of 1

[coral raven]

yes, that's what equivalence class means

if all odd numbers are in the equivalence class of 1

well 3 is an odd number

[mint bane]

so then the only distinct equivalence classes are given by two numbers that are 1 apart right

[coral raven]

yes

oh, that's what you meant by that

yes

[mint bane]

so those can be given by n and n+1 right, where n is just some integer

[coral raven]

yeah

[mint bane]

LETS GOOOOO

i was talking w a friend about this and they were making me doubt myself so much

[coral raven]

your notation kinda confused me

it doesn't say what the equivalence classes actually are

i'd rather just say the equivalence classes are {2n} and {2n+1}

evens and odds

[mint bane]

yeah idk it's just the notation prof used for the class

[coral raven]

yeah that's fair

[mint bane]

but n and n+1 work as well as 2n and 2n+1 right

[coral raven]

well [n] and [n+1] works, as does {2n} and {2n+1}

[mint bane]

okok j making sure lol, merci

[woeful crag]

hello

how can i prove that every vertice in a cycle graph has a degree of 2?

[obtuse lance]

what's your definition of a cycle graph

[woeful crag]

its a graph where you can start at any vertice and return to that starting vertice

and u need to have at least 3 vertices in a cycle graph

[obtuse lance]

what does it mean to start and return, a complete graph with 4 vertices would satisfy this, but I wouldn't call that a cycle graph

[woeful crag]

i guess your walk from one vertice to another goes through each verices when returning to your starting point??

hmm actually a complete graph also saftifies that

@obtuse lance could u give me a clue?

i mean in a cycle graph with n vertices must have edges between {1,2}{2,3}...{n-1,n} and {n,1}

[obtuse lance]

so this is your definition of a cycle graph?

[woeful crag]

yea

[obtuse lance]

the degree of a vertex is the number of edges it's connected to right

[woeful crag]

yes

[obtuse lance]

so what edges is the vertex k in?

it's in {k-1, k} and {k, k+1} only

[woeful crag]

hmm right, and that has a degree two

[obtuse lance]

yeah

[woeful crag]

cheers i think im just overthinking it

thanks you v much

[obtuse lance]

yeah you're welcome

lots of stuff at this stage boil down to checking the definition of things, if you're unsure how to prove something think about the definitions more and make sure you understand them

[woeful crag]

i see, i'll keep that in mind

[steep edge]

HI

WHICH CHANNEL SHOUKD I SEND MY PROBLEMS FOR SETS AND SERIES AND SEQUENCES ?

[weary tiger]

if f(x) is the generating function of some sequence (an) then how can I write $\sum_{n=0}^{\infty}na_{n}x^{n}$ in terms of f(x)?

[vital dew]

Laïka

[obtuse lance]

yep, it's xf'(x)

[weary tiger]

Thanks ^^

[obtuse lance]

any polynomial in n multiplying a_n can be gained through repeated differentiation and multiplying by x and sums like this

just be careful, getting n^2 is not the same as x^2 f''(x)

you need to do x(xf'(x))'

[weary tiger]

I get it

Also how do we prove that a generating function is some transformation of the other?

Do we just have to show that they count the same thing

[obtuse lance]

not sure what you mean by transformation

like how do you prove power series are unique or something?

[weary tiger]

I want to show that the gen func for t_n is (h(x))^2

[obtuse lance]

do you know about the convolution

the coefficients on h(x)^2 are the coefficients on h(x) convolved with themselves

[weary tiger]

Hum yep the convolution theorem is familiar to me

[obtuse lance]

if $a_n$ are the coefficients on h(x) then they obey $$t_n = \sum_{k=0}^n a_k a_{n-k}$$

[vital dew]

Merosity

[obtuse lance]

that's just what the convolution looks like on the generating function side

[weary tiger]

I see, I am yet to figure out the graph relationship

Thanks 🙂

[obtuse lance]

yeah, you're welcome, if it helps a bit you can think of how k and n-k add to make n, so you're combining every possible way to make n from two parts

[weary tiger]

A 15 regular graph has size 45 how many vertices does it have?

Is the answer 6 vertices ? 45 x2 /15

6 vertices doesn’t make sense, I forget how to calculate this

what do you mean by size again?

Edges

Oh

Use the handshake lemma

Sum of all degrees = 2 * number of edges

Times 2?

yup

So 45(2)= 90 is the sum of all degrees

Yes

But then how do I find out the number of vertices?

15*n = 90

n = 90/15

6?

How could 6 vertices have 15 degrees each?

You said its 15-regular

Doesn’t that mean each vertices have 15 degrees?

Yup

the sum of all degrees is thus 15 times the number of vertices

So a 6 vertice graph could have 15 degrees each vertices? I didn’t no edges could repeat?

@weary tiger is it possible to draw a regular disconnected graph that have two non isomorphic components ?

[last timber]

<@&268886789983436800>

no we can't

[limber token]

🥾

[last timber]

hi metal

i hope you are not horny today

[ebon aspen]

anyone know how to go about proving this?

[restive arch]

Suppose n is not odd, so n is even. Product of two even numbers is even ,therefore n^2 is even.
Now, n(n^2) is a product of two even numbers, therefore n^3 is even. This is a contradiction . Therefore if n^3 is odd then n is odd , for all integers n.

[runic crown]

,iam adv

[vital dew]

Gave you the Advanced selfrole.

[limpid fossil]

How can I find all the integers $n, m \in \mathbb{Z}$ such that $\frac{1}{n} + \frac{1}{m} = \frac{1}{5}$ without guess and check? Is there a rigorous way to solve this?

[vital dew]

add

[stray reef]

(m+n)/(mn) = 1/5 so mn = 5(m+n)

you can write this as mn - 5m - 5n = 0 and 'complete the rectangle' to get (m-5)(n-5) = 25

[weary tiger]

Can you define graphs that have infinite number of edges/vertices (not necessarily countable)? I was thinking maybe you can think of curves or sets in general in R^n as some kind of graph if you have an ordering between the vertices(points). Does that make sense?

[ebon aspen]

halp pls

[primal frigate]

In case you didn't know, the definition of modulo is: $a\equiv b \mod n$ means that $n \mid a-b$ . That should help

[vital dew]

Estridgenet

[haughty garden]

A direct proof isn’t too hard in any case. Suppose that $a \equiv c \pmod n$ and $b \equiv d \pmod n$. Then there exist integers $k, \ell$ such that [ a = kn + c, \quad b = \ell n + d. ] Then $a - b = (kn + c) - (\ell n + d) = (k - \ell)n + (c - d) \equiv (c - d) \pmod n$.

[vital dew]

opengangs

[valid wave]

how would I find incongruent solutions?

I found the amount of solutions and subtracted by 120?

is this correct?

so 108

[haughty garden]

You can reduce this to an equivalent linear congruence equation by dividing every term by gcd(32, 120) = 8

This tells you that there are 8 solutions to the equation

Then apply the Extended Euclidean Algorithm to find your first positive solution

[pallid belfry]

What are some fairly simple theorems that deal with Finite state machines?
Besides proving the equivalence between Deterministic and non-deterministic FSMs.

[obtuse lance]

pumping lemma

[ebon aspen]

would I use pigeonhole principle here?

[ebon aspen]

May I also have someone tell me if this proof is correct?

[last timber]

is that test

[haughty garden]

yes

[proper mulch]

hi

i started CS70 recently

and the lecturer says that first its better to take a basic course like MATH55 which seems pretty hard . so why would he said that .
if thsts the case then should i first take MATH55 and then go for CS70

[stray reef]

your negation's wrong

[ebon aspen]

what would it be?

[stray reef]

there exist sets $A$ and $B$ such that $A \subset B$ but $B^c \nsubseteq A^c$

[vital dew]

Ann

[stray reef]

tho you dont really need to do a proof by contradiction here in the first place imo

[ebon aspen]

yea idk why its asking me to

[stray reef]

oh wait, you're explicitly instructed to

[radiant oasis]

Hi, what does \lambda(G) stand for here?

[haughty garden]

Connectivity number - defined as the minimum number of edges whose deletion from a graph results in the graph being disconnected

https://mathworld.wolfram.com/EdgeConnectivity.html

[radiant oasis]

Yeah I saw that yesterday, just thought there might be something else.. The lemma is not intuitive to me.
Thanks @haughty garden

[weary tiger]

anyone have an algorithm for linear search??

[limpid fossil]

wait i have a quick question

how do you complete the square for nm - 5n - 5m = 0 when there are two variables

[coral raven]

it's more of a rectangle

so consider a rectangle with sides (m - 5)(n - 5)

the area will be mn - 5m - 5n + 25

you see on the LHS of your original equation you're just missing the 25

so you can just complete the rectangle by adding 25 to both sides

so if mn - 5m - 5n = 0
then mn - 5m - 5n + 25 = 25
and (m - 5)(n - 5) = 25

@limpid fossil

[limpid fossil]

yeah but how did you know you wanted to consider rectangle with sides (m-5)(n-5)?

i see that it factors out nicely

[coral raven]

experience

how would you know you wanted to consider a square with sides (x + a/2)

if you were completing the square for x^2 + ax

it's just a standard trick sorta thing

[limpid fossil]

oh i se

[quaint star]

If you have mn - am - bn = 0 then you will do (m-b)(n-a) = ab

[limpid fossil]

today i learned

it feels like im memorizing it though, i dont have the intution to understand why that is

[coral raven]

you can visualise it as an L-shape

like

an m x n rectangle

and on the top, on the m, you have an m x a rectangle

with the two m sides next to each other

and on the right you have a b x n rectangle

so it's like
m x a
m x n b x n

and then you can complete the rectangle with a b x a rectangle in the top right

[coral raven]

yes

[limpid fossil]

wow thanks

[strange raptor]

Hello, I just need an example of formal deductions. This is the practice problem I was given but I think with an example I can figure this problem out

[civic shale]

is anyone here familiar w inditinguishable objects and indistinguishable boxes?

[karmic nymph]

Just combine all those facts

[civic shale]

when you say unique strings does that mean abc not equal to cba? or the other way around?

[strange raptor]

I just wasn’t sure what format I was supposed to do it in but I figured it out. Thanks

[burnt frost]

can someone help me with this? i just started learning equivalence relations and i know that u have to prove how its reflexive, symmetric, and transitive but idk how to prove those things

[errant bear]

i mean, you just check if the statements hold

[burnt frost]

how do i show that its transitive

and how do i do the last part

[stray reef]

i mean doesn't the transitive property of tilde follow directly from that of equality?

if you give the "smallest prime factor of n" a notation like spf(n)

n ~ m iff spf(n) = spf(m)

so spf(m)=spf(n) and spf(n)=spf(k) directly imply spf(m)=spf(k)

[burnt frost]

oooh i see

thank you

i still dont know how to do the last part of the problem though

[stray reef]

what's spf(15)?

[burnt frost]

uuhhhh 3

[stray reef]

yeah

can you name some more numbers whose smallest prime factor is 3?

[burnt frost]

9 and 21

[stray reef]

good

you'll need another one though, since the problem asks for at least three such numbers

[burnt frost]

is that all i had to do?

and how would i do 7 then

[stray reef]

same thing

say what the smallest prime factor of 7 is, then name several more numbers whose smallest prime factor is the same

[burnt frost]

wait would the smallest prime factor be 7 or 1

1 right

[errant bear]

is 1 prime

[burnt frost]

oh whoops im dum

ok thanks so much

[weary tiger]

i posted this in #help-8 , but i thought posting here may be more fruitful

any help with #5 would be appreciated

s and t are supposed to be subsets of B for this problem..?

[unreal stump]

I think so

Because otherwise it makes no sense

[weary tiger]

yeah

i just don't know how to go about proving this

he awarded my friend 6/7 points for a proof that made absolutely 0 sense lol

rly inconsistent with grading, but i'd like to know how to solve it for the final

[weary tiger]

\begin{align*} y\in f(S\cup T) &\iff \text{ there exists } x\in S\cup T \text{ such that }y = f(x)\
&\iff \text{ there exists } x\in S \text{ such that }y = f(x) \text{ or} \text{ there exists } x\in T \text{ such that }y = f(x)\
&\iff y\in f(S)\cup F(T)\end{align*}

[vital dew]

Botnuke

[weary tiger]

would i need to establish that for #5?

oh, no, that's for 4

ah, yeah

i completed #4 lol

I think 5 is easier actually

using what i did for #4, i came up with this

though ik it’s wrong

obviously not in the form of a proper proof

\begin{align*} x\in f^{-1}(S\cup T) &\iff f(x) \in S\cup T\
&\iff f(x) \in S \text{ or } f(x)\in T\
&\iff x\in f^{-1}(S) \cup f^{-1}(T)\end{align*}

[vital dew]

Botnuke

[weary tiger]

ah

how would you phrase that?

that's my entire proof

you could write it how it's normally taught to be written, let x ∈ ..., then stuff, therefore x ∈ ...

then, there exists an f(x) such that f(x) is an element of S or T
since f(x) is an element of s or t, then x is an element of {f'(x)|f(x) element of S} or {f'(x)|f(x) element of T}
therefore, x is an element of f"(S)Uf'(T)

no?

and then do the same thing again with the lines reverse for the other direction of the set equality

but it's really the exact same thing I wrote

then, i could just say that they're elements of each other?

i'm sorry. it's a bit late -- i didn't see your above message

to the deleted message: mine is in english too, but the english is packed into the ⇔ symbols that should be read as "is equivalent to" or "which is equivalent to"

and "is an element of" is ∈

etc

[weary tiger]

the language here is kinda off

"there exists f(x) such that..." would be a weird thing to say

yeah, i agree

if you fix x, f(x) is a fixed object

i'm just following his notes

then~~, there exists an f(x) such that~~ f(x) is an element of S or T

for 4 this really only demonstrates one 'direction' of the set equality (you showed X ⊆ Y, but not Y ⊆ X)

change words like "then" and "therefore" to "equivalently" or "which is equivalent to" or something

how would you demonstrate equality for both directions in these problems?

or that both sides are subsets of each other (i.e. proper subset)

change the wording a little bit, or write up another excerpt where you let y ∈ f(S) ∪ f(T) first and then do the same thing in reverse

[unreal stump]

Let x in preimage of S U T,then f(x) is in S or f(x) is in T. If f(x) is in S then x is in preimage of S. If it's not x is in preimage of T,therefore x is in preimage of S or x is in preimage of T

[weary tiger]

[unreal stump]

It's just writing down the definitions

[weary tiger]

confused as to how to prove equivalency here

the wording is arbitrary, so far as this professor is concerned at least

the equivalency follows from the definitions of the terms

[weary tiger]

first equivalence: preimage definition (or at least one possible definition)
second equivalence: definition of union
third equivalence: same as first

this is my friend's submission (6/7)

do you mean to define them in this way?

are you asking if I am suggesting writing those definitions? no

[unreal stump]

That's correct

except for the S and T being subsets of A part

[weary tiger]

yeah

does anyone have a recommendation for this proof?

unsure as to where exactly i went wrong

[last timber]

what is f

[weary tiger]

fibonacci sequence

[last timber]

well first of all you have indexing broken

what is k on RHS

why you have basis as n = 2

[weary tiger]

ah

i meant 2t-1

etc

got ahead of myself there

but otherwise, how would i prove that these sides are equivalent?

[last timber]

well anyway

f_1 = f_2 is indeed true for usual fibonacci

so base case is provided

[vital dew]

Commander Vimes

[weary tiger]

wdym?

we were told to select a value n for the summation, assume true for k terms such that k>=n, and prove true for k+1 terms

[last timber]

what

are you claimed to do inductive proof?

[weary tiger]

?

yes?

[last timber]

then you assume that statement is true for n = 1

and that if statement is true for n-1 then it is true for n

[weary tiger]

can you do the summation from 1 to 1?

lol

seems unnecessary

[last timber]

summation of x_i from 1 to 1 is x_1

it is trivial but it is in your statement still

[vital dew]

Commander Vimes

[last timber]

consider how you can split sum in terms of n-1 and n

(just apply definition of sigma)

[weary tiger]

wait, what?

the base case is n=1*

[last timber]

no

the base case is n=1

[weary tiger]

we're trying to prove k+1

assume true for k terms

[last timber]

oh you want strong induction?

[weary tiger]

yeah

[last timber]

where you assume that it is true for all naturals less than n

[last timber]

anyway this does not change the stuff man

[weary tiger]

f1 = 1 = f2 = 1; f1=f2

yeah

[last timber]

the statement is true for 1,2,..., n-1 contains the statement is true for n-1

so we can use that

[vital dew]

Commander Vimes

[last timber]

do you agree that this is true @weary tiger

[weary tiger]

it's 12:40 am

uh

[last timber]

i just removed last term of summation from sigma

and wrote it explicitly

[weary tiger]

yeah

[last timber]

so this is true

[vital dew]

Commander Vimes

[weary tiger]

this produces f2k + f(f2+1) = f(2k+2), however

using strong induction

[last timber]

what

how?

[weary tiger]

using strong induction*

[last timber]

no man

[weary tiger]

;/

[last timber]

thus

[weary tiger]

i can't use that

i have to use k and k+1

my professor would not accept that

ik they're the same

[last timber]

first of all

transition from n-1 to n is the same as transition from n to n+1

just difference in noitation

[weary tiger]

.

i'm aware

but i'm unable to use this format for my submission

[last timber]

and nothing in statement of strong induction forces us to use two terms

[weary tiger]

:/

[last timber]

moreover

i am not even sure what exactly ur prof wants

since working backwards

[weary tiger]

k and k+1

instead of n-1 and n

that's it

basis case, assume true for k, and prove for k+1

:/

[last timber]

is that so hard to just redefine notation then man

[weary tiger]

it's 12:44 am

i mean, if it's not hard, then

[last timber]

i am doing this with n-1 and n transition, noithing stops you use my approach fro n to n+1 transition

anyway

using these two

you just plug second into first and get f(2n-2)+f(2n-1)=f(2n), qed

[weary tiger]

what

[last timber]

replace sum in first equation by its value which is known by hypothesis

[weary tiger]

homie, we're proving for n here

why are you working backward

lol

[last timber]

i am not working backward

i am continuing transition from n-1 to n

that is i am completing inductive steps

you should be able to modify this for n->n+1 transition since this is just difference in notation

[weary tiger]

ik how summations work, though

i just needed to rearrange these things to prove k+1 terms

:/

is f2k + f(f2k+1) the same as f(2k+2)?

[last timber]

explian from where you got f(2k)

and f(2(k+1)-1)

[weary tiger]

look at the summation for k terms

[last timber]

wait lol

nvm

your proof is correct

[last timber]

yes it is

[weary tiger]

okay

[last timber]

because by definition of fibonacci f(k)=f(k-1)+f(k-2)

[weary tiger]

so does adding terms of the fib. seq work in a way similar to exponents?

[last timber]

what do you mean

[weary tiger]

seems that way if you treat the subscripts as exponents

kinda

[last timber]

i do not get your point

[weary tiger]

like, you add f2k to f2k+1

to get f2k+2

[last timber]

i treat subscripts as indexes

[weary tiger]

it's like doing 2*2^2

[last timber]

no

[weary tiger]

you get 2^3

[last timber]

i mean in some sense there is connection since integer power is recursive

and we can define
p(0)=1
p(n+1)=2p(n) and get exactly 2^n function

but that is just similarity due to recursive nature

[weary tiger]

i think this should be sufficient

thank you!

[soft escarp]

c:

[tranquil vault]

Is this true?

[stray reef]

[quaint star]

I mean, I understand what you mean

But

[stray reef]

the wording

[tranquil vault]

lmao

This is my first time writing something

proofy

[stray reef]

what exactly are you proving?

you should state at the beginning what you are setting out to prove.

[tranquil vault]

I'm proving that you can only have a equivalence relation on the cartesion product of two sets if they are the same set?

[stray reef]

that's. part of the definition of an equivalence relation

there's nothing to prove here

[tranquil vault]

I couldn't find anything that said it online so I wanted to clarify it

[stray reef]

i mean, from what i gather you're saying that symmetry is impossible to make sense of

this does not at all require the symbol soup you have served to the reader

[tranquil vault]

I wasn't sure how to word it so I just used symbols

but ideally a concise statement would be better

[stray reef]

to be clear this is not a proof

[tranquil vault]

ye

its more of a statement

[stray reef]

but rather an informal explanation for why we can't talk about symmetry for relations from X to Y where X and Y are different sets

[tranquil vault]

yes

[stray reef]

for such a relation R to be symmetric, we need xRy to imply yRx- but yRx may very well be nonsensical, as nobody said y had to be a member of X

[tranquil vault]

I don't quite follow could you elaborate?

[stray reef]

R is a relation from X to Y, so in order for x R y to be a statement that we can say is true or false, we need the stuff on the left (x) to be an element of X and the stuff on the right (y) to be an element of Y

but when you switch it up and write y R x, suddenly you are requiring y (which is now on the left) to be in X

and who says y has to be in X?

[tranquil vault]

I thought the statement itself implied that?

I'm sorry my knowledge is quite half baked

I learnt most of it from Wikipedia yesterday

[stray reef]

i mean let's say R is the relation "x owns y" where x is a human and y is a pet

if you try to reverse it to talk about symmetry suddenly you have dogs owning humans

[tranquil vault]

I understand

my understanding of it is tat we have two sets the set of humans and the set of pets

the binary relation is a subset of the cartesion product humans x pets

which would imple that only the forward relation is correct

since the set of pets and humans are different

lets say we have a relation that maps the positive real numbers to the negative real numbers by the equation -sqrt(x)

[stray reef]

........

i dont think i can continue this

[tranquil vault]

before you go could you point me to a good resource where I can learn stuff

I really am trying here

It is not my intent to frustrate you. I'm sorry

[tranquil vault]

oh wait there are question channels. My bad I should of gone there I apologize for my negligence

[idle cave]

how is the statement, if you finish your meal, then you can have desert equivalent to you can have desert iff you finish your meal

isnt it just p => q

im confused how u understand that its biconditional

with a simple if, then

[stray reef]

it isn't

[idle cave]

oh nvm

i think the author was trying to make a point about the imprecision of the english language

[weary tiger]

Yo, was doing some problem and I came up with some recurrence I have no clue how to solve: $$ A_n = 6 \sum_{i=0}^{n-2} A_i 2^{n-2-i}$$ with $A_0=1, A_1=0$. Any ideas?

[vital dew]

Ledog

[unreal stump]

Induction?

[weary tiger]

Lol I want the general formula for n-th term.

[unreal stump]

Ok,you could do a couple of manipulations

[weary tiger]

Would have to guess it, no clue what it is.

[unreal stump]

Take B_i=A_i 2^{-i}

[stray reef]

sounds like some kinda generating function fuckery might be of use?

[weary tiger]

I thought about if for a second, but seems not that fun to do.

[unreal stump]

You could turn that whole thing into B_n=3/2(B_{1}+B_{2}+...B_{n-2} )

That seems doable

[weary tiger]

Does it?

[unreal stump]

Define C(n)= \sum_{i=0}^{n}B{i}

You end up with a homogenous reccurence in C(n) I think

[weary tiger]

Hmm I guess on LHS you have C_n+1 - C_n = C_n or sth?

[unreal stump]

Yes

There will be some 2's and 3's in the coefficients

But it will be of that form

[weary tiger]

Aight thanks I'll try that.

hmmm actually there's a problem with this

For different n's, A_i will be multiplied by different power of 2.

[unreal stump]

We accounted for that

Remember B_i=A_i 2^-i

[weary tiger]

Okay yeah, calculation error.

[stray reef]

i just tried it

its possible to get a generating function for this thing

$\sum_{n=0}^{\infty} A_n x^n = \frac{1-2x}{1-2x-6x^2}$

[vital dew]

Ann

[stray reef]

if yall give me some time i can say how i got this

@weary tiger @unreal stump

[unreal stump]

That was a nice way of doing it

[weary tiger]

Okay after fucking up 123618 times I finally got it

Btw this was a recurrence for the problem: how many 'roads' are there using n steps in which you start and end in the middle

[wanton marlin]

can anyone here help me with 1 question?

[quaint star]

@wanton marlin

Don't you think it's unreasonable to ask us to commit to helping you before showing us the question?

Show the question and someone will help if they can

[quaint star]

Okay

Apply Binomial Theorem twice

So write [(x + sqrt y) + z]^8 and apply Binomial Theorem on (...) and z

Then check which term will give you a z^2

Then only focus on that term

And apply binomial theorem again on the (x+sqrt y)^whatever power part

[wanton marlin]

alright got it thank you

[quaint star]

Np

[lilac breach]

I posted a problem a few weeks ago with 3-regular graphs and now I'm trying to solve the general case for it... but I don't know how to interpret Delta(v) for all v vertices. Do they all have the same degree bound?

[stray reef]

what's Delta(v)?

the degree of v?

[lilac breach]

Yes

[stray reef]

wouldn't it just be 3

oh wait no ok hold on

you're generalizing it

[lilac breach]

Yes

Because the vertices in the subgraph will always have at most Delta(v)

[stray reef]

as far as i remember you wanted a subgraph without vertices of degrees 3 or higher

so Delta(v) would be 2

[lilac breach]

Yeah, I just don't understand exercise 2. Are we generalizing it to any graph?

Here's the old one

[stray reef]

we're generalizing it to allow different bounds for different vertices

[lilac breach]

That also implies any graph or is it at most 3 now

[stray reef]

?

[lilac breach]

The given graph, is it still regular?

I suppose not

[stray reef]

doesnt looks like it

[lilac breach]

Not sure where to begin with this

[lilac breach]

Also, regarding exercise 1. I got the same result (1/sqrt(5)) by calculating the probability like this: Pr(e included)*Pr(deg(e_u) <= 1) *Pr(deg(e_v) <=1) = Pr(e included)* (1-Pr(deg(e_u) =2)* (1-Pr(deg(e_v) =2) = p*(1-p^2)*(1-p^2)
But I am not not sure if that's just by luck

[fallow pawn]

can someone help check this

[rigid night]

(iii) is wrong

[fallow pawn]

sounds good

thx

[errant bear]

is this

basic set theory moment. or is 5 also wrong

[weary tiger]

yep

[rigid night]

Oh
Wasn't sure what the complement was on the RHS, so left that.

[weary tiger]

5 is unclear, complement in relation to what?

[weary tiger]

hello im curious as to what the ^6 does outside the curly braces

[dawn robin]

I want to make sure im following the right route.

I have a problem that says to Prove by mathematical induction that C(2n+1, 3) is a solution to the recurrence relation Sn = S(n-1) + (2n-1)^2. For >= 2 with the initial condition s1 = 4

To do so i set x = n+1 and am now trying to show that
(2x+1)!/3!(2x+1-3)! = Sx-1+4x^2

do I have that right? Because im not sure what to do with all the factorials

[stray reef]

{0,1}^6 is the set of all bitstrings of length 6

[weary tiger]

oh ok so any combination of 0 and 1 with length 6

thanks

[weary tiger]

hello everyone, i have a problem with Proof strategies, like how to write a proof and such, it's very confusing and didn't understand the doctor's material

[stray reef]

is there a particular result you're trying to write a proof for rn?

[idle cave]

yo

can someone explain to me what propositional satisfiability is

[stray reef]

you have a logical circuit with a bunch of switches that act as inputs, and a bunch of lights that act as outputs.
satisfiability asks, "is there a configuration of on/off states for the switches that make all the lights turn on at once?"

[idle cave]

so configuration of inputs that basically provides a complete solution to smth?

[stray reef]

mmmm

maybe?

[idle cave]

OHHHHHHHHH

now i see why hes talking abt sudoku

[stray reef]

each light corresponds to a proposition

[idle cave]

alrighty

thanks ann

[bitter palm]

anyone interested in inductively defined sets?

I need a lil help

[stray reef]

post your problem

what have you tried?

also uh wait

is this a test

i see the

4 points
in the top right corner

[mint dawn]

It depends on your provided set of axioms lol

[untold raptor]

to be honest not really sure the first one i think is 0 and the second one i think is a probiltiy formula but idk which rn

[bitter palm]

Im supposed to define this set inductively. The base set is {1, 2} but I'm not sure on the inductive step. Any hints are appreciated. Thanks

[stray reef]

is that all you're given

[bitter palm]

yup

[stray reef]

so no information about any other elements in the set

[untold raptor]

yeah

[stray reef]

...

okay there's two of you here

one of y'all gotta move

[bitter palm]

sorry ill shut up

[stray reef]

@untold raptor what makes you think the first answer is 0?

[untold raptor]

cause their are only no way of filling the commitee when there are only republicann and democrates

[stray reef]

???

[bitter palm]

bruh

[stray reef]

there are 5 dems, 3 reps and 4 independents, and we want to make a committee of 3

our restriction is that the committee can't include both a dem and a rep

so like

you could pick three of the independents

and that'd be a valid committee

or did this somehow not occur to you? @untold raptor

also i am begging one of you two to change your pfp from discord default yellow

[bitter palm]

I would first try to find out how many possible combinations there are to picking a committe, then count how many of those fit the criterion

Alright, on it boss

[stray reef]

i mean you could count the number of D+I committees, and the number of R+I committees, and the number of indep-only committees

and then use the inclusion-exclusion principle on those

[untold raptor]

ah i see

thansk

[bitter palm]

weeb picture applied.

[stray reef]

anyway kalgerion who's to say your set isn't actually {1, 2, 5, 7, 10, 12, 25, 27} \cup {n in N : n ≥ 42069}?

[weary tiger]

Maybe ... is an element of the set

[stray reef]

[bitter palm]

lmao

because there is a constraint of maximum 2 elements in the base set

which are 1 and 2

and the elements after that are added inductively

[stray reef]

i mean

i can turn this into an inductive defn

call your set S

then it's defined by n ∈ S => f(n) ∈ S, where f(n) is defined as follows:

$f(n) = \begin{cases}2 & n=1 \ 5 & n=2 \ 7 & n=5 \ 10 & n=7 \ 12 & n=10 \ 25 & n=12 \ 27 & n=25 \ 42069 & n=27 \ n+1 & \text{otherwise}\end{cases}$

[vital dew]

Ann

[bitter palm]

[weary tiger]

its even better cuz here base set only 1 element

[bitter palm]

ill find the pattern dont worry

[weary tiger]

theres infinitely many possible patterns

[bitter palm]

should be in this form

[weary tiger]

what Ann did was of that form

[bitter palm]

yea but i dont think ill need a function for it

[weary tiger]

you do

+4 is a function

[bitter palm]

oh? anyways appreciate you taking your time

thanks

[weary tiger]

you should tell your teacher that the set is not well defined

[bitter palm]

others have solved it, albeit with 2 steps in the induction step

[weary tiger]

you are only given the first few elements of the set. there is no information about the others

so they could be anything

[stray reef]

^

[bitter palm]

True, I dont see any other solution than a function that maps the inputs like Ann did

[weary tiger]

all solutions are with functions

[bitter palm]

true true

[weary tiger]

theres infinitely many possible solutions

[bitter palm]

ill see what i can do

thanks again @stray reef @weary tiger

[rigid night]

AFAIK, the symbol on the right is always used for the set with no elements.

[slow jewel]

Is this inclusion-exclusion if so, why?

[stray reef]

well it is possible to use the inclusion-exclusion principle here

with four sets

hands not containing any spades, hands not containing any hearts, hands not containing any diamonds and hands not containing any clubs

[slow jewel]

its what the solutions used

[autumn quest]

In yoga class, all of the students are lined up according to height. Andy notices that the number of students who are taller than he is one-fourth the number of students who are shorter than he. Violetta notices that there are 3 times as many students who are taller than she than students who are shorter than she. How many students are in the class if there are fewer than 40 students?

plz help

[regal shoal]

Hmm I'd recommend drawing out the position of students that satisfy Andy's requirements first.
The first example would be
x x x x A x Then ask which of the X's can be Violetta that meet her requirements.

More algebraic approach:
If we know the proportion of student to the left and right of Andy we know there only a few number of total students that work for him. In that first example there were 4+ andy + 1 = 6, 8+ Andy + 2 = 11, 5*(students shorter than Andy) + 1 = total number of students. Similarly for Violetta, 4*(students taller than V) + 1 = total number of students. Then you can set the total number of students equal to each other and find pairs of (shorter than Andy, taller than Vanessa) that satisfy the equation.

[weary tiger]

would anyone know how to prove this?

my professor isn’t requiring that we use the summation above for the proof

[high ermine]

for proving that this is a perfect number try to list divisors of this number and then sum them using above formula

[weary tiger]

yeah, ik

how do i write it

😐

like, ik the divisors are itself, 1, 2^(s-1), and either 2 or 2^s-1

but how do i prove that

i can’t just add them and say that it’s a perfect number

[stray reef]

like, ik the divisors are itself, 1, 2^(s-1), and either 2 or 2^s-1
no

you are missing out on a lot

like... 2^k is a divisor of your number for any k between 1 and s-1

let $p := 2^s - 1$ for clarity, then the proper divisors of $2^{s-1}p$ are as follows:

$1, 2, 4, \dots, 2^{s-1}, p, 2p, 4p, \dots, 2^{s-2}p$

[vital dew]

Ann

[weary tiger]

?

misunderstood — i apologize

thought these were for nth terms

i’m still unsure as to how to set the proof up, though

[high ermine]

$(1+2+4+ \dots +2^{s-1})+(2^{s}-1)(1+2+4+ \dots +2^{s-1})$

[vital dew]

LearTsura

[high ermine]

and use formula given in exercise on these sums in parenthesis

$(2^{s}-1)+(2^{s}-1)(2^{s}-1)$

[vital dew]

LearTsura

[stray reef]

second sum only goes to 2^(s-2)

[high ermine]

oh okay, my idea was to sum all divisors and then obtain 2*number

[weary tiger]

my friend sent me a solution that does that

i just don’t really understand what’s happening lol

[weary tiger]

like, idk. i understand how you got the divisors, but how do you account for its being prime?

which part are we summing?

how do you set it up?

like, its divisors are 1/10 the proof

[high ermine]

sorry, what being prime?

[weary tiger]

"if 2^s - 1 is a prime number"

2^(s-1)*p isn't listed as a divisor either apparently?

i know that -- as far as perfect numbers are concerned -- it's excluded

but n | n