discrete-math

[west rain]

yep

oh wait that was a typo

here

[quaint star]

Oh, yes, typo

[west rain]

you mean gcd

okay yea that line makes sense now

[quaint star]

Now we look at the equations from the bottom to the top. The last equation gives us 1 as a linear combination 8 and 25.
$$1 = 25 - 8(3)$$
But the equation before that gives us 8 as a linear combination of 108 and 25, so we can substitute that in to get 1 in terms of 25 and 8. But then we can use the previous equation to replace 25 with 241 and 108, and then the one before that to replace 108 with 241 and 590. So we end up with 1 as a linear combination of 241 and 590, which is what we want. Okay, let me write it out.

[vital dew]

Lunasong the Supergay

[quaint star]

$$\begin{align*}
1 & = 25 + 8(-3) \
& = 25 + (108 + 25(-4))(-3) = 108(-3) + 25(13) \
& = 108(-3) + (241+108(-2))(13) = 241(13) + 108(-29) \
& = 241(13) + (590+241(-2))(-29) = 590(-29) + 241(71)
\end{align*}$$

[vital dew]

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

[quaint star]

So when I move to a lower row, I am using the previous equation to substitute in, then I simplify next to it.

See if you can follow what I did

[west rain]

yeayeayea I see what you're doing

[quaint star]

So we use each of the equations in the Euclidean algorithm to work our way back to 590 and 241, and we end up with

1 = 590(-29) + 241(71)

Now if we wanted to know the inverse of 241 mod 590

Then this equation reduces to 1 = 241(71) (mod 590)

So 71 is the inverse of 241 mod 590

And -29 is the inverse of 590 mod 241

Does that make sense?

So from 1 = mx + ny, we get that m and x are inverses mod n, and n and y are inverses mod m

Assuming m and n are positive

[west rain]

okay yea I think im following

im still processing it but I see what you're doing

[quaint star]

Okay, so if you want to implement this as code, you need to organize your data neatly. Because you need to store all of the equations in the euclidean algorithm, so that you can reverse them to get to 1 as a linear combination of 241 and 590

[west rain]

right

[quaint star]

Ima sleep now. But go through the process slowly, maybe try to to do an example on your own, and then try the code.

If you get stuck, ask again and I'm sure someone can help

[west rain]

thank you so much

[quaint star]

Np, good luck

[west rain]

at this point I think I have a good enough foundation. I'm gonna keep looking over what you did and try some for myself

gn

[quaint star]

👍

[hybrid crown]

(That was a helpful explanation on the euclidean algo for me as well)

[hybrid crown]

(so thanks!!)

[quaint star]

😂 yw

[hybrid crown]

(the words "linear combination" in particular helped crystalize it for me XDD)

[pale magnet]

I need help!!

[strange grotto]

suppose g has a vertex which is not connected. then maximum possible connected vertex would be n-1. so maximum possible edges would (n-1) choose 2. but edges are (n-1)C2+1. contradiction.

[pale magnet]

Thanks, i was trying by induction

[strange grotto]

ok base case is clear. consider graph with n vertices with (n-1)(n-2)/2 +1 edges and assume it is connected. add a vertex. now suppose this is not connected. but this (n+1) graph has n(n-1)/2+1 edges. that is, we have to add n-1 edges in the new graph such that it is not connected. note that we can only add a maximum of n-2 edges (nC2- (n-1)C2-1) in the graph with n vertices. contradiction. thus (n+1) graph is connected if n is.

Thus all graphs are connected.

[pale magnet]

So thanks!

😄

[mortal kiln]

I’m taking discrete math and have no math background, I’m stuck on this question, would appreciate your response. We have 7 balls, each of a different color, that we are placing in 3 different boxes, each of a different size. How many ways are there to do this so that none of the boxes are empty?

[stray reef]

without the "none of the boxes are empty" constraint the number of ways would be 3^7

...i take it that you aren't familiar with the inclusion-exclusion principle?

@mortal kiln

[mortal kiln]

I’m not

[stray reef]

damn

would've made things a lot easier

do you at least understand why the number of arrangements is 3^7 if you don't care about the boxes being empty?

[mortal kiln]

I always get confused about these type of problems because I don’t know if I have to use combination or not

[stray reef]

if by 'combination' you mean the n-choose-k thing, it's no more than a shortcut for some multiplicative counting.

you don't "use" it; it arises naturally.

[mortal kiln]

So we don’t use it in this problem?

[stray reef]

are you familiar with the more basic concept of multiplicative counting? perhaps it goes by some other name (or no name at all) in your class

[mortal kiln]

Yes

[stray reef]

well then

look at your problem like this: for each ball, there are 3 options for where it could go (the small box, the medium box or the large box)

and there are seven balls

so the number of arrangements (again, ignoring the 'no boxes empty' thing for now) is 3 * 3 * 3 * 3 * 3 * 3 * 3, or 3^7 for short

does that make sense to you?

[mortal kiln]

Yeah thanks

[stray reef]

now obviously this count will include some arrangements that we don't want

i.e. arrangements that leave some boxes empty

so if we were to count those, we could subtract them from our count of 3^7 and get the answer

does this make sense to you?

[mortal kiln]

So if the question was for example asking at least 2 balls in each box, would it be different?

[stray reef]

?

you haven't answered my question...

[mortal kiln]

Yeah that part made sense

[stray reef]

but yes you'd have to do it somewhat differently if the requirements were different

should i continue or are you going to attempt this on your own?

[stray reef]

👻

[mortal kiln]

If you can continue it would be really helpful tnx

[unreal stump]

This is from an old test

(and our professor doesn't share the answer key with us)

Should the answer be C(u,t)-1?

Because pick x from some group and there are C(u,t)-1 groups that x is not in

And each such group gives one value to x

[last timber]

@unreal stump is it given that K_a != K_b for distinct groups?

[unreal stump]

This is all I have

Yes,It could be less than C(u,t)-1

[last timber]

also how you treat case when t > u and we have zero groups

someone should get -1 numbers than

[unreal stump]

Ok,This is a very bad question

[last timber]

and this question is vague on whether groups are disjoint

[unreal stump]

Assume u>t,K_a's are all distinct and the groups don't intersect each other

[last timber]

then it seems that yes C(u,t)-1

oh wait

still

@unreal stump u = 5 and t = 3

we are able to form only one group

and there will be 3 ppl with no number

and 2 ppl with one number

[unreal stump]

Apparently C(u,t) here means ${u \choose t}$

[vital dew]

Buncho Dragons

[last timber]

@unreal stump but then groups are not disjoint

[unreal stump]

Yes,The groups are not disjoint

Apparently

[last timber]

oh lol

[unreal stump]

This question is just too vague

[last timber]

[young vector]

should I ask some very simple entry-level questions about topology here or should I apply for access of the topology channel?

[stray reef]

you can type ,iam adv to get advanced access lol

[last timber]

in #bots

[young vector]

yeah I was just thinking whether it's okay to clog advanced channels with simple layman questions 😄

[stray reef]

i mean you can post your questions here if you want

theyre probably to do with proof techniques or something of the sort

[ocean island]

Ty

[ocean island]

Can someone explain this step

[obtuse lance]

it might be easier to see written out

$S_n=a+ar+ar^2+ar^3+...+ar^{n-1} +ar^n$

[vital dew]

Merosity

[obtuse lance]

multiplying by r shifts all the terms basically

$rS_n=ar+ar^2+ar^3+...+ar^{n-1} +ar^n+ar^{n+1}$

[vital dew]

Merosity

[obtuse lance]

does that much make sense @ocean island

[ocean island]

Ok

But I dont get the removing step?

[obtuse lance]

the right side is nearly the same

[ocean island]

Yeah

[obtuse lance]

$rS_n=-a + (a+ar+ar^2+ar^3+...+ar^{n-1} +ar^n)+ar^{n+1} = -a + (S_n)+ar^{n+1}$

[vital dew]

Merosity

[obtuse lance]

-a is the j=0 term we put in and ar^{n+1} was an extra one we got out, otherwise all the terms inside are the exact same

[ocean island]

Oh

Wait why is -a the k=0 term

[obtuse lance]

well the k=0 term of S_n is a

so I'm adding 0 = -a + a

so I'm not actually changing anything, just completing the formula for S_n there by adding 0 in a fancy way

[ocean island]

oh

I see what you mean

So what you wanna do manipulate rSn in a way that matches Sn

[obtuse lance]

yeah, it's just the first and last terms that sort of get messed up

[ocean island]

And to do that, you need to add the "a + -a"

[obtuse lance]

so we fix those two end terms up, yeah

that fixes up the first term

the last term we just pull out cause ar^{n+1} is not in S_n

[ocean island]

Ah

I see it

Yeah that makes a lot sense now

Thanks haha XD

[obtuse lance]

yeah you're welcome

definitely a cool trick haha

cause it's like looking at a pattern in the equation, usually you're not looking at patterns in the formulas and stuff themselves which is kinda neat

[ocean island]

Yeah

If only this book explained it better lol

[obtuse lance]

when I learn math from books I usually get multiple books on the same topic and then if I get an explanation I don't like I just go to a different book to find an explanation I do like haha

[warped pecan]

Any ideas?

[weary tiger]

Hint: ||Can anything be simplified with Fermat's Little Theorem? ||

[warped pecan]

I can’t figure it out?

@weary tiger

[weary tiger]

Do you need another hint?

Use fermats little theorem

like you know a^11 =a mod 11

[warped pecan]

Oh I was taught a different version I guess?

Like k^(p-1) is congruent to 1 modp

[pale epoch]

that's the same, just multiply by k

[warped pecan]

But can I like add up remainders?

[pale epoch]

what do you mean?

[warped pecan]

Am I at least one the right track

[pale epoch]

ye, but you can reduce more

[warped pecan]

How?

[pale epoch]

$2^{202} = (2^{10})^{20}\cdot 2^2 \equiv 1^{20}\cdot 2^2 \pmod{11}$

[vital dew]

Lochverstärker

[warped pecan]

How do you go from 2^10^20 to 1^20?

Ah formats

[pale epoch]

2^10 = 1 mod 11 by fermat

[warped pecan]

Yes

Okay but if I do that for everything, do I like add each one up?

[pale epoch]

and general rules for congruences

[pale epoch]

yes

if a = b mod n and c = d mod n, then a + c = b + d mod n

that's the general theorem

like, you want to replace 2^2222 by the smallest possible representative mod 11

which is a number between 0 and 10

and there is some theorem that tells you that you can do this

in this case that smallest representative is 2^2 = 4

[warped pecan]

Ohhhh I see

Is this right the?

For the @pale epoch

[pale epoch]

i think so

im gonna trust your ability to do arithmetic more than mine

[warped pecan]

Hahaha okay but now how do I go about simplifying that

[pale epoch]

you calculate it

[warped pecan]

Oh I see

Since the one for 2 also came out to be 4 mod 11?

Is there something with that?

[pale epoch]

huh?

[obtuse lance]

it might help to think since x^10 = 1 mod 11 that you can imagine it being x^10 = x^0 mod 11 and so you're really thinking mod 10 in the exponent

and since the exponents are written in base 10 you can immediately just leave the last digit and write,

$2^2+4^4+6^6+8^8 \mod 11$

[vital dew]

Merosity

[abstract iron]

uhhh

I got a question

involving truth tables

so I know this is tautology

but like not sure how to explain it

[rotund frigate]

It says Using a truth table. You can determine whether a formula is a tautology by seeing if it is true for all possible inputs.

[mint shore]

can someone explain to me how this is broken down?

it's from a solved exercise and simplifications are skipped

solving a recurrence relation w generating function

that part kinda confuses me

the $3^n$ part can just be turned into $\frac{1}{1-3x}$

[vital dew]

Subdivisions X-1

[mint shore]

but how do you handle the other part?

just given this in terms of getting the sum out of the way

but here instead of u there is n+2

and it's screwing w my head a little

[obtuse lance]

$$\binom{n+2}{n} = \frac{(n+2)!}{n!(n+2-n)!} = \frac{(n+2)(n+1)n!}{n!2!} = \frac{(n+2)(n+1)}{2}$$ now you're effectively just looking at $\sum_{n\ge 0} (n+2)(n+1)x^n$, you know how to simplify from here? @mint shore

[vital dew]

Merosity

[abstract iron]

yeah but the 0's and 1's

I'm not the best at discrete maths mind you lol

[mint shore]

yea i do, thanks tons

[livid elk]

Show that for any positive integer $n$, there is exactly one positive integer $k$ for which $\frac{k}{2}(k-1)<n\leq\frac{k}{2}(k+1)$. Give a formula for finding this $k$ using floor functions.

[vital dew]

-vertex

[unreal stump]

Hint sum of natural numbers

[livid elk]

Looking for some insight as to where to start here. Cant seem to find it

[unreal stump]

You can find a k such that
n<=1+2+3+4...k

Now this k will be unique assuming you also use that 1+2+3...(k-1)<n

[livid elk]

ahh i see

clever with the natural number sum

appreciate it @unreal stump '

[livid elk]

I have shown that for any positive integer $n$, there is exactly one positive integer $k$ for which $\frac{k}{2}(k-1)<n\leq\frac{k}{2}(k+1)$. However I can't seem to come up with a formula using floor functions to find $k$. Any hints?

[vital dew]

-vertex

[last timber]

@livid elk you prolly may solve two inequalities

[vital dew]

Commander Vimes

[livid elk]

@last timber i played around with that, but couldn't seem to find anything.

[warped pecan]

How can I prove two Fibonacci numbers are comprime?

Coprime*

[civic horizon]

you have to be a bit more specific

2 and 8 are fibonacci numbers but they arent coprime

[warped pecan]

Oh sorry two consecutive

[civic horizon]

spamming the euclidean algorithm probably works

[warped pecan]

What do you mean?

[civic horizon]

gcd(a, b) = gcd(a, b-a)

using that repeteadly might be good

[warped pecan]

This is dumb but why is that true?

Like the second part

[stray reef]

any common divisor of a and b also divides b-a

and any common divisor of a and b-a also divides b

[warped pecan]

Linear combination

But the how is the fact that it divides equivalent to it being the greatest common divisor

[stray reef]

let S = {k in N: k divides a and b} and T = {k in N: k divides a and b-a}

do you agree that max(S) = gcd(a,b) and max(T) = gcd(a,b-a)?

[warped pecan]

Yes

[stray reef]

okay and so you agree that S = T by the argument i just presented?

[warped pecan]

Are the ks the same?

[stray reef]

that question is nonsensical

[jade birch]

Would anyone care to critique my proof? https://imgur.com/a/rPTUr0I

[odd trout]

HELP ME

[manic dome]

I proved it is an equivalence relation, but how do I write out the equivalence classes for this

[jade birch]

@manic dome prove it

[jade birch]

check my proof bros https://imgur.com/a/mEn9Iud

[modern dew]

hello

[jade birch]

hi

[warped pecan]

Anyone know how to prove it forward?

[obtuse minnow]

Hmm … hint?

If 11 divides A, 11 divides 2A or 3A or 4A or 5A or 6A or 7A or 8A or 9A or 10A

[red nest]

Try multiplying both sides by 9

[deft dock]

what is this even asking me to do???

[rotund frigate]

They want you to eventually prove t.

[jade birch]

@deft dock whaty isn't clear about that?

[timber sage]

hey anyone here know what all the symbols means like pyramids and stuff in mathmatics

[stray reef]

'pyramids and stuff'?

the meaning of a symbol is very likely to highly depend on context

@timber sage can you show the symbols whose meaning you're interested in?

[timber sage]

sure

i am trying to understand this..

in a bellman ford context

[stray reef]

those "pyramids" are just the capital letter Delta

[timber sage]

it would really help to know the name of the theory involved like a wikipedia page or something

[stray reef]

and in this context, they're being used to denote traded amounts of... coins?

[timber sage]

right

but how do we get to a maximum for a path i dont get it

[stray reef]

this sounds like some kind of cryptocurrency economics thing

[timber sage]

well it could just as well apply to resistor flow but yeah

thing is most flow theorys do not seem to account for the dynamic nature of the constant function on the edges

from what i could tell and i am super noob at this

i dont see why they use square root there also

[glass condor]

How can I find the solutions $n$ of $$N n = 0 \mod k$$ for some $N$ and $k$? What I've got is that it means $N*n$ is a multiple of some multiple of $k$, meaning that we can calculate the prime decomposition of $k$, remove from it the parts that are in $N$, and the remaining parts will be the lowest $n$. Is that the only way, or am I missing some more obvious one?

[vital dew]

ConfusedReptile

[glass condor]

oh wait that's just k/gcd(N,k), is it...

[obtuse lance]

yeah, or you could write it as lcm(N,k)/N, that at least is how I thought of it, since it has to be a multiple of k and N, so we pick the least one, then since we already have N, we can divide it out of what we need to complete n.

of course they're related by gcd(N,k)lcm(N,k)=Nk so it's all the same thing

[deft dock]

and we use each premise only once right?

[livid elk]

Why must $\frac{n!}{r!(n-r)!}$ be a positive integer whenever $n$ and $r$ are non-negative integers with $r\leq n$

[vital dew]

-vertex

[livid elk]

Since $n,r \in \mathbb{Z^+} \land r\leq n,$\hspace{2mm}$ \frac{n!}{r!(n-r)!}$ is the quotient of two positive integers, which must be positive.\
There are $\frac{n!}{(n-r)!}$ permutations of $r$ distinct elements that can be made from an $n$-element set, and there are $r!$ ways to order each $r$-element subset. Therefore, the number of $r$-element subsets is:\
$\frac{1}{r!}\frac{n!}{(n-r)!}=\frac{n!}{r!(n-r)!}$\
Since the number of $r$-element subsets must be a positive integer, $\frac{n!}{r!(n-r)!}$ must be a positive integer.

[vital dew]

-vertex

[livid elk]

does this proof suffice?

[cerulean wind]

yes this is a good combinatorial argument

[livid elk]

@cerulean wind great, thanks

[modern dew]

i should prove that

[narrow trench]

is φ the totient function ?

[weary tiger]

you should

[weary tiger]

yes

[modern dew]

it is

[dull slate]

really interesting 💗

$\phi(n) = n\prod_{\begin{array}[c] p \in \mathbb{P} \ p | n \end{array}}(1-\frac{1}{p})$

[cerulean wind]

why are you using an array

[dull slate]

to make p \in P and p | n in one column

lol

[cerulean wind]

use \substack

and use \nmid for |

[dull slate]

how does that work?

[civic horizon]

\nmid is not divides

[cerulean wind]

like this $\sum_{\substack{n=1\\text{p is prime}}\ \text{another line}}\text{your mom}$

[dull slate]

tnxxxxxxx

is there another one for mutli columns?

[cerulean wind]

right. it’s \mid for a | b

just keep using substack

[dull slate]

and for multi eqtions?

[cerulean wind]

maybe not? lmao

[dull slate]

ive been using this

[dull slate]

why just not let it | ?

$\phi(n) = n\prod_{\substack{ p \in \mathbb{P} \ p | n }}(1-\frac{1}p)$

[vital dew]

4z1z

[dull slate]

[cerulean wind]

cus cool kids use \mid and \nmid lol

[vital dew]

-vertex

Show that $\forall n \in \mathbb{Z}^+, n^2\mid [(2+n)^n-2^n]$ at first glance this seems to rely on induction, however it does not seem to work, as 

$n=k$ $\rightarrow$ $(2+k)^k
$n=k+1$ $\rightarrow$ $(k+3)^{k+1}

Is there something im missing?
```Compilation error:```! Missing $ inserted.
<inserted text> 
                $
l.58 $n=k+1$ $\rightarrow
                         $ $(k+3)^{k+1}
I've inserted a begin-math/end-math symbol since I think
you left one out. Proceed, with fingers crossed.```

-vertex

[livid elk]

Show that $\forall n \in \mathbb{Z}^+, n^2\mid [(2+n)^n-2^n]$. At first glance, this seems to rely on induction, however it seems to not work, as

$n=k$ $\rightarrow$ $(k+\textbf{2})^k-2^k=k^2P$
$n=k+1$ $\rightarrow$ $(k+\textbf{3})^{k+1}-2^{k+1}=(k+1)^2Q $

is there someh

[vital dew]

-vertex

[livid elk]

something im missing*

assume n=k, prove n=k+1 that is

[obtuse minnow]

Do you have to use induction?

I think I see a non-induction way of proving it?

[livid elk]

no, it is not necessary to use induction, it was just my only intuition here.

[obtuse minnow]

Yeah, how much do you know about Combinations as they relate to the binomial theorem?

Sorry, like, is that something you can use to solve this?

[livid elk]

I dont think i could formulate a proof using that method, however I could probably follow yours.

possibly* lol

[obtuse minnow]

so okay what are the terms for (a + b)^n ?

[cerulean wind]

oh nice

[obtuse minnow]

Then think about a = 2 and b = n. Then think about what happens to the leading term.

[livid elk]

$(a+b)^n=(C{n,0})a^nb^0+C{n,1})a^nb^1+...+(C_{n,n}a^0b^n$

[vital dew]

-vertex

[obtuse minnow]

yep okay plug in 2 for a and n for b.

[livid elk]

well i fucked it in discord but you get it lol

[obtuse minnow]

I'll assume you can clean it up later.

(i.e. we're good?) 🙂

Tell me when you're done with (2 + n)^n and what the first term is.

[livid elk]

sorry, one minute, on the phone

[obtuse minnow]

kk

[livid elk]

sorry, work, the first term is $2^n$

[vital dew]

-vertex

[obtuse minnow]

yep. So it cancels with the - 2^n right?

[livid elk]

right

[obtuse minnow]

So what about the next few terms?

(First term, check! It's zeroed out by the -2^n. Zero is good in this case.)

[livid elk]

$\frac{2^{n-1}}nn!{(n-1)!}$

[vital dew]

-vertex

[livid elk]

$\frac{2^{n-1}n*n!}{(n-1)!}

$\frac{2^{n-1}n*n!}{(n-1)!}$

[vital dew]

-vertex

[obtuse minnow]

is that divisible by n^2?

[narrow trench]

yeah

what's n! equal to ?

[obtuse minnow]

Let's just say: 3! = 3 x 2 x 1. 6! = 6 x 5 x 4 x 3 x 2 x1

[livid elk]

yes, i see why its divisible by 2

n^2*

[obtuse minnow]

For Systems ... There's a nice generalization about (n!)/((n-1)!). It's equal to just "n." (3 x 2 x 1)/(2 x 1) = 3. (8 x 7 x 6 x 5 x 4 x 3 x 2 x 1)/(7 x 6 x 5 x 4 x 3 x 2 x 1) = 8.

[narrow trench]

yup

[obtuse minnow]

So vertex, what are the rest of the terms? Are they EACH divisble by n^2? 🙂

[narrow trench]

because n! = n*(n-1)* ... * 2* 1 = n * (n-1)!

[obtuse minnow]

Yep.

@livid elk Can you argue the third, fourth, up to the last terms are all divisible by n^2?

[livid elk]

all remaining terms take the form $\frac{2^{n-k}n*n!}{(n-k)!k!}$ so are divisible by $n^2$

[vital dew]

-vertex

[obtuse minnow]

hmm not quite.

I gotta go in 10-15 🙂

I should go. Here's what we've discussed so far and that last bit that might need induction.

||
Facts:

1. All C(a,b) ... all combinations ... are whole numbers.
2. The k'th term of a binomial expansion (a + b)^n is C(n, k - 1) a^(n-k+1)b^(k-1).
3. n divides C(n, 1).

Consider (2 + n)^n. The first term is 2^n which nicely cancels with the 2^n we need to subtract!!

The 2nd and 3rd and other terms are C(n, 1)(2^(n-1))(n) + C(n, 2)(2^(n-3))(n^2) ...

Notice the second term has the product of C(n, 1) and n and as such is divisible by n^2.

Notice also each term after that has n^(k+1) where k+1 > 1. n^2 divides the n^(k+1) part of every term from the third to the last!!

And that's it!!

The first term gets subtracted to become zero (zero is auto-divisible by n^2). The second term has a factor of n^2 because of C(n,1) and n^1. The rest of the terms have a factor of n^(k+1) and because of this, each of these remaining terms have a factor of n^2.

When you add up multiples of n^2 you get a multiple of n^2. So the whole thing is divisible by n^2.
||

[livid elk]

thanks, really appreciate it

[obtuse minnow]

yeah, gotta go

yw!!

[shell flicker]

how do I exactly prove this, this makes senses to me because otherwise it wont be true, but I have no idea how to prove this formally

[cerulean wind]

A and B are subsets of some other set correct?

anyway, it doesn’t really matter. $$2^{|A|}=2^{|A\setminus B|+1}$$ so $|A|-1=|A\setminus B|$ hence there is only one element of A that is also a member of B, and the conclusion follows

[vital dew]

coycoy

[shell flicker]

thank you!

[deft dock]

where does the d come from???

should it say "for all integers a, b, c, and d" instead?

[narrow trench]

yeah

[deft dock]

[deft dock]

Prove the statement: For all integers a,b and c, if a|c and b|d then ab| cd .

Proof:
Suppose a, b, c, and d are any integers such that a|c and b|d.
By definition of divisibility, c = k * a, for some integer k and d = y * b, for some integer y.
Thus, c * d = (k * a) * (y * b) = k * y * a * b by algebra and the distributive law.
Let x = k * y
By substitution, c * d = x * (ab), where ab, x, and c * d are integers because products of integers are integers.
Thus, cd is divisible by ab for some integer x

is this correct?

[cerulean wind]

yea

[deft dock]

im actually getting the hang of this

for a first time proof class id say im not doing too bad

[deft dock]

i think this is correct as well?

[cerulean wind]

yup

nice

[deft dock]

[deft dock]

did i write this correctly?

how would i go about proving this?

[deft dock]

also for this why dont we mention infinity and just go separate ways

[snow sleet]

For this problem the formal predicate logic notation would be $\forall x\in\mathbb Z: 5|x\implies 5|-x$.

[vital dew]

logician_pdx

logician_pdx

[snow sleet]

we don't just mention infinity because doing so would be an instance where we're assuming what we're trying to prove. We're trying to prove there is no greatest even integer, so we can't/shouldn't assume there is no greatest integer to begin with.

[deft dock]

my night in shining armor

[deft dock]

ah this makes sense

[snow sleet]

@deft dock So the proof you provided that shows there is no greatest even integer works because if you give me any even integer, I can find another even integer greater than it. In predicate logic: For any even integer N, there exists an even integer M such that M>N. So there must not be a greatest even integer because if there were, we've shown we can find one greater than it, a contradiction.

[deft dock]

mhm

so my proof works right?

[snow sleet]

oh that was your proof with M and N?

nice!

[deft dock]

could you check this proof as well?

[snow sleet]

before I check that one, do you mind if I slightly reword your proof that there is no greatest even integer?

[deft dock]

here:

Suppose that there is a greatest even integer called N.
Hence, N > n, where n is all even integers.
Let M = N + 2. M is an even integer because it is the sum of two even integers.
Thus, M > N because M is two more than N (M = N + 2)
So, this means that M is greater than the greatest integer, N. This contradicts our original assumption.
Hence, the given statement is true.

so you can edit without having to type everything

[snow sleet]

kk thanks; imma code it using the LateX bot here

[deft dock]

you can type this later but

is -5 | x the same as 5 | -x?

[vital dew]

logician_pdx

[deft dock]

at least in terms of proofs?

[deft dock]

woah

wait what

everything after M = N + 2 > N becomes a blur

[snow sleet]

yes, -5|x is actually equivalent to saying 5|-x since there's an underlying equation there and you can just apply/delete negative signs from both sides to obtain the other., but 5|-x makes more sense given the english statement you were trying to transform into predicate logic

okay so if we assume N is the greatest even integer. Then this must mean that any integer greater than N isn't even

[deft dock]

got it

mhm

[snow sleet]

but we've shown M=N+2>N is even

so N must not be the greatest even integer.

[deft dock]

mhm

right right

[snow sleet]

it's essentially a "maximal criminal proof"

[deft dock]

never heard of it

we must be behind or something

[snow sleet]

the maximal criminal was N

[deft dock]

this is a summer de class anyways

[snow sleet]

we assumed there was a counterexample, then there must be a greatest counterexample

which we called N

it's typically not a method of proof anyone really teaches

[deft dock]

i thought m was the counterexample

[snow sleet]

we didn't assume M was the greatest even integer

we assumed N was

[deft dock]

ohhhh

but M is the counterexample no?

or contradiction?

[snow sleet]

M is what we used to give us a contradiction

[deft dock]

idk math vocab is weird

i hate it

[snow sleet]

we could have used M=N+4

or M=N+100

[deft dock]

wait so then whats a counterexample

i thought contradiction = counterexample

[snow sleet]

so we assumed for the sake of contradiction, that the statement we're trying to prove was false. This means we assumed there was a counterexample

a counterexample is something that renders a mathematical statement false.

[deft dock]

so...

a contradiction???

[deft dock]

ohhhhhhhhhhhh

[snow sleet]

a contradiction isn't a counterexample

[deft dock]

counterexample is a contradiction

[snow sleet]

a contradiction is something like x<x

[deft dock]

a counterexample would be specific values that make that true?

[snow sleet]

no

consider the statement

[deft dock]

[snow sleet]

if x is prime, then x is composite

a counterexample would be x=2.

this is because 2 is prime, but 2 isn't composite

see how there's no contradiction here

[deft dock]

mhm

[snow sleet]

so in our proof, the fact that we had M>N and 2|M, those two things together contradict the maximality of N

[deft dock]

why 2|M?

where does that come from

[snow sleet]

so 2|M means M is even, right?

this is because M=N+2, and the sum of 2 even integers is also even

[deft dock]

oh.

ahhhhhh

[snow sleet]

2|2 and 2|N, so 2 divides the sum 2+N=M

yeah you got it!

[deft dock]

wait wait

so instead of 2k = M

youre saying 2|M?

for how even?

but same thing?

wait

OHHHHHHHHH

yes yes

same thing

because |

[snow sleet]

if 2k=M for some integer k, this by definition of divisibility means 2|M

[deft dock]

and QRT

[snow sleet]

right

[deft dock]

ah yes yes

woahhhh

so simple but ive never seen it manipulated that way

[snow sleet]

by QRT, do you mean the division algorithm?

yes, slick proofs are fun right?

[deft dock]

yeah the whole n = 2d + q or wtv

[deft dock]

no.

proofs are terrible

[snow sleet]

gotcha; yeah that's also known as the division algorithm

[deft dock]

i wanna go back to caclulator man

[snow sleet]

lmao

[deft dock]

precalc to discrete was a large jump

[snow sleet]

proofs are fun once you get the hang of it and appreciate the beauty of the logic behind proofs.

damn that is quite a jump

I've already taken discrete, but sounds like you're handling the jump quite well!

keep up the good work!

[deft dock]

i hope so im hangning on by a thread because its a de class

[snow sleet]

what's de?

[deft dock]

wait could you check that 3 cases abomination proof?

[deft dock]

dual enrollment

[snow sleet]

oh gotcha

yeah sure let me see it again

[deft dock]

im still in high school im going into my junior year this year

[snow sleet]

wow, that's impressive actually.

[snow sleet]

I didn't get to discrete till bout sophomore year in college

[deft dock]

comedically i took this class for fun because i saw it didnt have any pre reqs

[snow sleet]

lmao

so first off, I noticed they left off 4q+3

[deft dock]

yeah strange

[snow sleet]

4q+3, should be there

[deft dock]

also

in my webassign

those werent even there

instead they were

hold on

n = 2q and n= 2q +1

instead of the 4q stuff

same proof as well

almost

wait so why is the divisor two in one place and 4 in another?

with the other one having 4q, +1, +2, and +3 (not included)?

[snow sleet]

oh nice proof

well so if n is even, then n=2k for some integer k. For that same integer k, n^2=(2k)^2=4k^2.

[deft dock]

[deft dock]

mhm

[snow sleet]

If n is odd, then n=2l+1 for some integer l. For that same integer l, n^2=(2l+1)^2=4l^2+4l+1=4(l^2+l)+1.

given an integer n, n is even or n is odd...hence only two cases to consider

[deft dock]

right right

but i still dont get the disparities

[snow sleet]

by disparities, you mean what?

[deft dock]

or wait.

actually

the whole thing with 2q + 1 and 2q

and the other stuff with 4q and other constants

[snow sleet]

that's just breaking up the integers into even and odd integers

[barren rose]

anyone know how to see what a recurrence relation converges to

[snow sleet]

the QRT is just saying "you give me an integer n, and for that n, n leaves remainder 0,1,2,or 3 after division by 4"

[deft dock]

okay

wait but

how are we

hold on

[snow sleet]

not me unfortunately sorry

[deft dock]

i dont think im explaining what im confused about

okay so

i have two of the same statements that they want me to proove

they want me to proove the same things

but

why is it that in one of them

we assume the divisor is 2

and in the other one we assume the divisor is 4

?

[snow sleet]

again, this has to do with how we can break up the set of integers.

splitting up the integers into evens and odds is a much quicker way of doing this than covering all four cases (4q+0,4q+1,4q+2,4q+3).

so you could totally use the (4q+0,4q+1,4q+2,4q+3), route...it'd just be longer than necessary

want me to write a proof for this?

[deft dock]

so

n = 2q +1 and n = 2q

is the same as

(4q+0,4q+1,4q+2,4q+3).

?

[snow sleet]

no!!!!!

[deft dock]

[snow sleet]

recall what the QRT guarantees given the integers n and 2

and then given the integers n and 4

so do you agree that an integer is either even or odd?

[deft dock]

yeah

[snow sleet]

okay, so 2q, 2q+1 makes sense, right?

either the integer is divisible by 2, hence 2q...or the integer isn't divisible by 2, hence 2q+1

[deft dock]

yup even/odd

[deft dock]

mhm

[snow sleet]

okay so do you also agree an integer is divisible by 4 or not divisible by 4?

[deft dock]

yes

[snow sleet]

if an integer is divisible by 4, we can write it as 4t right?

[deft dock]

yes

[snow sleet]

for some integer t*

awesome.

and if that same integer isn't divisible by 4, how can we write it?

we could write it as 4t+1, 4t+2, or 4t+3

right?

In other words, if n isn't divisible by 4, then n leaves a nonzero remainder after division by 4

[deft dock]

yes

wait

OHHHHHHHHHHHHH

[snow sleet]

awesome!!

[deft dock]

we stop at 3

because remainder no bigger than divisor

okay okay

[snow sleet]

right, because 4t+4=4(t+1)

[deft dock]

keep going

[snow sleet]

perfect

so we can break up the integers into even or odd

or we can break it up into 4 cases (divisible by 4 (one case) or not divisible by 4 (three cases))

[deft dock]

so either or works?

okay so

i get even and odd

but why specifically 4?

why not 6?

oh wait.

lemme guess

more cases?

[snow sleet]

you could break up the integers into those divisible by a million and those not divisible by a million, but you wouldn't wanna have to cover a million cases explicitly in a proof

[deft dock]

yeah...

so

if 2 yeilds less cases,

why was 4 present?

[snow sleet]

present in your three cases proof? or the other proof you showed?

[deft dock]

in the three cases proof

did my teacher just put it for more exposure ig?

[snow sleet]

oh, well maybe your teacher just wanted to show you another way of doing it, tho I'd argue he/she shouldn't have left off the 4q+3 case

[deft dock]

yeah im gonna email but i alr turned in the assignment so it should be ight

but other than that thanks a lot

[snow sleet]

you're welcome!

@deft dock I'll write up a proof for that problem and then post it here both for you and others

[vital dew]

logician_pdx

[barren rose]

Know how to do part a ?

[obtuse lance]

what methods did you cover in the notes?

[barren rose]

. Substitution, Iteration. There might have been one more

et me check

let*

[olive wraith]

to check does 1/4 is greater than 1/2 should we convert it onto decimal form

[snow sleet]

no

[olive wraith]

like .25 and 0.5

[snow sleet]

just check that 2<4, so 1/2>1/4

[vital dew]

logician_pdx

[olive wraith]

right

[vital dew]

logician_pdx

[weary tiger]

$a_n = a_1(f(2) \cdot f(3) \cdot f(4) \cdots f(n))$ I think

[vital dew]

omeganebula

[weary tiger]

but dunno about the method covered in your notes

[weary tiger]

$f(n) = \frac{n+1}{n-1}$ btw

[vital dew]

omeganebula

[olive wraith]

just reading discrete math book in universal quantifires come this staement Ax(x^2 >=x)

domain is real numbers

[snow sleet]

um so what's A there?

[olive wraith]

(1/2)^2 >=1/2 is false

[unreal stump]

You mean $\forall x$ ($x^2>x$)

[vital dew]

Buncho Dragons

[olive wraith]

yes excatly

[unreal stump]

That's false yes

[olive wraith]

how you guys right this formate ?

[vital dew]

logician_pdx

[unreal stump]

mb

[snow sleet]

I use LaTeX

[unreal stump]

Also is $\forall x \in R$ a valid first order quantifier?

[vital dew]

Buncho Dragons

[unreal stump]

I don't usually see people using \in in a FOL Statement

[snow sleet]

wym @unreal stump ?

he said the domain was the set of reals

[olive wraith]

he

[unreal stump]

Like people write
$\forall x (x^2>0)$ but not
$\forall x\in R (x^2>0)$

[vital dew]

Buncho Dragons

[unreal stump]

Is that because the convention is understood(i.e.,we know x is a member of R)

[snow sleet]

depends on the context

[vital dew]

logician_pdx

[snow sleet]

yeah, once the universe of discourse has been established/agreed upon you can go straight into the notation you're using

[unreal stump]

ic

[snow sleet]

it really depends on how picky your professor/teacher is

and whether or not you should state where x `lives'

[olive wraith]

I just start learning discrete mathematics

[snow sleet]

noice

[olive wraith]

but I have not very good math foundation but I learn a lots of math from khan academy so some time I face difficulty in understanding but the book I follow is nice it tells things in detail discrete mathematics and it's applications by kenneth

[snow sleet]

ah gotcha; well whenever you have questions or difficulty in understanding some math concept in discrete, feel free to ask here.

[olive wraith]

thanks

[snow sleet]

you're welcome!

[livid drum]

@unreal stump it is first order. In other contexts, membership could be viewed as part of the second order framework— but quantifying over elements in a set, or elements which satisfy a property, is still first order quantification.
(Quantifying over properties would be second order quantification.)

[south jacinth]

I'm trying to teach myself discrete math but the book doesn't have the answer for this question

I think the answer is 2 but I'm not sure

[narrow trench]

write them all out

[jade birch]

Well, T_1 would be {1, 1} no?

[surreal surge]

hey

i invetned a new base today

invented*

it doesn't even use numbers but it can permute all of the integers

anyone interested?

i call it base-x-unknown-base

[jade birch]

u wont

[surreal surge]

0 1 2 3 4 10 11 12 13 20 21 22 30 31 40 5 1,0 1,1, 1,2 1,3, 1,4, 1,10, 1,11 1,12 1,13 1,20 1,21 1,22 1,30 1,31, 1,40 1,5 2,0 2,1 2,2 2,3 2,4 2,10 2,11, 2,12, 2,13 2,20 2,21 2,22 2,30 2,31 2,40 2,5 3,1, 3,2 3,3 3,4 3,10 3,11 ,312 3,13 3,20 3,21 3,22 3,30 3,31 3,40 3,5 4,0 4,1 4,2 4,3 4,4 4,10 4,11 4,12 4,13 4,20 4,21 4,22 4,30 4,31 4,40 4,5 10,0 10,1 10,2, 10,3, 10,4 10,10 10,11 10,12 10,13 10,14 10,20 10,21 10,22 10,30 10,31 10,40, 10,5 11,0 11,1 11,2 11,3 11,4 11,10, 11,11 11,12 11,13 11,20 11,21 11,22, 11,30 11,31 ...

[errant bear]

wat

[distant pollen]

can someone explain this to me?

[vestal cradle]

Do i = 6 and i = -3 for 2i-3 and see what you notice about the results

for i=6, 2(6)-3 = 9, for i=-3, 2(-3)-3 = -9, so they sum to zero. If you then were to exclude those two from the sum, you'd end up with the same result.

[surreal surge]

0
1
2
3
4

0 1 2 3 4

1,0 1,1 1,2 1,3
2,0 2,1 2,2
3,0 3,1
4,0

1,0 1,1 1,2 1,3 2,0 2,1 2,2 3,0 3,1 4,0

what comes next?

[vestal cradle]

69

[surreal surge]

does this look right:

0
1
2
3
4

0 1 2 3 4

1,0 1,1 1,2 1,3
2,0 2,1 2,2
3,0 3,1
4,0

1,0 1,1 1,2 1,3 2,0 2,1 2,2 3,0 3,1 4,0

1,0,0 1,0,1 1,0,2 1,0,3 1,0,4 1,1,0 1,1,1 1,1,2 1,1,3 1,2,0 1,2,1 1,2,2 1,3,0 1,3,1 1,4,0
2,0,0 2,0,1 2,0,2 2,0,3 2,0,4 2,1,0 2,1,1 2,1,2 2,1,3 2,2,0 2,2,1 2,2,2 2,3,0 2,3,1 2,4,0
3,0,0 3,3,1 3,0,2 3,0,3 3,0,4 3,1,0 3,1,1 3,1,2 3,1,3 3,2,0 3,2,1 3,2,2 3,3,0 3,3,1 3,4,1
4,0,0 4,0,1 4,0,2 4,0,3 4,0,4 4,1,0 4,1,1 4,1,2 4,1,3 4,2,0 4,2,1 4,2,2 4,3,0 4,3,1 4,4,0

1,0,0 1,0,1 1,0,2 1,0,3 1,0,4 1,1,0 1,1,1 1,1,2 1,1,3 1,2,0 1,2,1 1,2,2 1,3,0 1,3,1 1,4,0 2,0,0 2,0,1 2,0,2 2,0,3 2,0,4 2,1,0 2,1,1 2,1,2 2,1,3 2,2,0 2,2,1 2,2,2 2,3,0 2,3,1 2,4,0 3,0,0 3,3,1 3,0,2 3,0,3 3,0,4 3,1,0 3,1,1 3,1,2 3,1,3 3,2,0 3,2,1 3,2,2 3,3,0 3,3,1 3,4,1 4,0,0 4,0,1 4,0,2 4,0,3 4,0,4 4,1,0 4,1,1 4,1,2 4,1,3 4,2,0 4,2,1 4,2,2 4,3,0 4,3,1 4,4,0

https://pastebin.com/9hALzybr

[jade birch]

https://tenor.com/view/impress-based-american-psycho-very-based-impressive-very-based-gif-21665669

[distant pollen]

i see, so if the sums of each equal up to 0, its equivalent to the other?

[vestal cradle]

That's not quite what I was saying

summing from -2 to 5 is the same as summing from -3 to 6 in this case since the sum of i=-3 and i=6 is 0.

[livid drum]

The tree constructed from k other trees, need not be given a name.
Once built, it can be one of trees used as part of the formation of a new one.

Any tree can be formed via those rules of formation. (Try to find a counter example.)

you may have an incorrect perception of the tree simply based upon its name?
For example, a tree called T3 need not have three primary branches.

Idk but a name is a name. It doesn’t assert any status or Hierarchal superiority.
||unless it’s got a yellow tag...which is why this discord is silly...||

[warped pecan]

Can someone pls help me with this because I don’t understand how to even start

I kind of know how RSA encryption works but have no idea how to approach this

[pale sorrel]

hmm, well, do you know how to encrypt the letter 'S'?

look back at the RSA encryption, and try working out how to encrypt the number 19, for example, when the public key is (n,e) = (1963, 49). do you have problems with this?

[warped pecan]

@pale sorrel yes but I don’t know how to deal with the modulus of such a big number

[pale sorrel]

oh, i see... are you allowed to use a calculator?

you can break it up: for m^49 mod 1963, first compute m^7 mod 1963. then can you see how i can get m^49 from m^7 (mod 1963)?

[warped pecan]

I did this?

But then I tried encrypting N and got the same value and I’m pretty sure I shouldn’t have?

[pale sorrel]

for S, that looks good, i computed it myself and got the same value.

you should consider the approach i mentioned previously though, it is a lot less work, and you are less likely to make computational mistakes

here it is in action: first compute 19^7, reduce it modulo 1963. thats 59.

then take 59^7, reduce it modulo 1963 to get 461, the same as your computation of 19^49 above

with this approach, you can try to compute N again, and see if you get the same result as your first attempt

[warped pecan]

Ohhh I see what you did

I’m going to try to decrypt using that

Would that still work?

Or no?

[pale sorrel]

yeah, you can use the same trick depending on what the secret key 'd' is. i dont know what it is here though

[warped pecan]

Is this doable

How do you recommend approaching this?

[surreal surge]

https://pastebin.com/VMqRZ7sP

https://pastebin.com/CScUg3x0

[pale sorrel]

oh he leaked it! yes, it is quite a large exponent, have you heard of the square and multiply method?

that pastebin over there is probably suggesting the use of that method

[warped pecan]

Yeah I thinks but did not really understand it

[pale sorrel]

ah, i see, well ill type out a small example for you, and i hope it helps you. if not, there is the rest of the internet

say you want to compute the modest but somewhat difficult example of 2^70, modulo n = 101.

first, reduce 2^2 mod 101. make a note of it, somewhere.

now we want to compute 2^4. to do this, we may take our earlier computation of 2^2 mod 101, and square that. again, keep the value around.

for 2^8. we take our result of 2^4 mod 101, and square that.

we do this until we have 2^2, 2^4, all the way up to 2^64

by multiplying some (and definitely not all) of those values together, we can get 2^70 modulo 101

[warped pecan]

Also, sorry to interrupt but how is it that before you could do 59^7?

[warped pecan]

Okay this makes sense!

Thank you so much!

[pale sorrel]

most practically, i just use a calculator. if i was on an exam, i would do something like 59^3 or something.

take 59^3 mod 1963, square that, reduce it mod 1963, and multiply the result by 59.

you effectively compute (59^3)(59^3)(59) to get 59^7

[warped pecan]

Oh but like I know that you are squaring the mod of 19^7

Ahhhh I see

But why do you want 59^7

[pale sorrel]

because in the beginning, we wanted to compute 19^49

as an intermediate step, we computed 19^7, and then reduced it modulo 1963. once we had that, we took the result to the power of 7, and reduced it modulo 1963 once more

effectively, we end up computing (19^7)^7, which is 19^49

please let me know if i am not clear on any point

i do not explain things too often, so that is my fear

[warped pecan]

Why are we allowed to replace 19^7 with its modulo?

[errant bear]

merositt is a big fan of unknown bases

[pale sorrel]

hey, sorry, i missed your comment, but im quite done with math for the night. in any case, you may have seen a result that went something like this: if a = b modulo n, then a^k = b^k modulo n, for any positive integer k. it is for this reason that we can replace 19^7 with its reduction modulo 1963. to be explicit, take 'a' in the previous theorem to by 19^7, and then 'b' to be its modulo reduction.

in general, when you are evaluating an expression modulo n, you can replace any parts of that expression with its modulo reduction to make computations easier

[tranquil flint]

If we have a connected planar graph such that each face is bounded by a different # of edges, and there are 35 vertices

how do I prove it has at most 11 = f

I have some progress

like i said say theres a face thats contained by 3 cycle, then another contained by 4 cycle and so on

if i can show the largest cycle to exist is size 8 i think im good

but idg how i would show that

Cuz if 8cycle is largest cycle (?) (idk if this is true)

then 2m <= X <= 8f where X is sum of # of edges on the boundary of all faces

and then i can use n - m + f = 2

[snow sleet]

Graph theory isn't my forte @tranquil flint , but I'd suggest a proof by contradiction

[tranquil flint]

the hint says

to take the inequality

2m >= 3f and "improve it" based on restrictions

and i guess itd be "at most" instead of "at least"

[snow sleet]

"improve it"... so vague lol. what a hint

[tranquil flint]

Well ik what it needs to be

i just need to explain

how to get that

its 2m<=8f

then im done

just not sure how to understand/prove/explain the 8f part

[snow sleet]

hmmm

<@&286206848099549185> anyone know some graph theory?

[tranquil flint]

its alright if no one can, ill ponder it overnight but help is much appreciated

any insight

[snow sleet]

so let me get this straight...you wanna show the the number of faces is no more than 11

[vital dew]

logician_pdx

[tranquil flint]

Ohh

that works 😮

Did you use fact that

If we have a connected planar graph such that each face is bounded by a different # of edges

(the graph in this question)

[snow sleet]

no I didn't use that fact...I just thought might be a valid approach since the number of vertices n is fixed, 2 is fixed, and we have (m+2)-n=f. So m is really the thing we need to bound.

[tranquil flint]

hm i see

i will ponder

[snow sleet]

same here!

[tranquil flint]

thank you though, any other insights greatly appreciated

[snow sleet]

you're welcome!

[tranquil flint]

i hate graph theory so much

☠️

[snow sleet]

lmao same!! I took it (and passed) and it was one of those classes that couldn't end soon enough!

[cerulean wind]

sry to butt in but same

thought it was just meh

[tranquil flint]

it seems very useful tho

as an applied branch

but fuck

[snow sleet]

I'll let you know if I have any other potentially helpful insights. lmk if you come up with something clever. I'm interested in seeing a dope proof for this

[tranquil flint]

i hate it so much

[snow sleet]

Yeah I like it's cousin though, combinatorics

[cerulean wind]

meh. discrete math is hard fr

just counting in general

[snow sleet]

For instance, to count the number of edges on the complete graph K_n, I gave a combinatorial proof that that is the same as counting the number of hanshakes that occur in a room filled with exactly n people if each person in the room shakes hands with everyone else.

[cerulean wind]

just spam induction

[remote cosmos]

lmao

[cerulean wind]

i should probably get more comfortable with it. for some reason analytic/algebraic proofs feel so much more natural

[tranquil flint]

ive gotten good at combinatorial proofs

i always use

teams and captains

as analogy

and it just works

somehow

i just write what each term is in the real world

in terms of teams, captains

maybe theres 3 teams

2 captains per team

etc

weird caveats

[snow sleet]

dope

[snow sleet]

correction, the order of the difference here needs to swap @tranquil flint

[subtle ermine]

I'm stuck on how I would be able to make a compound proposition that is only true if at least one of p1, p2,p3,.......pn is true

The previous problem had this which is only true if at most only one proposition is true

I'm not entirely sure where to start but I've been experimenting with this

[snow sleet]

@subtle ermine I have an idea

[vital dew]

logician_pdx

[subtle ermine]

Hmm. If all are false then the first statement would be true. But the second statement would be wrong.

If you have some true in the first statement it would be ALL false, and then the latter half can be anything

and it would be true

is that right?

[snow sleet]

if at least one of the atomic propositions is true, this statement (as a whole) is vacuously true. If all are false, then the whole statement is false.

[subtle ermine]

Hmm

I see

[snow sleet]

this is what you wanted

a conditional proposition is a compound proposition

[subtle ermine]

Just wondering what's the best way to appraoch problems like this. I just started discrete math so it feels very different from what i was doing b4, aka calculus

[snow sleet]

well so I like to think of what makes the statement true and what makes it false.

rather than trying to think of the truth table with 2^n rows ot T's and F's

do you see how my statement I've brought here is exactly what you want?

[subtle ermine]

Yes I do

Hm wait if I think about it, conditional is defined to where q can only be true if p is satisfied
So you found a way to where p was true if all were false and then we just have to make it so that q is false

then any other case is just considered true because in any other case p would be false instantly leading

I see!

[snow sleet]

p->q is true precisely when p is false or q is true or both

this is why "p->q" is logically equivalent to "(not p) or q" that's an inclusive or there

[subtle ermine]

Ah I understand

I'll try doing more practice, but now I see that I should be more flexible, I was trying to do it with just And/Or, but conditional is very useful too. Same with the other compounds connectives probably

[snow sleet]

yes, it's less about being more flexible and more about being more aware of all the tools you have at your disposal (conditional statements are just one of the many tools)

for your future reference, this is actually a proofs/logic question, so it'd be more appropriate to ask it in the "proofs-and-logic" channel, but luckily I saw this here and was able to answer

[subtle ermine]

Ah alr, thanks!

[snow sleet]

you're welcome!

[subtle ermine]

Oh yeah mb
This is in my discrete math textbook so I just posted here but I'll be careful next time

[snow sleet]

yeah I mean it's not incorrect to post it here...I covered propositional and predicate logic in my discrete class...it just fits the proofs-logic channel a bit better tho simply due to the nature of your question

@subtle ermine and just another slight correction/clarification, 'p implies q', in English, (especially in proofs) is taken to mean "if p is true, then q is true." (if p is false, then that's besides the point and we have nothing to prove...hence vacuously true)

I think you'll find that you'll get better at this logic stuff as you progress with proofs

[surreal surge]

https://pastebin.com/PrtZ3ULL

[cerulean wind]

dude what r these

[obtuse lance]

<@&268886789983436800> keeps spamming this across multiple channels

[young patio]

👍

[gray axle]

hey guys, got a slideshow that im struggling to understand -- im reading this slideshow in order to understand a concept -- the concept of the abelian group U(1) specifically in astrophysics but any level of understanding in any field would be much appreciated. this is the slideshow :) https://hepwww.pp.rl.ac.uk/users/haywood/Group_Theory_Lectures/Lecture_2.pdf

[livid drum]

@gray axle
This is the definition of a group.

A group is a set of elements G together with some operation between them •.

For any two elements x,y of G, you can form the product x • y.
This is why • is considered a binary operation on G.
You can also expect x • y to itself be an element of G.
This is why • is considered closed.
We demand that • is associative.

There is a special element in G, call it e, where for every element x in G,
x • e = x.
This is why e is considered the identity. In this particular form it is considered the right sided identity.
(Once we finish these definitions of a group, you can show that a right sided identity is also a left sided identity.)

Finally for any x in G, there exists an element y such that,
x • y = e.
This is why y is called the inverse of x.
In this particular form y is considered the right inverse of x, and x is considered the left inverse of y.
(You can show that a right sided inverse is also a left sided inverse.)

[livid drum]

@gray axle
So this is the usual mathematical outlook.
But I would really like to share something else with you.
I would like to answer the question "Why these axioms for defining a group?"

Perhaps all of mathematics is born, in one way or another, as a contemplation of space or of numbers.
This concept of a group is born from fantasies of "space".

@gray axle
Imagine we live in some weird space.
We make a set X consisting of all the points we can occupy.
Now consider a particular subset G of functions f : X --> X.
These correspond to "movements" (or affine translations) we can make in this space.
For example, say "up" were an element of G. That would mean at any point in the space,
we can perform the "up" motion to end up at another location in space.

Now what are the basic postulates we might have for "motions" in this space?
Here are our basic demands.

1. The identity function is an element of G.
   Intuitively we should have the capacity to remain absolutely still, to choose not to move, to be stationary.

2. If f is an element of G and g an element of G, then their composition is an element of G.
   If we have the capacity to translate by "up" say, and also move by "right", then surely we have the capacity to first go "up" and then go "right" and that entire movement can be regarded as one "movement" we can make in space.

3. For every movement f in G, their must be a movement g in G such that f composed with g is the identity.
   If we can move "up" then surely we have the ability to undo that movement, of progressing backwards. Surely we should be able to move "down".
   So if f is in G, it must be invertible and its inverse must also be in G.

4. For every two points x, y in our space X, their exists a movement f in G such that f(x)=y.
   Intuitively this represents "completion". That no point in space is inaccessible.
   Our space is "pure" and "empty", free of all obstacles and all barricades which otherwise impede movement.
   If we start at x, we can move by a particular movement to arrive at y.

---

@gray axle
5. For every x in X there is only a single movement f in G such that f(x)=x.
This is "homogeneity of space". Whatever keeps us still at x, when "imitated" at other points in space, say y,
should also keep us still. In that way there can only be one movement which keeps us stationary-- the identity.

[livid drum]

@gray axle

That's it with our demands.
In fact not only is G a group ( over the natural operation of composition),
but there is a very deep natural function between X and maps X-->G.

Consider the map psi : X --> (X--> G), defined as:
psi (x1) (x2) = "the necessarily unique map in G which connects x1 to x2".

In fact for any x1 in X, psi(x1) is a natural bijection from X --> G.
This means there are as many points in space X as movements in G.
For every song there is a singer, dance there is a dancer.
For every action there is an actor to mediate its effect.

Any group structure on G, can be inhereited by X via this isomorphism from X--> G .
The iso is not canonical-- there are several bijections to choose from, one for each point in space,
This degree of "free choice" corresponds to selecting the "identity" element of X.

In fact we can also go the other way around. Given a group X, we can form a group G which satisfies our above demands, and which is isomorphic to X.
This can be called the dual group of X.

This is the end of the story, and how i view groups. sorry and thank you.

[west silo]

The given condition is satisfied for any function iff for any n+1 points at least it is 1. So we choose n+1 points and map them to 1 and we have to choices for remaining points. So the total number is (2n choose n+1 ) x 2^(n-1)

am i right?

[vast narwhal]

I don't think these two steps are independent of each other.

[obtuse lance]

I counted them differently, by symmetry the ones > will be the same as < so I just count the number of ways to make functions and subtract by the number of ways to split into two equal groups then divide by 2

$\frac{2^{2n}-\binom{2n}{n}}{2}$

[vital dew]

Merosity

[vast narwhal]

what about balanced functions though...

[obtuse lance]

that's what the subtraction removes

[vast narwhal]

oh, right, that's what you said

[obtuse lance]

there are 2n choose n balanced functions

yup

I was kinda terse

[loud copper]

[vast narwhal]

at first I thought you meant subtracting the <0 sums

[obtuse lance]

yeah I could have said that more clearly, but I was trying to say it in one line lol

[loud copper]

and goddamn, was it beautiful 😌

[vast narwhal]

it's pretty clear. the symmetry route prevails again

[obtuse lance]

can we generalize the problem?

I'm thinking $h: {1,2,\dots,pn} \to {\zeta, \zeta^2, \dots, \zeta^p}$ with here $\zeta^p=1$ is a primitive pth root of unity might work

[vital dew]

Merosity

[obtuse lance]

if it's not prime, counting will be harder cause there are nontrivial ways to make 0 by adding

I think this will still keep the symmetry argument through it

$\frac{p^{pn}-\frac{(pn)!}{n!^p}}{p}$ I think

[vital dew]

Merosity

[obtuse lance]

erm wait what am I talking about

0 doesn't make sense

[vast narwhal]

re>0 then

or im>0

[obtuse lance]

maybe it can make sense as being restricted to between pizza slice sectors of angle 2pi/p in the complex plane or something

maybe 2pi/p + pi/p multiples to be precise, like visually is how I'm thinking it, writing it in symbols looks less obvious

[vast narwhal]

maybe put them on the equator of a qubit

[obtuse lance]

haha

well ok in p=2 case we have basically a line separating them

like if I imagine rotating from 1 to -1, halfway through I have a line I draw in the complex plane

[vast narwhal]

the imaginary line

[obtuse lance]

if I now separate into 3 parts I have to cut the complex plane into 3rds

but rotated by a sixth

I don't think it actually matters tbh I might be getting overly technical about it, algebraically the functions we get are gonna be related by multiplication by zeta^k for some k

so where we decide to say these are is not really important except for how we define the problem ourselves, since this partitions no matter what

I just wanted it to coincide with the p=2 case of the original problem

between the dotted line divisors are where the sums are landing is what I'm saying haha

left is p=2 case, right is p=3 case

[vast narwhal]

So sums evaluated could be in 6 different places in the p=3 case, indicated by the arrows and the dotted lines

is that right?

[obtuse lance]

no just 3 places

the p=2 case we only have the positive and negative cases

even though it looks like it's cut into 4 regions

[vast narwhal]

oh, the dotted lines are the boundaries?

[obtuse lance]

yeah

it's so that 1+1+1 is positive and -1+-1+-1 is negative

and these are in the middle of the regions, so it's unambiguous

much like 1+1+1 is in the first region, zeta+zeta+zeta is in the middle of the second region, etc

[vast narwhal]

There's a lattice then

[obtuse lance]

these are just rays that go off to infinity

there's no lattice as far as our problem is concerned

for every h we have zeta^k*h for k in {0,...,p-1} is really all that matters

and this partitions them

[vast narwhal]

yes it partitions the powers of zeta

[obtuse lance]

p=2 case that was us just saying h and -h were the 2 cases, aside from the ones that are perfectly balanced

well, here's a desmos of it basically just made lol https://www.desmos.com/calculator/nvd4jjhuxo

[vast narwhal]

Maybe get it to plot all of the possible sums in question?

[obtuse lance]

well not super interested in that unless you are unsure about something

I'd rather think about if this is possible to generalize to non prime

like for 4 regions, we can make 0 in unbalanced ways so kind of curious how to get that to work out

[vast narwhal]

what do you mean?

[obtuse lance]

to make 0 with 2 or 3 you need exactly the same number of each kind of root

1+(-1) or 1+zeta+zeta^2 etc

for 4 you could have 1+(-1)+i+i+(-i)+(-i)

so the solution will be something like

$$\frac{4^{4n}-\sum_{i+j=n}\binom{2i}{i}\binom{2j}{j}}{4}$$

[vital dew]

Merosity

[vast narwhal]

oh, so it could be "balanced wrt to real but not imaginary"

[obtuse lance]

yeah, every composite case will have this sort of issue I think

so now it's like, some kind of inclusion/exclusion on the divisors so probably we will need the mobius function to count these correctly lol

Maybe I should make it concrete and change the regions slightly so it's simpler to work with algebraically, we can define $h: {1,2,...,kn} \to {1, \zeta, ..., \zeta^{k-1}}$ and the sum $S(h) = \sum_{j=1}^{kn} h(j)$ which is generically complex and so we can then ask to count the number of functions $h$ such that $$S_h \ne 0$$ and $$0 \le\arg(S_h)< \frac{2\pi}{k}$$

[vital dew]

Merosity

[obtuse lance]

this coincides with the original problem when k=2 (if it doesn't tell me cause I messed up lol)

[vast narwhal]

yes this looks like what you've been saying so far

so strategy is to count where S_h = 0, then divide the remaining regions by symmetry?

[obtuse lance]

yup

I'm not even sure how to do it when k=6 or k=12 haha

ok k=6 I think makes sense, just individual ways you would do it with 2 and 3 cases added up

maybe relatively prime numbers can always be split up and worked independently

[vast narwhal]

so prime powers would be the harder case?

[obtuse lance]

I think so, I'm trying to work out a few cases since I need to see more details

looks like when you have k=pq for two different primes, then the number of ways will be $$\frac{(pq)^{pqn}-\sum_{pi+qj=pqn} \frac{(pi)!}{i!^p} \frac{(qj)!}{j!^q}}{pq}$$

[vital dew]

Merosity

[obtuse lance]

I should probably write a program to test it to make sure, I'm not thinking too hard and could easily be wrong lol

maybe being relatively prime doesn't matter considering this is basically the same way I split it apart for when p=q=2

[livid drum]

@west silo
As Apopheniac says that formula double counts.
Eg. let n=3.
In one count, we have:
The choice where {1, 3, 4, 5} ↦ +1 and separately 2 ↦ +1, 6 ↦ -1.
But in another count, we have the same function:
The choice where {1, 2, 3, 5} ↦ +1 and separately 4 ↦ +1, 6 ↦ -1.

Instead choose j inputs to map to 1, (and send the rest to -1).
Sum this count from j=n+1 to 2n.
This is the total number of functions

[west silo]

ohhh hmm I get it now

[west silo]

this is a great way

[obtuse lance]

thanks

[split haven]

I proved for a sequence an+1=f(an), a0=2 that

1. if a0=2 then an>φ,
2. an is monotonically decreasing and
3. if the limit to infinity exists then its equal to φ
   is do the first 2 statements guarantee the existence of the limit?

[last timber]

@split haven please use proper notation

anyway

[vital dew]

Commander Vimes

[split haven]

yep

[last timber]

then yes, the limit is guaranteed to exist

[split haven]

thank you

[last timber]

(but not guaranteed to be ф)

[split haven]

I will use proper notation next time

It's guaranteed by the third statement right?

I proved that if it exists then its φ

[vital dew]

Commander Vimes

[split haven]

I'm kinda proud I came up with that by myself without knowing if its provable or not and without having studied sequence

sorry for patting myself in the back

[last timber]

you basically used monotone sequence theorem in 1 and 2

it is good that you came to it by urself

||though intuitively ig this theorem is clear||

[split haven]

Yeah but many "theorems" which seem intuitively right are not actually theorems because there are weird cases for which they are not true

this came out from a circuits exercise , compute the equivalent resistance of this:

and I kinda over engineered the answer

[warped pecan]

Can someone please explain to me how to find the number of lattice paths that don’t cross y=x?

From 0,0 to n,n

I have absolutely no idea how to do this

[weary tiger]

anyone able to help me with this? I wrote the negation out and got suppose x is irrational... but idk what manipulation is needed for this