discrete-math

[iron marsh]

We have a lead 🙂

[twilit sundial]

yup

i'm looking at the multinomial sum $(1-1-1)^n$ rn

[vital dew]

elrichardo1337

[twilit sundial]

we can express multinomial coeffs in terms of binomial coeffs so i think we might be able to get somewhere with those?

[iron marsh]

How exciting

[twilit sundial]

so $\binom{n}{i,j,k}$ i believe is equal to $\binom{n}{i}\binom{n-i}{j}\binom{n-i-j}{k}$

[vital dew]

elrichardo1337

[twilit sundial]

but since $i+j+k=n$ we can simplify that by a lot

[vital dew]

elrichardo1337

[twilit sundial]

we would get $\binom{i+j+k}{i}\binom{j+k}{j}$

[vital dew]

elrichardo1337

[iron marsh]

Alright, this is hurting my brain cells. I think I'm tapping out.

[twilit sundial]

lmao aight

thanks for the help

[iron marsh]

no problem, it's an interesting problem to think about. To prove...that's another story

[twilit sundial]

yea

[iron marsh]

Maybe there's some piece that magically fits everything together. But I have no idea 😛

Btw, I get the sneaky suspicion this concept generalizes

[weary tiger]

anyone wanna check if my hw is correct? only 1 question

[twilit sundial]

so it turns out this funny little thing has exactly what im looking for 😭

ohhhhhhhhhhhhhh shit of course

that's how we make the signs selectively change, use roots of unity !

[weary tiger]

Damn this document looks hot

Can you send this @twilit sundial

[twilit sundial]

https://artofproblemsolving.com/community/c5h1061437p4596291 see this page, the download link is in the first message

this is many years old and potentially a little bit dated for contest prep? but still a very good resource

[weary tiger]

I'm not preparing anw xD I've crossed the age limit now

[twilit sundial]

lmao same here

[weary tiger]

I'm just interested in olympiad math

[twilit sundial]

i only barely made AIME my senior year of HS

yeah same, it's a very fascinating world to dive into

[weary tiger]

That's applaudablee

AIME is hard

[twilit sundial]

thank you lol

(then i proceeded to get 2 on AIME bc i was so burned out 😭)

but at least i qualified? 😃

[weary tiger]

That's finee, I tried AIME problems before my regional selection test this year and I didn't even make it past like P5 on the old ones like AIME 2013

[twilit sundial]

we all gotta start somewhere lol, no shame in that

[weary tiger]

Well its over for me now :/

You're in uni now?

[twilit sundial]

i just do contest problems on the side for fun

yeah, second year

[weary tiger]

Damn nice

What you studying

[twilit sundial]

double major applied math and piano lmao

[weary tiger]

I'm planning on doing the same in college

[twilit sundial]

nice

[weary tiger]

Holy smokes I'd love that life

[twilit sundial]

(i'm in a uni in the US)

[weary tiger]

Obviously, lol

[twilit sundial]

lmao

[twilit sundial]

it is utter pain, the majors don't overlap at all so i'm overloading on classes

but i can do it in 4 years so why not

[weary tiger]

Can't you like drop one of them

[twilit sundial]

i could but i'd really rather not

[weary tiger]

Hmm

[twilit sundial]

at worst i would downgrade piano to minor

[weary tiger]

Yeah what's the harm with that anyways

Alright goodluck man

[twilit sundial]

ig?

thanks lol

the only reason i got into this uni was bc of my piano audition, would NOT have gotten in otherwise

[weary tiger]

I retract my statement

[twilit sundial]

lmao 😭

ik im kinda sunk costing and whatnot

but like

i'd like to see it through to at least the end of my undergrad

i'd never stop playing even if i wasn't taking classes for it but

[weary tiger]

It's a different kind of pressure when there's like a systematic approach to it I guess

[twilit sundial]

yea the conservatory grind is hell

(plus conservatories around the world do a TERRIBLE job with actual career prep)

(even the top ones)

especially if you're in a classical major

pop/jazz/etc people have it easier just bc the market is better for them

[weary tiger]

IDEK because I've never met any classical musician irl

[twilit sundial]

💀

[weary tiger]

Where I'm from any non engineering/ non medicine career is a joke

[twilit sundial]

rip

[weary tiger]

Yeah, you guessed it

India

[twilit sundial]

LMAO

damn

[weary tiger]

Yeah I get that classical is just kinda ded

But I still love classical more than other genres

[twilit sundial]

classical piano majors upon graduating (they are now unemployable with no marketable skills):

[weary tiger]

Perform at someone's wedding : P

[twilit sundial]

that's for like only a few hundred USD a pop, not really sustainable in the long run

although i have done that before

[weary tiger]

Hmm that's true

So for masters you gonna switch?

[twilit sundial]

will probably try for some more specialized science

[weary tiger]

Hmm

[twilit sundial]

but it's gonna be hard to even get into those without specific coursework in them

like electrical engineering is smth i'm interested in but my schedule simply has no space for it 😭

i'd need physics, chem, EE, etc. classes that i have no way of getting bc i don't meet prereqs or it just conflicts with literally every other class i have

[weary tiger]

I wish I could give you some advice or something but man, I'm in my senior year of hs

[twilit sundial]

oh damn good luck with uni applications

[weary tiger]

IITJEE exists:

[novel raptor]

Guys how to prove 8b

[coral parcel]

If it's just a matter of convincing yourself/someone it's true, I'd draw some Venn diagrams.

[novel raptor]

require formula

I realized what it looks like

[rigid oriole]

heck is oplus

[timber minnow]

This may be dumb but if B is the x axis and C is the y axis and A is the line y=x, the LHS reduces to A while the RHS reduces to just 0. (We are talking about vector spaces here right?)

Unless Oplus is xor here

[timber minnow]

I think it's the symmetric difference

[rigid oriole]

holy sht thats cursed

i kept thinking could it be disjoint union or something

[coral parcel]

A set algebra becomes a ring if you take symmetric difference as your addition operation and intersection as your multiplication, so a plus-like notation for the former is not completely unreasonable.

[iron marsh]

@twilit sundial any luck?

[weary tiger]

It's the distributive properties law

[cloud stream]

My prof did not cover how to actually show that these are true. Like he gave us no examples of the process and im not exactly sure what to do

[iron marsh]

Tldr; assume you have an element in the first set, and somehow arrive to it being in the other

For equality, you have to go both directions: first assume an element is in the first set , and show it is in the second set.
Then assume you have an element in the second set and show it is in the first set.

Here's a simple example: Suppose $B \subseteq A$, then show that $A\cap B=B$. \par
Well, suppose $x\in A\cap B$, which means $x\in A$, and $x\in B$. Since $x\in B$, and the choice of $x$ is arbitrary, we have $A\cap B \subseteq B$. \par
Next, suppose $x\in B$, since it is given that $B\subseteq A$, $x$ is also in $A$. Thus, $x\in A\cap B$, and so $B\subseteq A\cap B$. \par
Since each set is contained in the other, it follows that $A\cap B=B$.

[vital dew]

dackid

[iron marsh]

Hope this is helpful to you @cloud stream

[winged temple]

Am I correctly interpreting the statement "Either it does not walk like a duck or it does not talk like a duck, or it is a duck." as: (~P nor ~q) nor r ?

also

anyone know where in the latex manual it shows the commands for boolean logic symbols?

I can't find it anywhere

[little prism]

you can also just detexify them if you wanna know their commands

[twilit sundial]

yea I got it, using this thingy called “roots of unity filter”

[coral parcel]

I would notate that as $\neg\text{walks} \lor \neg\text{talks} \lor \text{is}$.

[vital dew]

Troposphere

[coral parcel]

You almost certainly don't want to be speaking about NOR.

[winged temple]

oh my god my head is exploding

if ~p then ~q is NOT the contrapositive of if p then q

why is everyone saying that?

the truth columns are different

in the 1st statement if p is false and q is true, the statement is false

and if p is true and q is false, it's true

the 2nd statement has the reverse outcomes

so what gives?????????

[faint sphinx]

The constrapositive of P ==> Q is (not Q) ==> (not P)

You can check that these have the same truth values

(not P) ==> (not Q) would be the inverse (equivalent by contrapositive to the converse, Q ==> P)

[winged temple]

oops...........

[ashen junco]

Hello! I need to prove the following logical equivalence without a truth table. I'm really confused how to get from an "if then" to an "and."

[stone basalt]

#proofs-and-logic

[hidden sparrow]

a quicker way than the standard approach would be to use indicator functions mod 2

[weary tiger]

$(\sum_{i=0}^{n} a_i)^2$

[vital dew]

Succubus

[weary tiger]

Can anyone show me a very easy derivation of this sum

The end result has a sum with an idex i \neq j and a sum where a_i is squared

[torn dome]

Could someone please help me prove that part b is a tautology?

[grave basin]

Think of inclusion exclusion

[coral parcel]

The quesion is okay for this channel too.

[coral parcel]

When you're instructed to use a truth table, you're not supposed to "get from this to that". You simply fill out truth tables for each side and then note that the result colums have the same content.

[weary tiger]

Anyone got Discrete and Combinatorial Mathematics", by Ralph P. Grimaldi

[azure adder]

how do we write "or" in english

sorry really vague question

e.g. exclusive or is "either we play basketball or play soccer"
what's the equivalence in that with or in english

[weary tiger]

A ball is dropped from a height of 160 feet and rebounds to ½ of the height it previously fell. What is the total vertical distance it will travel?
geometric sequence question

[iron marsh]

We don't really have an inclusive or. However, you could say something like "In my hands, I could have an apple, a banana, or both." So in logic, that's like saying I have A XOR B XOR (A and B), which is technically equivalent to inclusive OR.

[unborn vapor]

The word “or” is ambiguous in that it can be inclusive or exclusive depending on the sentence. Even if you include the word “either”, there are actually still sentences in which that would be interpreted as an inclusive or. So it’s not possible to give a particular word or phrase that always means inclusive or, nor one that always means exclusive or. The only way to be perfectly explicit is to do what dackid suggested and include something like “or both” or “but not both”.

However, in a class that requires you to write precise logical statements in plain language like this, the prof might adopt some conventions for simplicity. You seem to have indicated that your prof accepts “either” as indicating an exclusive or. When I took a course like this my prof also did that, and he said that if we didn’t say “either”, it would be interpreted as inclusive, so you could ask your prof if they will also do that. But remember that all that is just a convention used in this one class and is not representative of the actual English language

[surreal iron]

Hello guys, I'm looking for a book recommendation on graph theory for a CS student. I am planning to do my bachelor's thesis in that subject so I'm trying to better my knowledge in the field. I was looking at Combinatorics and Graph Theory by Hariis, Hirst and Mossinghoff but not sure if it is adequate for my level.

[fathom olive]

can this be read as, "The set of elements x in the universal set U such that the element x is not in set A"

[haughty garden]

Yea that’s reasonable

[viral cove]

Is $O(\frac{n^2}{log(n)})$ faster than $O(n^2 \times log(n))$?

[vital dew]

Insanity Cry

[snow junco]

yes

ofc is it?

even at just N=2, for all n≥N the first O=f(n) ≥ g(n) = second O

if you add coefficients then the numbers change a bit

but it still scales log(n)^2 times faster at its base

[snow junco]

that's one way to word it yes

[knotty rune]

I am confused on how to finish the truth table for this

is the logic format correct at least?

this is the updated version

[oak plaza]

I don't understtand the usefulness of the hint.

Suppose that k = gcd(a/d, b/d). Then it means that k divides both a/d and b/d. So a/d = kl and b/d = kj for integers l and j. So a = kld and b = kjd.

Not sure where to go from here.

[weary tiger]

k=1 as per the statements

[oak plaza]

How do you know that k = 1?

[weary tiger]

Because if gcd(a,b)=d then a=dm and b=dn for coprime m and n. So a/d = m and b/d = n are coprime and hence k = gcd(a/d,b/d) must be 1

[oak plaza]

Okay that makes sense.

You're assuming that a and b are not equal.

[weary tiger]

I'm not sure if my argument is very rigorous but you could think of it as something like this:

Pr[gcd(a,b)=d] is equivalent to saying Pr[gcd(a/d,b/d)] = 1. Suppose the set of all favourable outcomes of the event of gcd(a/k,b/k)=1 is S and the set of all favourable outcomes the event of gcd(a,b) = 1 is S'. Note that for every tuple (a,b) with a fixed a in S, there are k corresponding tuples (a,b), (a,2b),...(a,kb) in S' and similarly for every tuple (a,b) with a fixed b in S, there are k corresponding tuples in S'; implying as per the Fundamental Theorem of Counting that the cardinality of S' is k*k = k^2 times the cardinality of S. Hence, the probability of S' is also k^2 times that of S (since we are working under the same sample space in both cases) and hence,
P = Pr[gcd(a,b)=1] = k^2 Pr[gcd(a/k,b/k)=1] = k^2 Pr[gcd(a,b)=k]. The claimed result follows immediately.

[oak plaza]

It's probably gonna take me a sec to digest this but thanks. I've gotten this problem out of a book on cryptogrpahy and network security. None of the things that you're mentioning here were mentioned in that book. I might need to prep before reading that book.

[weary tiger]

Yes, you need some knowledge of combinatorics and elementary number theory for this

All the best

[distant grove]

Can someone help me with this

[distant grove]

Initially I thought we would need to use the Bertrand’s ballot theorem to get the probability of A being ahead at all times. And once we have the fraction (the probability (4/14)), we multiply by the number of permutations, which is 14!. But my teacher said:

If you have 14 votes and of them you should choose 5 of one kind, in how many ways can you do that? The first one you have 14 places, the second 13 and so on to the fifth when you have 10 place left. Using the multiplication principle that means \frac{14!}{9!} but then the order of the individual votes does not matter so you get…

[distant grove]

Someone said we use “multinomial coefficient”, but why?

[distant grove]

The way the question is written, it's not clear whether one should ignore the voters' identities when counting the vote sequences, but I believe that's what the teacher expects. I suspect they don't expect me to use Bertrand's ballot theorem (since we haven't covered it in the lectures). Perhaps they simply want me to write a program to enumerate the solutions and count them that way. Treating the voters as indistinguishable means counting AAAAAAAAABBBBB only once instead of 9!5! times for all the different ways A-voters and B-voters can be rearranged.

[foggy gale]

what symbol is this?i dont rememeber/know what it means

[faint sphinx]

$\bigwedge$ (which means meet in a lattice, i.e. infimum) and $\bigvee$ (which means join in a lattice, i.e. supremum)

[vital dew]

Ryx (Home for flowers)

[faint sphinx]

They are also used for a few other purposes, but it looks(?) like this might be is

[haughty garden]

Could also be a compact way to write a conjunction of disjunctions; Q_1 is true if and only if, for each i, you can always find some index j such that p(i, j) is true

[faint sphinx]

this is the special case L = {0 < 1} but yeah that could also be it, hard to tell without context

[haughty garden]

That’s at least the context I’m used to when doing research haha

[foggy gale]

the bigger context would be the queens problem i guess, i can put the whole thing in

[faint sphinx]

looks like this was correct lol

[foggy gale]

Ty for the help

[jolly ledge]

lmao, rosen

[muted gate]

hello folks

I'm having trouble proving this result:

Let $f: A \to B$ be a function, and let $X \subseteq A$. Then $X = f^{-1}(f(X))$ if and only if $f$ is injective.

[vital dew]

texaspb

[muted gate]

any advice?

I can show my work if needed (not that much of a work though)

[grand totem]

Where exactly are you stuck? One inclusion of the equality $X=f^{-1}(f(X))$ holds regardless of whether $f$ is injective or not. So it might be a good idea to start with that

[vital dew]

Neverbloom

[faint sphinx]

One thing to note is that this is not technically correct as written

It should be that $f$ is injective if and only if $f^{-1}(f(X)) = X$ for all $X \subseteq A$

[vital dew]

Ryx (Home for flowers)

[muted gate]

so like

what I noticed is the fact that

supposing X = f^-1(f(X)), then for x,y in X we have f(x), f(y) in f(X)

this is correct right?

I was trying to reason with this fact, and that it would imply f being injective (b/c two elements in the domain are mapped to two different elements in the image)

[grand totem]

If you're trying to prove injectivity it's a better idea to start by assuming that f(a) = f(a') and then trying to come up with a useful X, for which X = f^{-1}(f(X)) lets you conclude that a and a' must be equal

[muted gate]

right

will try that!

[muted gate]

well

turns out that doing this first assumption "f(a)=f(b)" for a, b in A made things so much easier

I actually didn't know if it was okay or nice to do such assumption

[muted gate]

hey

do you guys have any tips on proving this one now

For all $Y \subseteq B$, $f(f^{-1}(Y)) = Y$ if and only if $f$ is surjective.

[vital dew]

texaspb

[muted gate]

haven't done any work yet (don't know how to go about it)

[grand totem]

It is quite hard to assist with these types of questions without any further information on what you're having problems with or where exactly you're stuck.
Most of the proofs are rather short and mostly boil down to chasing definitions, so it's hard to give any hints without completely spoiling the solution in the process.

[muted gate]

sorry, i'll try to be more thorough

my issue was "how does f(f^(-1)(Y)) = Y leads to f being surjective (i.e there exists an a in A such that f(a) = b for some b in B), turns out the solution (at least the one the professor gave) was not like anything I'd expect

I'll send it here

I just couldn't think of anything that would help me achieve the result tbh

sadly

i'm trying the other direction by myself (<=) now

[grand totem]

I'd say the most natural order to prove this in is to first prove that $f(f^{-1}(Y))\subseteq Y$ holds. This does not require $f$ to be surjective. Then prove the other inclusion (i.e. $Y\subseteq f(f^{-1}(Y))$) under the assumption that $f$ \emph{is} surjective. This establishes that $f$ surjective implies $f(f^{-1}(Y))= Y$ for every $Y\subseteq B$.

[vital dew]

Neverbloom

[grand totem]

As for the other direction (i.e. $f(f^{-1}(Y))= Y$ for every $Y\subseteq B$ implies $f$ surjective), you pick any $b\in B$ and are supposed to come up with an $a\in A$ that maps to $b$ under $f$. Since you've assumed that $f(f^{-1}(Y))= Y$ for \emph{every} $Y\subseteq B$ you must again come up with a nice choice of $Y$. Certainly that $Y$ should somehow depend on your $b$ and a very natural choice is to simply consider the singleton ${b}$ (which is a subset of $B$ as $b\in B$).

You then have that $f(f^{-1}({b})) = {b}$. Technically, the only inclusion you \emph{really} care about is the one that says ${b}\subseteq f(f^{-1}({b}))$ (after all, the other one holds always and so will probably not prove to be useful in proving that $f$ is surjective).

But $b\in{b}$ together with ${b}\subseteq f(f^{-1}({b}))$ tell you that $b\in f(f^{-1}({b}))$. So there is some $a\in A$ such that $f(a)=b$ and $a\in f^{-1}({b})$ (if you unpack the definition of preimage here it will just say $f(a)=b$ again). And so you've found an $a\in A$ mapping to $b$ under $f$.

[vital dew]

Neverbloom

[muted gate]

heey!!

thank you so much

I was stuck with this part of "coming up with a nice Y"

same problem as before hehe

your explanation cleared up a lot

[timber minnow]

From this, I wonder what the process is to actually compute higher and higer Bernoulli polynomials

I guess from 2 you may be able to deduce that the nth bernoulli polynomial has degree n, then you could substitute the form of a degree n polynomial into 3 and try to solve, but that seems it would be too complicated as you aren't using previous computations to help find the current polynomial

too many coefficients to solve for...

[abstract mica]

hello, idk if I'm allowed to do this but if anyone could take a look at my question in #help-12, I have my answer for the problem so far and an explanation of what I'm confused about, thank you!

[rare river]

Hey guys I have a question

(a) Here is a theorem about integers: “Let n be an integer. If n is the square of the
integer m, then n’s rightmost digit is 0, 1, 4, 5, 6, or 9 .”

i. Does the theorem imply that no integer with rightmost digit equal to 2 can
be the square of another integer? Explain.

I am having a hard time interpreting this problem and coming to a conclusion

I'd like some fresh perspectives on this so I can make a more robust conclusion

[brave rock]

Yes; contrapositive.

[inland hearth]

anyone knows what to include in an algorithm that computes all cases of 4-colouring a planar graph without same adjacent colours?

[abstract tulip]

how can I prove that this is true?
where U_n is number of unbaleled tree with n vertices

$U_n < \binom{2n-2}{n-1}$

[vital dew]

Choram

[unreal plover]

Can i have intuition for if b | ac then b | (a,b)*c

I think thats what the identity was

Whenever gcd comes up i kind of lose a bit of intuition for whats going on

I always try to think of divisors as “counting up” which helps me

[gusty swallow]

so (a,b) gives you some factors of b that is in a. So to get the rest of the factors ofb, you need the factors that are in c.
so multiplying (a,b) * c gives you every factor of b, and probably some extras

[unreal plover]

Count up to the rest of b?

[plain bear]

does anyone know how I can start the simplify of the expression?

[quiet eagle]

Hi, I need to find a good formula for this sum. Is trying to bring all the sums into a denominator profitable? When I tried to do it, it was a bit too complicated. However, if it works, I'll go with it. \ \${\frac{1}{2!}}+{\frac{2}{3!}}+{\frac{3}{4!}}+\cdot\cdot\cdot+{\frac{n}{(n+1)!}}.$

[vital dew]

Sciencenjoyer

[plain bear]

Can someone help?

[weary tiger]

Well, those many complements, unions, and intersections make me think of De-Morgan's laws, and really it's quite natural here as we have a complement of the union of two complements, which allows us to negate them entirely (and replace the union with an intersection).

From there it's mostly just playing around with the expression and order of operations (using the commutativity and associativity of unions and intersections), and see where you get.

[unborn vapor]

What lithium said, also, I think part of the reason you’re not getting answers is that your question is vague and not super helpful - like at least tell us where you’re getting stuck and what you’ve tried

[elder berry]

think of telescoping series, in particular do something to the numerator of each fraction ||k = (k+1)-1||

[jolly ledge]

https://proofwiki.org/wiki/Composite_of_Symmetric_Relations_is_Symmetric

I feel like the proof here is wrong? Specifically this part:
"As R and S are symmetric relations:
∃y∈A (x,y) ∈ S^(-1) and (y,z) ∈ R^(−1).
Hence, by definition of composition of relations: (x,y) ∈ S^(−1) ∘ R^(−1)"

Ignoring the fact that it should have been (x,z) instead, shouldn't it be R^(-1) ∘ S^(-1)? And is the proof fixable?

[quiet eagle]

ohhh got it thanks

[meager prawn]

You have
xSy and yRz
Hence z R^-1 y and y S^-1 x
???
Hence x R^-1 y and y S^-1 z
Hence x(S^-1 R^-1)z
Hence (x, z) in (R S)^-1

It's not possible
Let R = {(1,2), (2,1)} and S = {(2,3),(3,2)}
R and S are symmetric
(S R) = {(1,3)}
It's impossible for (3,1) to be in (S R) since 3 is not an input for R

As shown by https://math.stackexchange.com/questions/4303917/proving-that-composition-of-symmetric-relations-is-symmetric

So wikiproof bad

But I suppose you figured that out since then

[jolly ledge]

wikiproof failed me 😭

[jolly ledge]

you overestimate my abilities of constructing counterexamples

thanksies bezier

[meager prawn]

yw

meanwhile I get to learn about relation composition

[weary tiger]

Can someone help me with 2b

[jolly ledge]

tfw CS student doesn't know discrete math:

[jolly ledge]

how would you express the statement "every odd number"?

[meager prawn]

have yet to take CS classes, so CS student is bold

also kmm

I actually intend to double major

so I'm still a math major

still gonna have over 12h of math classes a week

[jolly ledge]

owh

[jolly ledge]

💀

gg.com

[blissful dock]

can someone help with

[coral parcel]

An obvious invariant would be "s is the i'th triangular number, a.k.a s = i(i+1)/2".

[blissful dock]

yes

but i < n

[coral parcel]

Yeah, you'll need that in the invariant too.

i <= n, actually.

[blissful dock]

because of the last iteration before it exits?

[coral parcel]

Yeah, the last time you evaluate the condition you'll have i=n.

[blissful dock]

okay so what if i <= n

because in the book i read that is also i(i+1)/2

[coral parcel]

You need to know i=n after the loop such that you can then reason from s=i(i+1)/2 to s=n(n+1)/2.

[abstract whale]

Hey guys! How did k(2k + 1) turn into n(n+1)/2?

[coral parcel]

Insert n=2k into n(n+1)/2 and simplify.

[blissful dock]

dont understand what you mean

[abstract whale]

Bruh, how could I have missed that lol. Thank you, fam.

[blissful dock]

okay if it is i(i+1)/2 as you say then I guess I jsut substitute that into s = s+s-n

but im confused as to how i<n and i<=n both give i(i+1)/2

[coral parcel]

Suppose you have s = i(i+1)/2 we execute the loop body once. If we call the new values j and t instead of i and s so we can speak about both new and old values, we then know
s = i(i+1)/2
j = i+1
t = s+j
From these three pieces of knowledge you need to prove t = j(j+1)/2. That will take a small bit of algebraic footwork, but it shouldn't depend on whether i<n and/or i <= n, since neither the assumptions nor the conclusions even mention n!

[blissful dock]

mention whaT?

n factorial?

[coral parcel]

No, they not mention the value n

[blissful dock]

oh xd

because it doesnt depend on n it doesnt matter is what you say

[coral parcel]

Yes.

[blissful dock]

frick you are right

[coral parcel]

Yes - though that matter of phrasing will raise some eyebrows. It's better to say "assume P(k) is true and prove P(k+2)".
(Because if you have a number n that is the same number as k, then that is certainly not also the same number as k+2).

[blissful dock]

so i guess i just ahve to show that (i+1)(i+1+1)/2 is true then from there substitute into s+s-n and i should be n^2?

[coral parcel]

It sounds like you're mixing up the analysis of the loop body, with the analysis of the rest of the function.

[blissful dock]

really?

isnt that what you said

i just wrote i+1 instead of j

[coral parcel]

(And it doesn't make sense to say " (i+1)(i+1+1)/2 is true" -- (i+1)(i+1+1)/2 is just a number, not a claim that can be true or false).

[blissful dock]

okay sorry

i need to prove

[coral parcel]

At the end of the loop body you have, indeed (with my variable names) t = (i+1)(i+1+1)/2, which we can rewrite to t = j(j+1)/2 since j=i+1.

[blissful dock]

that my induction hypothesis?

[coral parcel]

In my experience, when you're talking about "loop invariants" you're not also saying "induction hypothesis" -- but it's possible your book arranges things otherwise, so take what I'm saying with a grain of salt.

[blissful dock]

I just need to show that it is invariant for i+1 right

[coral parcel]

You need to show that the invariant still holds. Since iNew = iOld+1 that will look somewhat like "invariant for i+1", but what we really mean is that whatever values the variables have after an execution of the loop body, those values correspond to each other in the ways the invariant claims.

We had the invariant s=i(i+1)/2 -- in other words sOld = iOld (iOld+1)/2.

We have now concluded sNew + iNew (iNew+1)/2, which is good, so that part of the invariant holds, good!

[blissful dock]

yea so is it wrong to say the invariant is true

[coral parcel]

No that is good.

I objected to your wording "for i+1".

(We also need to prove that the invariant i <= n keeps holding, but that is similar).

After we've done all that, we're through proving the loop, and we can then stop thinking about i+1 at all!

[blissful dock]

what do you mean keeps holding

[coral parcel]

What we know after the loop is:
a) from the invariant: s = i(i+1)/2
b) from the invariant: i <= n
c) because the loop ended: not(i < n)

[coral parcel]

Just that evaluating the condition i <= n still produces true at the end of the loop body.

[blissful dock]

i dont get it

[coral parcel]

Which of the many things I've written don't you get?

[blissful dock]

didnt we prove already that the invariant holds true already i dont get what you mean by "(We also need to prove that the invariant i <= n keeps holding, but that is similar)."

[coral parcel]

I've proposed the invariant s = i(i+1)/2 AND i <= n. We've gone through proving that the first part of that is preserved, and I was merely pointing out that strictly speaking we also need to prove that the second part is preserved.

[blissful dock]

how do you prove that

[coral parcel]

Well, you know that
a) from the invariant: iOld <= n
b) because the loop condition was true: iOld < n
c) from the assignment in the loop body: iNew = iOld + 1
Do these three facts give you enough information to conclude iNew <= n?

[regal gate]

given an integer partition (d_1,d_2,..,d_n) of 2e you can ask whether there exists a simple graph in n vertices and e edges with this degree sequence.

If such a graph exists we say that the integer partition is a graphical partition.

Question: what are criteria to determine whether an integer partition is a graphical partition? What are fast algorithms that do the job, and how fast are they?

mmh

a greedy algorithm might work?

mmh I think it does lol

[blissful dock]

does this make sense

[coral parcel]

If you haven't yet understood my objection to writing "the invariant holds for i=k+1", then I think I'm out of ways to explain it, other than just shouting louder and shriller. Does anyone else have an idea?

[blissful dock]

you probably explained it fine i have just been awake for a while I just want to solve this exercise before going to bed

i can barely think i wont waste anymore of your time

[coral parcel]

The second sentence here looks good, though.

[worthy siren]

yeah the last one is True

[timber minnow]

I can understand i and ii as saying how to get Bn recurively and saying that the Bn are either odd or even about x = 1/2, but I can't think of a nice way to intuitively think about iii.

some kind of condition about averaging uniformly spaced points on a bernoulli polynomial I guess?

[unreal plover]

Its also true that if b | ac you can say b | (b,a)*(b,c)?

[gusty swallow]

Yes

[unreal plover]

Got it. I understand this now. Thanks!

Thinking about it also caused me to fully understand euclids lemma too

p is prime iff for all ab if p | ab -> p | a or p | b

[timber minnow]

actually do bernoulli polynomials go here?

[unreal plover]

Do u know how much this stuff is used in abstract algebra?

This stuff is all from my abstract algebra class

[gusty swallow]

It’s pretty relevant to modular stuff which are usually among the first groups you deal with

And relevant to homomorphisms/isomorphisms

[unreal plover]

Yeah we did modular stuff last class and i need time with that to intuitively get it

Prof went so fast

Ok cool

[drifting brook]

can someone explain how i got part b correct? kinda just followed my heart with this one

[light raven]

It seems you got it correct by selecting the correct option out of 5. This tends to randomly happen 20% of the time if you guess. If you apply heuristics like eliminating certain options which are clearly not correct, like the one with a V in it, you can increase your odds to 25%. You might also eliminate the first two if you intuit that rVq should be transformed into something that appears "balanced", whereas r^~q and ~r^q appear "unbalanced". Now it's 50/50 between the last two.

The last two are direct negations of one another so it ought to be simple to deduce which one is correct by seeing when the original implication is tautology, e.g. by assuming q is a tautology. If you assume this, you can see the fourth option is a tautology directly while the fifth option is a contradiction.

[thick needle]

p->q <=> ~(p^~q), the rest is there

[unreal plover]

For #14, im not really sure what [a,b]Z is supposed to represent

The only thing i found it book was that [a,b] is supposed to be the lcm of a,b

[timber minnow]

It's the multiples of [a,b]

So the set of [a,b]k with k an integer

Or just the set [a,b]Z for shorthand

[faint sphinx]

If you know what aZ and bZ are, it's the same thing but with the lcm(a,b) = [a,b] instead

[torpid mango]

Anyone who can help me abit with my discrete math homework ?

been stuck on a task for 4 hours xD

[brave rock]

Just ask the question

[torpid mango]

(A^c∪B)∩(B∪C)∩(C∪A)=(A^c∪B)∩(C∪A).

i need to prove that whats left is equal to right

and i can only use some simple laws for sets

we are not at the logic part of discrete math yet

so we are using the algebra rules for sets

i feel like i can only use the distributive law once and then i get stuck

[unreal plover]

I have a question asking for divisor diagram for 60 and something else

These numbers have 3 prime factors. Not sure how to draw this on a page without it looking like a mess

[coral parcel]

Your options are basically these, I think.

[abstract whale]

Hey guys! I am completely lost on how the solution turned out the way it did for this question. Also, is there any good resources on how to use/manipulate sequences/series in order to understand solutions like this, or to just know how to use them in general?

[neat oxide]

Part A
f(x) = Fools in my class
w(x) = Wise person
s(x) = Says bun diddy bum bum
b(x) = best students are all in my class
f(x) ⇒ ¬w(x)
w(x) ⇒ s(x)
¬s(x) ⇒ b(x)
¬f(x) ⇒ b(x)
tell me if this is good
and please give justifications

is this also good

[azure adder]

is this possible?

[thick needle]

de Morgan to ~p^(q^~r), if q is f so is ~p^(q^~r); if q is t or will be always t

[sour talon]

Let P(x,y) be the statement y < x^4. Determine the truth values of the following
quantifications, where the domain for each of the two variables consists of all real
numbers.

Hi, I was wondering if anyone could reword or answer this differently in english words, I understand it when I think of the answer in math but when I read the solution in english I don't get what it's saying.

this is the answer

i get how it's false, as there is no real number x such that all real numbers why would satisfy that inequality

but "as there is no vertical line wholly within that region of interest" doesn't make sense to me

[azure adder]

sorry should've elaborated more, possible to simplify so from that to q == q

[thick needle]

if q is f, ~p^(f^~r) = ~p^f = f, f or f = f; if q is t, ~p^(t^~r) or t = t

so ~p(q^~r) or q = q

[azure adder]

breaking it down strictly with laws of equivalence

so with distribution, demorgan, absorption etc, it's a lot of work to prove it honestly

thanks though

this is my attempt on it, I don't see the mistake

or more to do idk

noooooo...

[thick needle]

oh, ~(p or ~ (q ^ ~r)) or q = ~(p or (~q or r)) or q = ((~p ^ q)^ (q^~r)) or q = (~p or q) ^ q ^ (q or ~r) = q ^ (q or ~r) = q

demorgan inside, demorgan, distrib, absorb, absorb

and a^b^c = a^b^b^c = (a^b)^(b^c)

or smth, it's 4am here

[thick needle]

oh, u can just absorb 3 times and ur done

[azure adder]

how'd you get this?

~(p or (~q or r)) or q = ((~p ^ q)^ (q^~r))

oh associative?

[thick needle]

yeah

[azure adder]

yup

how would you catch something like this though..

[azure adder]

holy crap......

stuck a lil bit on this

(~p or q) ^ q ^ (q or ~r)

[thick needle]

meant on your last step all that was left is to absorb 3 times

[azure adder]

q ^ (~p or q) == q?

[thick needle]

(a or b) ^ b = b absorbtion

[azure adder]

oh it wouldn't matter if a is ~a or a it would still be b?

[cosmic moss]

anyone has some ideas?

[thick needle]

yup

[azure adder]

kk thank you ❤️ kiss

[cosmic moss]

😭

[azure adder]

sorry boss I im on a time limit

[static briar]

How tf do I do this by induction

[cosmic moss]

no problem

[cosmic moss]

why is my answer wrong?

🙃

[plucky wedge]

this question makes no sense to me, does it have an answer?

[cosmic moss]

😭

[thick needle]

https://en.m.wikipedia.org/wiki/Quantifier_(logic)

[haughty garden]

Induct on $n$. For $n \geq 2$, notice that the sum is equal to the sum over all nonempty subsets of $[n]$ plus any subset that includes the $(n + 1)$ term. For such a subset, you can include $n + 1$ first and then you're considering all (possibly empty) subsets of $[n]$. Therefore, we have [\sum_{\substack{S \subseteq [n + 1], \ S \neq \varnothing}} \frac{1}{S!} = \sum_{\substack{S \subseteq [n], \ S \neq \varnothing}} \frac{1}{S!} + \frac{1}{n + 1} + \frac{1}{n + 1}\sum_{\substack{S \subseteq [n], \ S \neq \varnothing}} \frac{1}{S!}]

[haughty garden]

Then use your inductive hypothesis and simplify

[static briar]

Ai

Wait

How Can a subset of n have the term n plus 1 in it

[static briar]

According to this

[haughty garden]

no, you consider subsets of [n + 1] in your inductive step

so you split it into subsets of [n] and subsets that include (n + 1)

they partition the subsets of [n + 1]

[static briar]

Ah ok lemme see here

[cosmic moss]

could someone help with my question please?

[static briar]

Shouldn’t there only be one 1/n+1 instead of two in your picture

[haughty garden]

the first 1/(n + 1) is for the empty subset of [n]

i.e. S = {n + 1}

[faint sphinx]

if p is a prime factor of n, then since nb=a (since n = a/b) p is also a prime factor of a. So 6 does follow from 3 and 5

[cosmic moss]

The equation in Statement 2 is not justified by the definition of rational number.

is this the only one?

[faint sphinx]

That one does not follow, yeah. What about statement 7? How would you know that p is also a prime factor of b?

[cosmic moss]

it only show p is a prime factor of a right?

[faint sphinx]

right

[deft vigil]

Having a hard time wrapping a hard time around hamming graphs more intuitively. I see the definition, but would like to understand more intuitively...

I understand for the word graph we want to have an edge from each letter to every other letter, so that's why we have K26, but why do we need to Cartesian product each K26 graph ell times to get to a word graph

For clarifying notation, the square means "Cartesian product these 2 graphs together"

[cosmic moss]

thanks a lot!

[dire mural]

Need hints on part 2),3),4),5). Thanks.

[neat oxide]

please check my answers out and tell me what justifications should i give

[neon jewel]

Can anyone please explain this in detail, thanks

[neon jewel]

Never mind, got it

[glossy coyote]

someone please

help me solve this proof

all i see is letters

[p Λ (p → q)] → q

[unreal plover]

Can someone give intuition for:

If ac = ad mod n and (a,n)=1, then c = d mod n.

[haughty garden]

If (a, n) = 1, then you can “cancel” out the a’s because a has an inverse modulo n

[unreal plover]

What does it mean for a to have an inverse modulo n

[static briar]

How tf to do part 2

[coral parcel]

That looks hard.

For large n, I believe the reachable squares will form a large half-solid octagon with "fuzzy" edges, but the fuzz consists of the same patterns at each n, such that f(n) ends up following a quadratic function. But at smaller n where the general pattern has not yet developed fully, the numbers will be quite ad hoc.

[coral raven]

maybe there's a colouring type argument

like for example the squares are by default black and white

and then the knight always switches from black to white to black to white

so that could help narrow it down

[coral parcel]

Hmm, I was wrong -- the stable pattern arises much earlier (and is much less fuzzy) than I thought. Here are the reachable shapes for n=0, 1, 2, 3, 4.

So it looks like for n>=2 we can count f(n) as a square (turn the pattern 45°) minus four times some triangular number.

[coral raven]

right, that makes sense

[static briar]

Ye idk what my prof is on

I was able to do king

But knight I geniusbely don’t know how it’s possible

[coral raven]

there might be a distance metric in which this is more natural

[static briar]

Are the centres reachable here or is it just the black squares

Wait I think they always should be reachable

[coral raven]

the centres are reachable after an even number of steps, but not after an odd number

[coral parcel]

Yeah, I used a red square for "reachable center" and a yellow one for "not reachable center".

[static briar]

Ahh

Bro the effort you put in making the image is godlike

[coral parcel]

It went pretty quickly with Gimp. At each level copy-paste the previous level with 8 different offsets, and at the very end, color in the center pixels and blow the entire thing up by a factor of 10.

[quiet eagle]

Given: $T_{n}=\sum_{k=2}^{n-1}T_{k}\cdot T_{n-k+1}$
and $C_{n},=,T_{n+2}$ \
How do I show that: $C_{n+1}=\sum_{k=0}^{n}C_{k}C_{n-k}$.
My textbook says, it's easy to show. Im worrying if: $C_{n},=,T_{n+2} \Longleftrightarrow C_{n-2},=,T_{n} $ ?

[vital dew]

Sciencenjoyer

[cerulean raft]

hi

i just started taking a class

called discrete structures

and uh

its csci 2011 at the UMN

and its so confusing

ive been liek a straight a student forever

but i think this is gonna change it

it's so different from anything I've taken

it's like math on steroids but using yoru brain

im so confused

i was wondering if you guys know HOW youa re supposed to study for such a class

Here's the things we're workingn on

[lapis mantle]

it's confusing, indeed. I'm taking that class this semester as well.

That's so comprehensive

maybe have a look on the set theory and logic first will help.

[azure adder]

are they any online resources for a problem sets of a particular topic in Discrete math

[unreal plover]

its just like rules u would learn in an algebra class

[torn nymph]

is there any youtube series / video that could help with understanding relations?

I'm having a lot of problems with understanding how to prove things and i could really use some resources, even books

[quiet eagle]

solved

[hushed comet]

uni level or need problem sets for olympiads level ?

since preparation for both things is entirely different

[analog hound]

What is meant by saying that two cards drawn from a standard 52-card deck have "equal face value"? Does the ace of diamonds have equal face value to the ace of hearts? Does the 2 of clubs have equal face value to the 4 of clubs?

(A question is asking me to count sets of five cards with a condition imposed using that language)

Ah nevermind I found a search term that doesn't return explanations about unrelated subjects

[static briar]

I still haven’t been able to find a formula lmao

It’s 1, 8, 33, 76 so far respectively for 0,1,2,3

[azure adder]

uni levels, sorry for the late reply

maybe both

[static briar]

Need help for part 2. Btw just do people don’t get confused the question implies that whoever finishes the chocolate on their turn loses

[faint sphinx]

Please don't double post.

[static briar]

Mb should I delete this post?

[livid minnow]

Hello I’m having a hard time trying to come up with an efficient way to solve this problem: Find the number of binary strings that do not have any repeating substrings of length 3

I think he may just want us to write a program to solve this

Because I can’t figure out how to do it mathematically without tediously exhausting through a shitload of cases

[lapis mantle]

Nim game, which is a impartial game. Do you know Sprague–Grundy Theorem? It will help.

[static briar]

nope

[lapis mantle]

please make it clear. Did I misinterpreted?

[static briar]

No I meant to say I am not familiar with the theorem

I will look into it

[sour arrow]

@static briar
Sprague-Grundy applies, but it won't help you actually find the winning strategy

If you want a hint, consider the amount of chocolates left (mod 4) after any given turn

[lapis mantle]

The task is to figure out the strategy to win. It contains the fist take strategy and the fellow. The build of the strategy is recursive and it starts with the situation that the amount of items are below 4. But we should to find out which situation is preferred first.

I mean through the SG we can find out how to transfer the situation to the one we expected.

[plucky wedge]

Given statement (P → Q):
If ( x + y \geq 2 ), then ( x \geq 1 ) or ( y \geq 1 ).

Contrapositive (¬Q → ¬P):
If ( x < 1 ) and ( y < 1 ), then ( x + y < 2 ).

To prove the given statement, we will prove its contrapositive.

Proof:

Assume ( x < 1 ) and ( y < 1 ).

Then, ( x ) can be written as ( x = 1 - a ) where ( a > 0 ), and ( y ) can be written as ( y = 1 - b ) where ( b > 0 ).

Adding the two equations, we get:
[ x + y = (1 - a) + (1 - b) ]
[ x + y = 2 - (a + b) ]

Since ( a > 0 ) and ( b > 0 ), their sum ( a + b ) is also greater than 0.

Therefore, ( 2 - (a + b) ) is less than 2.

So, ( x + y < 2 ).

This proves the contrapositive. Hence, the original statement "If ( x + y \geq 2 ), then ( x \geq 1 ) or ( y \geq 1 )" is also true.

Why are we allowed to restrict what a and b can be?

[vital dew]

Branshi

[plucky wedge]

^ Why are we allowed to restrict what a and b can be?

having those values as a negative would make the proof false but why can we not make them negative?

[iron marsh]

Do you agree that any number can be expressed as 1 minus some positive number?

[plucky wedge]

are you saying if I agree if all real numbers can be expressed as 1 - some positive integer? If thats the case then would it be no since we wouldn't be able to express positive integers?

[iron marsh]

You're right, that's why they established the condition x<1 and y<1

And in that case, we can

Which is a good point. Because if x>=1, you could not express x as 1-a for some positive number a

[ripe beacon]

Is it 'proven' by induction that
4(5^(k)+2^(k))
is divisible by 7?

[meager prawn]

It's 4 times a multiple of 7, so it's a multiple of 7

[ripe beacon]

Well, how do you figure if k = 3?
You'd have 4(5^3 + 2^3) how do you know it's a multiple of 7?

[ripe beacon]

(And how would you know that 4(5^2 + 2^2) (for k = 2) isn't a multiple of 7?)

[brave rock]

Neither the statement nor the proof say anything about when k is even.

[hardy sun]

I posted this on help forum but got no reply. Can someone help see which step I made a mistake? The goal is to write the form s.t. quantifiers and bound variables go first, i.e. PNF.

[brave rock]

The only one-sided implication in your working is the wrong way around

You erroneously assumed that if a implies b, then not a implies not b, when in fact this is wrong.

[hardy sun]

I got it. Thank you👍

[jolly flame]

Hi guys . I might need your help in the future

[brave rock]

sorry I'm busy that day

[worthy siren]

we assume that this is true for k = 1. then we prove that k = 3 is also true
because 4(5^1 + 2^1) is divisible by 7 and 21(5^1) is divisible by 7.

[worthy siren]

the question is not asking for even powers of 5 and 2. its only asking about odds

there may be some odd powers that also be divisible by 7. unless it has been proven that it cant

[broken veldt]

https://www.youtube.com/shorts/7zVvIb0mtiQ

IS THIS SOLVABLE??

I NEED AN ANSWER

[sick lantern]

Is there any algorithm to eulerize a digraph (adding edges, minimizing the cost) I searched around couldn't find any, I saw several for undirected ones.

[plain pulsar]

Suppose that all the following are true.
a ∧ b
a → ¬ c
b → ¬ d
¬ (c ∨ d) → e
Prove e ∨ f.

how to prove this when i dont know what is f

also i dont understand this question

[drifting brook]

can i set up a truth table for this? or do i just gotta think it out

[grand totem]

f may not be mentioned in the assumptions but that doesn't matter. If you know that e is true, then so is e ∨ f. So your goal should be to prove e.
The last assumption tells you that it would be sufficient to prove ¬(c ∨ d) instead. Can you finish from here?

(We haven't used any of the first three assumptions yet. Can you see what to do with those and how you may derive ¬(c ∨ d) from them, essentially finishing the proof?)

[ember basin]

Write the regular expression from:
The set of strings over the alphabet {0,1} that donot contain 00 as a Substring
(1+10)^+(01+1)^
Is this answer correct?

But if we have 0 the statement is false

[ashen token]

I don't think 010 matches your expression

[ember basin]

Yes

But can i test with 0?

[ashen token]

0 also doesn't seem to match your expression yeah

[ember basin]

Oh ok ty bro for your help

[digital carbon]

I have done a presentation on a graph theory conjecture called Erdős-Gyarfas conjecture
Last week I have e-mailed them that the presentation is not on the website(https://pgadey.ca/seminar/)
I did not get a reply.
Am I allowed to post the PowerPoint file here?

[sage pelican]

Struggling with 2a) not sure how to start it / visualize it

[last flicker]

Look through table 6 and/or the provided p->q == ~p v q and see if any of those rules can be applied to one side to start transforming it to the other

Just try one of those rules that could apply and see if you can actually get any closer to getting to the other side using that and other rules.

[weary tiger]

Modus ponen is when conclusio is true and tollen is when conc is false right

[west wren]

Can anyone check my rough sketch of a proof below?

Below are some relevant definitions (from the second edition of "A Book of Abstract Algebra" by Charles Pinter):

Thank you in advance!

[cerulean raft]

hi, i have a question about biconditionals

so say that if the biconditional is, "if you don't miss the final examination, then you pass the course, and if you pass the course, then you miss the final examination," does this mean that the ONLY way you pass the course is if you don't miss the examination (i.e. even if you fail the final, you still pass the course, because you took the final exam)?

i guess my question is if the biconditional implies that the implication is the ONLY way that a certain end outcome can occur

[sage pelican]

can anyone give me a hint how to solve part a), i think im =just very unfamiliar with terminology

[snow sleet]

not quite. your statement says that if you don't miss the exam, then you don't pass the course based on the contrapositive of "if you pass the course, then you miss the final examination"

[knotty rune]

Biconditional A<->B
means if A is True IFF B is also True

vice versa if B is True IFF A is also True

anytime if A is false, then the whole statement is False
and anytime if B is false, then the statement is False

1st Part:
"if you don't miss the final examination, then you pass the course.
can be rewritten as if you took the final exam, then you pass the course.
Let F = you took the final exam
Let P = you passed the course
Then you'll get: F -> P

2nd Half:
since we let F = you took the final and P = you passed the course,
Your statement: "and if you pass the course, then you miss the final examination,"
^P->~F

Together with 1st and 2nd half you get:
(F->P)^(P->~F)

It doesn't match with F<->P
Since F<->P means (F->P)^(P->F)

Let me know if I'm wrong.

[west wren]

Can anyone check my rough proof? Thank you in advance...

[west wren]

Part (a) is essentially asking whether we can, for any choice of x and y from {1,2} (with repetition allowed), choose some z from {1,2} such that P(x,y,z) is true. Now if x=1 and y=1, then we can set z=1 to make P(x,y,z) true; if x=1 and y=2, then with z=1, P(x,y,z) is true; if x=2 and y=1, then with z=1, P(x,y,z) is true; and if x=2 and y=2, then with z=2, P(x,y,z) is true; and thus, the statement of part (a) is true.

[regal gate]

A subgraph H of G is called an elementary subgraph if each component of H is either an edge or a cycle.

What does this mean? (they do not define these concepts in the book I'm using)

I think a component is a connected subgraph spanning all the vertices?

so elementary graphs are of this form?

just want to make sure I'm interpreting things correctly

[cerulean raft]

Thanks!

[cerulean raft]

Thanks!

makes snese

[unreal plover]

I am confused

Not sure how we got “[-a]^(-1) = -[a]^(-1)”

[meager prawn]

if [a] [b] = 1, then [-a] [-b] = (-[a]) (-[b]) = (-1)² [a] [b] = 1
Hence if b = a^-1, then -b = (-a)^-1

[sage pelican]

thanks for the reply! what does the change between the ∀ and ∃ mean, sometimes on x sometimes on y

like, on A), ∀x∀y∃z

what would be the change if it was ∀x∃y∃z

[meager prawn]

the first one you can kind of see as defining a function z = f(x, y)
The second defines a function (y, z) = f(x)

"for all prime p congruent to 1 mod 4, there exists a and b such that p = a² + b²"
You can say (a, b) = f(p)

"to each a, b, there exists a number c such that c = a² + b²"
defines a function f(a, b) such that c = f(a, b) = a²+b²

(though note that defining such a function f often involves a choice: because there exist several solutions, defining such a function involves an implicit choice. But this isn't #proofs-and-logic, so it isn't very important)

[sterile flame]

Hi there. In a book I've found the following example of inductive definitions (let $n'=n\cup {n}$):

$\phi (0)=z,\ \phi(n')=f(\phi(n),n)$ [this will be definition (a)]

$\phi(0,a)=g(a), \ \phi(n',a)=H(\phi\vert(n'\times A),n,a)$ [this will be defintion (d)]

Of course (d) is more general than (a), so the existence of (d) implies the existance of (a).
Let $g$ and $H$ be two functions belonging to $Z^A$ and $Z^{T\times \mathbb{N}\times A}$, respectively, and let $\phi$ be a function satisfying (d). Now let us define a sequence $\Psi: \Psi_n=\phi\vert(n'\times A)$, then:

$\Psi_0 =z^*={\langle \langle 0,a\rangle, g(a)\rangle :a\in A}$

$\Psi_{n'}=\Psi_n\cup {\langle \langle n', a\rangle, \phi(n',a)\rangle : a\in A }
=\Psi_n\cup {\langle \langle n', a\rangle, H(\Psi_n,n,a)\rangle : a\in A }=f(\Psi_n, n)$

Which means that $\Psi$ satisfies (a). Now the author writes "Now we shall prove the existence and uniqueness e of (a). This theorem shows that we are entitled to use definitions by induction of the type (a). According to the remark made above, this will imply the existence of functions satisfying formula (d)". I don't really get how proving that $\Psi$ satisfies (a) [assuming there exists a $\phi$ satisfying (a)] implies the existence of $\phi$ satisfying (d). May someone help me out please?

[vital dew]

davide

[halcyon swallow]

does anyone know how to solve 136x = 119 (mod 255) using the euclidean algorithm

[foggy gale]

can P(x,y) be switched to P(y,x) and stay the same?

[brave rock]

What is P?

[foggy gale]

like for example lets say x and y if true if x doesnt like movie y would switching it be logically equivalent

[ivory badge]

Well, if x doesn’t like movie y

That sounds dumb if I say Die Hard doesn’t like the movie Jim

[brave rock]

No

[ivory badge]

Swapping things usually isn’t the same

[strong musk]

hello, Im in need of some help with this Q

On an outdoor terrace in town A beer costs 52 SEK and a soft drink 28 SEK. One afternoon, a bunch of thirsty engineering students bought beer and soft drinks for a total of 880 SEK. How many beers can they have bought at most?

I have made an equation 52b + 28s = 880 where b = beer and s = soda, 'I get the gcd(52,28) and get 4, I divide by 4 and get the equation 13b + 7s = 220. I got the answer 35 beers at most, is that correct)

[slender verge]

how would i place brackets in this p ∨ q∨ ∼ p∧ ∼ q ∨ p ∧ q

[faint sphinx]

idk is there more context?

[slender verge]

im good im pre sure its true

think i got it

[knotty rune]

If you let “x likes y” to be L(x,y) then that means x likes y, switching the x y order would mean y likes x. So it’s not the same. I always wished my crush I like would love me back, but that rarely happens right?

[faint sphinx]

huh

that absolute depends on the context and where brackets are but sure, if you think you've got it. Idk what you mean by true here tho

[slender verge]

it simplified to 1 or true

[subtle sparrow]

(A - B) - C = A - (B - C)

So
when I do

A N (B N C')' then A N (B' U C) distribute i get (A N B') U (A N C)

however
when i do

A - (B N C') then (A - B) N (A - C') then (A N B') N (A N C) 

somehow i mustve done something wrong to get UNION in one and interesection in the other one????????
i believe the second one is correct with the intersection?! or i could also be doing something completely wrong
any help is appreciated thanks

[nova wing]

is ~p->q the contrapositive of p->~q?

[faint sphinx]

Contrapositive of A => B is ~B => ~A.

[last flicker]

no, the order of implication gets switched around as well as p and q negated

[faint sphinx]

now carefully trace what happens to the (double) negations

[regal gate]

what is an odd circuit

k is chromatic number, lambda= max eigenvalue of graph G

nvm it should be a cycle of odd length

the maximal eigenvalue is 2 I think

[foggy gale]

why does xhave to be chosen before y here?

[foggy gale]

ty for response

[little prism]

because it is named first

[foggy gale]

named first?

im a little confused

is it bc of the formula

or the position of x,y in the predicate

[little prism]

we read from left to right

first x, then y

[foggy gale]

why would this one work then? thats what confuses me

is it bc its position can be swapped?

[little prism]

because you can choose a specific y which works. instead of it having to work for all y's

[foggy gale]

So if the formula was something else then would

work ?

Like if x*y =0

Was the formula

[little prism]

yes

it depends quite heavily on what R(x,y) is

[foggy gale]

I c, Ty for the help

[sage pelican]

bit of an easy one but, just to check my thinking,

original is next to (a/b/c)

i may be wrong, because i treated each as, if p then q, and not as q provided p or such

[tidal prawn]

given that {n,n,n,n} is the same thing as just saying {n}, would {n,n,n,n} still include 4 elements or would it just be one element, repeated four times?

[cyan dew]

One element

[tidal prawn]

appreciate it, and a set in a set also counts as an element, right? so for example, {1 , {1}} = 2 elements?

[warm quest]

How should I approach this restriction?

I realize this is the same as choosing 4 dividers out of 15 + 5 - 1 and removing the outcomes that involve one of the 5 divisions having more than two

However, I am really lost on how to express this properly

[warm quest]

I should be ashamed, this is basically the complement rule

So basically, you have x1 + x2 + x3 + x4 + x5 = 15 with x1 <= 2

this is the same thing as the 1 - x1 > 2, which we can acquire from simply removing those biscuits from the pile

so we get C(15 + 5 -1, 5 - 1) - (12 + 5 - 1, 5 - 1)

[snow sleet]

I would actually just add the cases where that dog gets no biscuit, 1 biscuit, and then 2 biscuits

[snow sleet]

x1 should actually be <=2, right not just <2

@warm quest...any luck with a direct approach?

ping me if you still need help....I've counted this problem a couple ways and I'm getting consistent answers

[warm quest]

this is right, thank you for the correction. I edited the post. Can you tell me if your method results in the same number of combinations?

I get 7260 combinations adjusting for the fact that it is x1 <= 2

[snow sleet]

you know this can't be right since 15+4 choose 4 isn't greater than that

[snow sleet]

I'm getting 2056

,w 19 choose 4

[vital dew]

Results provided by WolframAlpha

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

Requested by logician#7452

[snow sleet]

and this was the answer for no restrictions^

since there are restrictions, your answer should be less than this^

Do case 1: That dog gets 0 donuts. Then distribute the 15 treats amongst the 4 other dogs

Do case 2: The dog gets 1 treat. Distribute the remaining amongst the 4 other dogs

Do case 3: The dog gets 2 treats...distribute etc...

Then add those up since there's no overlap, we don't need to subtract anything

[warm quest]

I'm getting 2056 by 19 choose 4 - 16 choose 4

[snow sleet]

ok, curious how figured 16 choose 4....

[warm quest]

because >= 2 is the same as 1 - >=3

[snow sleet]

yes

wait

[warm quest]

1 in this case being the sample space (idk if that is the actual combinatorics word for our set of all possible combinations)

[snow sleet]

at most 2 implies >=3 if you're doing the compliment

[warm quest]

oop

sorry tired that is what i meant

ye

[snow sleet]

I agree with this now

because

you can just fix 3 treats in that dog pretty much

[warm quest]

Would you happen to know how to back work from a specific number of combinations? I've had part (b) on my problem list for a while

[snow sleet]

not sure about that one.....

[snow sleet]

let's go back to this for a sec

[warm quest]

I know that part a) is C(10+4 - 1, 10) but I am pretty unsure of how you would actually find the number beyond plugging and messing around

sure

[snow sleet]

Here's how I did it....just to give you two more ways of doing this

,w Sum[Binomial[i+3,3],{i,13,15}]

[vital dew]

Results provided by WolframAlpha

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

Requested by logician#7452

[snow sleet]

That was the some of the cases that I outlined

also.....

I did this

,w Expand[Sum[x^i,{i,0,15}])^4(x^0+x^1+x^2)]

[vital dew]

Results provided by WolframAlpha

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

Requested by logician#7452

[snow sleet]

look at the coefficient of x^(15)

[warm quest]

out of curiosity, how does that account for the restriction?

[snow sleet]

the 4 dogs can take on treat values from 0 to 15, while that one can only take on values from 0,1,2

[warm quest]

oh i see

[snow sleet]

look at the exponents

yea

it's called a Generating Function

I'm kind of confused on that part a problem tbh how many baskets are there? and how many fruits are there in total??

I feel like there's some info missing

[warm quest]

Yeah that's kind of where I'm at and researching a bit hasn't helped. There's not examples in our book that are similar.

I know we are basically looking for C(10 + n - 1, 10) >= 5000

obviously n = 7

However, I have no clue how I would be expected to do this without just making an educated guess and checking the number

[snow sleet]

oh

oh yeah use factorials

[warm quest]

Well, what would that process really look like on paper?

[snow sleet]

use the formula for n choose k

[warm quest]

well, yes

[snow sleet]

n!/k!(n-k)!

[warm quest]

n!/k!(n-k)! >= 5000

however i do not have factorials memorized and it seems a little bit like just going back to the fundamental principle of counting

[snow sleet]

To be honest.....

and to be precise

You're asked to find the smallest positive integer n for which C(10+n-1,n-1) is at least 5000

so plugging and checking isn't necessarily a wrong way of doing this

[warm quest]

Yeah, that was my first thought. The professor just put "why?" as a comment for n = 7, as if there was some great explanation.

I appreciate you talking through these problems with me

[snow sleet]

To prove n=7, is the smallest n, you need to also show that n=6 gives an answer less than 5000

and also show it holds for n=7

those two things together prove n=7 is smallest such n

[warm quest]

Honestly that's totally fair, might ask about it in office hours just to make sure that was the expectation.

[snow sleet]

because realistically, someone could say n=10, and true it holds for 10=n, but it also holds for infinitely many other things (values of n larger than 6)

ping me if you need any more help on counting problems nice job on those problems! I like your approach of counting the compliment with that dog/biscuit problem @warm quest

[warm quest]

thanks man, I will! I really appreciated the reality check

@snow sleet Part C is another one I've been trying to crack for a couple days

obviously a and b are 10! and 8!

b) because you in essence create one object out of ALI and count permutations that way

[snow sleet]

I would arrange ALINDROM

[warm quest]

I may be over thinking 3, but there is 9! combinations of the letters before E

you mean fix p and e and see what the number is?

[grave sail]

hi, would someone be able to verify my work on a logic law problem, im not sure if I'm following steps correctly.

[snow sleet]

and then choose 1 of the 9 spots if you glued them together. and then add the case where you choose 2 of the 9 spots

[snow sleet]

not yet... but you can post it

[warm quest]

I considered that but I somehow convinced myself that there would be counting mistakes considering that the position of E and P can vary

[vital dew]

logician

[snow sleet]

because given 2 of the 8 spots, there is only one way to place the P and E so that P comes before E

181440 sound right?

Does my casework make sense?

count where P appears right before E

[warm quest]

not entirely sure I understand the methodology right now

[snow sleet]

try this easier approach...ready?

watch this

9!/2 is the answer

the number of ways in which P comes before E is the same as E before P

those two added together give 9!

make sense?

[warm quest]

wait so we just count all the permutations ignoring e and subtract out all the ones where the equivalent for P would be the same?

bro that actually makes A LOT of sense

[snow sleet]

exactly because the number of ways to permute the letters can be counted as 9! but also we could count the case where E comes before P and then the case where P comes before E (there are no other cases!) and then add them up to get 9!. So by symmetry, 9!/2, must be the answer to the problem u asked

[snow sleet]

not only did we count it one way, we counted this way too^ and got the same answer

[snow sleet]

what would you like to ask?

technically the logic channel would be better for that question, but I'll see if i can answer it here

@warm quest answer should be 10!/2 I miscounted how many letters are in PALINDROME loll

[grave sail]

Sure one sec

[snow sleet]

this should then be $8!\binom{9}{1}+8!\binom{9}{2}$

[vital dew]

logician

[warm quest]

I thought the 9! made sense as there are 9 letters before E, so we are counting all arrangements of those and dividing out the ones that would be after

[snow sleet]

PALINDROME is a 10 letter word

so I could say there are 10! permutations

or

I could count case 1: P comes before E (call that number x)

and then case 2: E comes before P call that number x

[warm quest]

I wonder if this is really equivalent to counting indistinguishable objects where P and E are really the same, so we do not consider their change of position.

The equivalent formula would be 10!/2!

= 10!/2

[snow sleet]

I think that may just be a special case since 3! doesn't equal 3. And 2!=2 as a special case

but yes you're right for that problem because you could replace P with E

[warm quest]

well, let's say there's 10 letters in our word and 3 of them are the same

[snow sleet]

but do you see how x+x=10!?

[warm quest]

it would be 10!/3!

[snow sleet]

right if 3 if the 10 letters were identical

[warm quest]

which on first examination seems the same if we held 3 position restrictions instead of 2

[snow sleet]

I kind of see what you're saying?

We could have also counted your problem by doing a nice overcomplicated sum

fixing where E went

last position

second to last

etc.

[warm quest]

that was my initial correct approach but I decided that was far too laborious for our class' spirit

[snow sleet]

I mean you're prolly right, but sometimes doing more approaches to the same problem is how you become good at counting

[snow sleet]

like this^

[warm quest]

you're right, I'm going to try and do some of our problem set in different ways. appreciate the help

[snow sleet]

looks good unless I missed a silly mistake that we all prolly woul've made too. Also, showing the truth table is sufficient

[grave sail]

Yea but I need to practice logic laws, anyways thank you I appreciate it !

[snow sleet]

There are things out there called combinatorial proofs that use counting arguments to establish a bijection between finite sets (and thus showing the sets are of equal size)...Like showing that the sum of C(n,i) where i goes from 0 to n is equal to 2^n.

$\sum_{i=0}^n\binom{n}{i}=2^n$

[vital dew]

logician

[snow sleet]

the left hand side counts subsets of size 0, then 1, then 2, and so on up to size n.

the right hand side counts subsets as well by listing the n elements and then saying yes if the element will be in the subset we're constructing or no it won't...so all such binary strings correspond to exactly one subset of the overarching n element set that we're counting subsets of

@warm quest just a little exposure to combinatorial proofs...pretty much doing the same idea of counting one thing in more than one way

anyway I'll leave you with that I'm off to sleep now.

[warm quest]

gn bro, I like the exposure. Our professor has been showing us a few proofs but they've been very hand waived

[foggy sentinel]

How many arrangements of the letters in FYSIKER preserve the order of consonants, i.e. 'Before S before K before R'

I'm desperate for help.. please

[coral parcel]

Can you count the rearrangement of XYXIXEX? For each of those there is exactly one way to replace the X's with F, S, K, R in that order.

[foggy sentinel]

I don't understand

[coral parcel]

Can you count the rearrangements of FYFIFEF?

[foggy sentinel]

7! ?

[coral parcel]

Even when some of the letters are the same?

[foggy sentinel]

Yes

[coral parcel]

Can you count the rearrangements of FFFFF?

[warm quest]

For the first problem, I got that the sample space is 12 choose 2 and that the probability of exactly one dog and exactly one cat chosen at random is (6 choose 1)(6 choose 1) / (12 choose 2)

[coral parcel]

Sounds right.

Because all 12-choose-2 outcomes are a priori equally likely.

[sage pelican]

is it enough for me to just say true, after writing ∀x∃y ¬ (x + y = 1)

[warm quest]

So, for the second problem I guess I really had the question: Wouldn't that be (6 choose 1) + (6choose 1) / (12 choose 2)?

Because we are expressing independent probabilities, but I think choosing a SPECIFIC one is making me overthink

[coral parcel]

You're counting the "Lilo and Stitch" poster twice.

[warm quest]

Well, that's true I think. I guess we could take the complement of (10 choose 2) and make that what we divide.

[coral parcel]

And you seem to be assuming you're now only interested in posters that happen to have one dog and one cat.

[coral parcel]

That would work.

[foggy gale]

if some x are y and z and some are not would that be ( ∃x y(x) ^ (z)) ^( ∃x y(x) ^ ¬(z))
or would it instead be ∃x ( y(x) ^ ((z) V¬(z)))

[warm quest]

1 - (10 choose 2) / 12 choose 2. I suspect this answer is faulty as it says that the probability of having one or the other or both is 31%, while they make up 2/12 of the sample space.

[coral parcel]

Well, the probability of the animal to the left being among the two named ones is 2/12 = 1/6, and the probability of the animal to the right being one of them is also 1/6. If we pretend (counterfactually) for a moment those two couldn't happen at the same time, the total probability would be 1/6+1/6 = 1/3, which is close to your 31%.

[warm quest]

That makes good sense, I appreciate the help

[foggy gale]

Or is this logically equivalent

This statement

if some x are y and z and some are not would that be ( ∃x y(x) ^ (z)) ^( ∃x y(x) ^ ¬(z))
or would it instead be ∃x ( y(x) ^ ((z) V¬(z)))

[warm quest]

One of my classmates gave the answer to part 1 with 1 + 5 choose 1 + 5 choose 2 + 5 choose 3 + 5 choose 4 + 5 choose 5

However, I viewed this as selecting from n = 10 donuts with repetition, with k = 5

so I got (14 choose 5), why would this approach not work?

[snow sleet]

Wouldn’t work because for instance u can’t have 5 sour cream donuts. U can only have at most one

[snow sleet]

,w Expand[(x^0+x)^5(x^0+x+x^2+x^3+x^4+x^5)]

[vital dew]

Results provided by WolframAlpha

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

Requested by logician#7452

[snow sleet]

,w 2^5

[vital dew]

Results provided by WolframAlpha

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

Requested by logician#7452

[snow sleet]

Their answer is right…I would just say 2^5 since for the five types that can have at most one, you just say yes or no for whether u’ll have that type and then the remaining if any will be from the one with at most 5

[tidal tulip]

For a given (false) claim and proof, what skills do you use to determine where the proof is false?

[snow sleet]

Depends on the statement and the “proof.” U got an example?

[tidal tulip]

I believe step 6 doesn’t make sense. Note that “ \ ” is minus and “ ‘ “ is complement

[snow sleet]

Does 10 look right? I don’t think so

[tidal tulip]

Same with 6 tho no?

Because why can’t X be in both A and B?

[snow sleet]

Yea I believe ur correct on that

[tidal tulip]

Similarly, I have another claim (true this time) but the proof is broke

[snow sleet]

Ok

Let’s see it

[faint sphinx]

6 is fine

(x in A \ B) if and only if [ (x in A) and (x not in B) ]
Taking negation we get: (x not in A \ B) if and only if [ (x not in A) or (x in B) ] by De Morgan's laws

Remember, logical "or" is not exclusive: You're right, you can have x in A and x in B

[snow sleet]

Oh wait true disjunctive syllogism

Yup k 6 is fine

[tidal tulip]

Oh I see

So it would be step 10

But I don’t understand completely why it’s 10

[snow sleet]

If x is in B, can it be in the set of things not in B???

No

Right

?

[tidal tulip]

Nope

[snow sleet]

Perfect that’s why

[tidal tulip]

But for A it works

[snow sleet]

So x is not in B compliment

[tidal tulip]

?

[snow sleet]

Yes because they stated it correctly for A

[tidal tulip]

Ok ty

And what about the second proof?

[snow sleet]

Case 2:4 and 5 don’t look right to me

Might be more statements wrong but those for sure are not correct

[tidal tulip]

2:4 as in 2,3,4?

Oh wait u mean case 2 like 4 and 5

[snow sleet]

Yes

Case 2 points 4 and 5

[tidal tulip]

So you think case one is completely right

[snow sleet]

Unless I overlooked something looks fine to me

[tidal tulip]

I was thinking case 1 step 5

What does it mean by “because x is not in B”

[snow sleet]

Literally that lol

If x is not in B, it’s not in A

And so it’s not in A minus B

[tidal tulip]

Say we have two sets A and B

A = {1,2,3}

B = {1,2,3,4,5}

A - B = {4,5}

Right?

[snow sleet]

Noo

A minus B is everything in A minus the things in A intersect B

B-A is {4,5}

[tidal tulip]

Oh shoot

It’s {}

For A - B

?

[snow sleet]

Right because everything in A is in B by assumption

[tidal tulip]

Ok

And say we have x = 3

So how would this info support case one line 5

[snow sleet]

Because if x is not in B it can’t be in A. So it wouldn’t be in A-B since it’s not in A in the first place

[tidal tulip]

Ohh I see

And this would disprove case 2 line 4

[snow sleet]

No

One step at a time lol

Case 2 line 4 states that since x is in B x is not in B-A?

Is that true? Prolly not

[tidal tulip]

We can use the same sets of A and B again to verify

[snow sleet]

Sure

[tidal tulip]

Since X = 3 is in B , x = 3 is not in {4,5}?

[snow sleet]

Nooo u did the opposite of a counterexample lol

[tidal tulip]

Yea I see that lol

[snow sleet]

Try x=4

Then x is in B

[tidal tulip]

Since X = 4 is in B , x = 4 is not in {4,5}?

[snow sleet]

And in B-A={4,5}

[snow sleet]

Read ur last part of that

[tidal tulip]

{4-5} = B - A

4 is in B - A

[snow sleet]

Yes u said it wasn’t

[tidal tulip]

Oh I was just plugging in the values from the prompt

Hence the question mark

[snow sleet]

Ok

So know u see why that line in the proof is wrong

[tidal tulip]

So, the prompt works for selected X values only

Not all?

[snow sleet]

All we need to do is show that the statement doesn’t hold for some sets A and B with A being a subset of B.

To show the line is false

[tidal tulip]

I see

[snow sleet]

They’re proving this so they need to prove it for all sets

All we have to do is come up with a counterexample

[tidal tulip]

Gotcha

Now I actually have to solve this proof lol

But I was also wondering would 2 cases for this claim be exhaustive?

[snow sleet]

Yes

Case 1: not in B case 2: in A

[tidal tulip]

Could it be simialr to when you use 1. X subset Y 2. Y subset X

[snow sleet]

Huh?

We’re not asked to show equality

[tidal tulip]

Like that?

[snow sleet]

This is a separate problem lol this is for showing two sets are equal

[tidal tulip]

Whaaa

[snow sleet]

Showing two sets are subsets of each other shows they’re equal

[tidal tulip]

This is the claim

[snow sleet]

And this is why they did this

[tidal tulip]

And I want to write two claims that are equivalent to the claim

[snow sleet]

Here^

[tidal tulip]

So what I did would be correct?

[snow sleet]

I’m so lost rn which ones did u do?

[tidal tulip]

Ok so

[snow sleet]

What claim lol? I’m so lost

[tidal tulip]

This is the claim and I want to write two claims that are equivalent

[tidal tulip]

So these are my two claims

And my next step is to proof these 2 claims

[snow sleet]

Okay but technically each of those two claims aren’t equivalent to the claim with equality

[snow sleet]

This is really one claim that’s equivalent not 2

[tidal tulip]

Right but the cases need to be exhaustive right

That’s why I’m using 2 claims