discrete-math

[stray reef]

permutations are functions from {1,2,3,4,5,6} to itself

you want to count those functions f: A_6 -> A_6 such that f(2) is even and f(4) is even and f(6) is even

[tribal wasp]

Sorry about that

I see, thanks.

[plain hatch]

where r_i is the number of ways of placing i-non-attacking rooks on the the forbidden positions.

i dont get this process of counting r_i

I understand to write out all the possible i-tuple of rows but how are they counting the number of "ways"?

I understand the formula for the number of ways to place six non-attacking rooks I just don't understand how they are counting the r_i

[vestal bronze]

i don't understand what it is solving, what's r1

[plain hatch]

r_i is the number of ways of placing i-non-attacking rooks on the the forbidden positions.

I think I got how it was counting now I was just counting the rows bottom up instead of top down

while this way of counting works some students counted 36 for r_2 from here performing 7+6+7+6+3+2+3+2 = 36 or 7+7+6+6+3+3+2+2=35 which im not sure what they did

[plain hatch]

since the method from here would result in
rows: 1,2 1,3 1,4 1,5 2,3 2,4 2,5 3,4 3,5 4,5
ways: 2 4 4 4 4 4 4 2 4 4

I am curious on how they counted it since I am meant to be grading them lmao

I made a help thread with my specific question: #1217306875880804453 message

[muted moth]

is the path 1, 2, 3, 1, 4, 5, 1 a circuit or a cycle?

[agile magnet]

What's the difference between circuit and cycle?

[blissful wind]

Hi, I hope this is the right channel
I have a quick notation question:
if I have a set of numbers A = {3, 1, 14, 6}
how would I declare an increasing sequence with one term for each element of A that would look like this:
U1 = 1, U2 = 3, U3 = 6, U4 = 14

[agile magnet]

This seems fine for me. Each Ui is an element from A, as the i's increase the Ui's increase

[vital dew]

Spamakin🎷

[blissful wind]

what i'm asking is more a general notation for any set A, make a sequence of its elements but ordered in increasing order

maybe someting like this?
(a | a element of A, an <= a(n-1))

[vital dew]

Spamakin🎷

[blissful wind]

shouldn't it be round parentheses ? (because sets dont have on order)

[agile magnet]

Eh nah

Actually tbh the way you see it more is ${a_i}_{i \in \mathbb{N}}$

[vital dew]

Spamakin🎷

[agile magnet]

And words around saying that it's an increasing sequence, elements come from A etc

Words are useful

I mean as long as it's clear it doesn't matter that much

[blissful wind]

also this allows the serie to have duplicates of elements of A, dosen't it?

[agile magnet]

I guess yea

TBH this is why I'm saying just write words

[blissful wind]

ok, thanks a lot

[errant trail]

Can you guys help me check if this is right

[nimble raptor]

confused by this problem. how can I write a proof for it?

[compact yacht]

Does $A \approx B$ mean that there is a bijection from $A$ to $B$? @nimble raptor

[vital dew]

Leu

[nimble raptor]

yes chef

[crimson zenith]

so in class my prof said that the modulo function isn't onto but I wrote this proof - is it valid?

[stray reef]

sure, but you could have also put a = c and b = (anything bigger than c), no?

so a tiny bit overcomplicated.

[stray reef]

do you remember in what context that was said?

[crimson zenith]

fair

I don't remember the exact context in which it was said but she gave an example where if you have something mod 4 you can't get anything over 3

which makes sense but I don't understand why we're restricting it to 4 when dealing with onto

[stray reef]

so she's saying that for a fixed m, the function x ↦ x % m has range {0, 1, ..., m-1}

i mean... that tracks? but we'd need to all be on the same page regarding which function we're looking at the surjectivity of

[crimson zenith]

that makes sense it just seems like an odd definition

but yeah I see what you're saying

[young zenith]

Do ya'll know how I could approach question 14?

[compact yacht]

You can use simpler bijections, for example, the identity map $f: \mathbb{Z} \to \mathbb{Z}$ is a bijection and there is a bijection $g_1: \mathbb{Z} \to \mathbb{N}^2$ and a bijection $g_2: \mathbb{N} \to \mathbb{Z}$, therefore there is a bijection $g = g_1 \circ g_2: \mathbb{N} \to \mathbb{N}^2$. You can use those those construct a bijection from $\mathbb{Z}\times \mathbb{N}$ to $\mathbb{Z}\times\mathbb{Z}^2 = \mathbb{Z}^3$

[vital dew]

Leu

[mild root]

Question 6 is a tough one

thoughts on my work so far? am i on the right path

[supple talon]

yeah this generally seems right

[worldly slate]

Question: In 4c, what's stopping me from saying either x or y is 0 to make the expression be false?
Context: based on my professor's answers 4c is true.

[viral crown]

it's just saying there exists an x,y s.t it's true

"There exists an x and there exists a y such that [xy=1] where x,y in R"

[rare raptor]

I have a question regarding discrete math. I have to take it next semester and was wondering if you guys found it more/less difficult than cal 1 and/or cal 2?

[twilit sundial]

discrete math deals with very different subject matter than the standard calculus sequence

[viral crown]

depends

whats the syllabus

[twilit sundial]

it may be that you find it easier or harder depending on your background

[viral crown]

^

calc is also primarily an algebra check

so

discrete math is very different

what's ur syllabus

[calm chasm]

This felt pretty straightforward. Did I miss anything ?

[compact yacht]

nope

[calm chasm]

Ty

[worldly arrow]

hi, can you tell me, what is discrete mathematics?

[brave rock]

Discrete mathematics is a common title for a course where students first encounter important concepts such as sets, functions, and relations.

[calm chasm]

For my school, it's our proofs class.

[static briar]

is there a quick way to do this wsithout using havel-hakimi

[stray reef]

why is havel-hakimi disallowed?

[static briar]

idk he just said

[stray reef]

who's "he"?

[static briar]

prof

theres no due date for this btw

just a practise type of ting

[stray reef]

so your professor EXPLICITLY forbade the use of havel-hakimi, punishable by zeroing the entire assignment. is that correct?

[static briar]

theres no mark for it

but its not allowed and for tests and wat not we would not be allowed to use it

[stray reef]

i would try to construct the graph "by hand"

start with the highest degree node

see what neighbors it could have

perhaps arrive at a contradiction of some kind

[static briar]

mm ok

[lapis mulch]

what does "maximal number of neighbors" mean here?

[wet granite]

It looks an good question please look. I tried to put random numbers

[cerulean radish]

Be clear about what you need help with

If you have an answer to the question but are not sure about it, post it here (preferably with workings if you have any)

[wet granite]

Ohh. I don't have answer of it

Let me delete this

[cerulean radish]

Do not delete

[wet granite]

Ahhh

[cerulean radish]

Repost it and we can work on it

[cerulean radish]

Right

Can you recall what reflexivity means?

[wet granite]

Yes. When relation holds for itself

[cerulean radish]

Right, and so reflexivity in this case would mean that xRx holds for every integer x, i.e., x^2 and x^2 are always not coprime

Equivalently it means the same as gcd(x^2, x^2) ≠ 1 for all integers x

Can you simplify gcd(x^2, x^2)?

[wet granite]

x^2

Gcd

[cerulean radish]

Yeah

So reflexivity of R says that x^2 is never equal to 1 when x is an integer

Is that true?

[wet granite]

I didn't understand properly

X^2 never equal?

(0 and 1)

Can create contradiction

[cerulean radish]

Hopefully you meant x = -1 and x = 1

[cerulean radish]

Right

[cerulean radish]

These two values of x indeed contradict the statement xRx

Means R is not reflexive

[wet granite]

Gcd of (-1^2,1^2)=1

[wet granite]

Let's check transitive?

[mighty nest]

do we dicuss graph theory stuff in discrete math too?

[cerulean radish]

Sorry, I was away

What do you think about transitivity?

[wet granite]

Nevermind i have got example

[cerulean radish]

Finite graphs, sure

[wet granite]

It fails at transitive

[cerulean radish]

Yeah nice

[wet granite]

I only got it by random example

[cerulean radish]

So the answer is "none of the above"

[wet granite]

4,36,9

[wet granite]

It should be A and C

[stray reef]

yes, graph theory is fine here

did you have a question?

[cerulean radish]

Oh sorry yeah it's asking about the properties which are not satisfied

Symmetry is satisfied, yes

[wet granite]

Yes absolutely

mathemtically we can prove transitive?

[cerulean radish]

You already disproved transitivity

[wet granite]

Gcd(a^2,b^2) =\1
Gcd(b^2,c^2)=\1

Then gcd of (a^2,c^2)=1

[cerulean radish]

In the case of a = 2, b = 6 and c = 3, a counterexample to transitivity is produced, yes

[mighty nest]

this is from jeffEs algorithms

[cerulean radish]

So transitivity is not satisfied

[mighty nest]

this is my attempt at it

i wanted to know if this works

[wet granite]

No that's incorrect because 2,3,6 is not square of any

[cerulean radish]

You need to square those integers

[wet granite]

Yes. That is the same example i took

[wet granite]

Here

Thanks for working out/helping me

[agile magnet]

I don't get what's going on here

it seems like you're doing BFS / DFS? It's not clear what your graph structure is

Here's what you should do

construct a new graph based on the input graph G (so define vertices and edges)

construct this graph so that you can just answer the question using some very basic black box algorithms (BFS / DFS / Whatever-First-Search, some other shortest path algo, whatever you think is appropriate and fastest)

and then just argue why your graph construct + result from the black box algorithm answers the question

no need to write pseudocode, blackbox algorithms are standard

why reinvent the wheel, if that makes sense

(fun fact I took algos with Jeff E lol)

lemme know if what I said makes sense

[quaint nebula]

Hello, I have seen months ago a YouTube video about some topics of research in combinatorics. The video mentioned the yet open problem of the game n in a row that has been solved for most values of n but not for (in my memory, might be wrong) 6-7. Did someone see this video?

[cursive nymph]

is it guaranteed that the relation ~ is not empty?

i mean, I can show it's a ZFC set

I'm just not sure how to show ~ != ø

[compact yacht]

If X is not empty we have the nonempty set ${(x,x):x\in X}\subset R$ for every equivalence relation R

[vital dew]

Leu

[compact yacht]

And, of course, for every relation R, X×X is an equivalence relation on X that contains R

Actually If X is empty as well the empty set is an equivalence relation on X

[cursive nymph]

gotcha, thanks!

[cursive nymph]

guys, how do I show
$$
M \backslash \bigcap_{\lambda \in I} C_\lambda = \bigcup_{\lambda \in I} \left(M \backslash C_{\lambda} \right)
$$?

Like, I can show it if the index set $I$ is finite. But what do I do in case it isn't?

[vital dew]

Sweet Tea 🧋

[fossil mural]

...i don't get how you do that for just a finite index set? unless you did like, induction

[cursive nymph]

if it is finite, then take any
$$
x \in M \backslash \bigcap{\lambda \in I} C\lambda = M \backslash \left( C_1 \cap \ldots \cap C_n \right) \iff x \in M \text { and not } (x \in C_1 \text{ and } \ldots \text{ and } x \in C_n)
$$

and then apply de morgans law to prove it

[vital dew]

Sweet Tea 🧋

[cursive nymph]

ohh

[fossil mural]

oh yeah i guess that makes sense

[cursive nymph]

[fossil mural]

well uh, you can do the same thing with infinite I too, basically

the idea is that $\forall$ looks like infinite conjunction and $\exists$ looks like infinite disjunction

[vital dew]

bee [it/its]

[fossil mural]

so you have the analog of de morgan, $\neg\forall x \varphi$ and $\exists x\neg\varphi$ are the same

[vital dew]

bee [it/its]

[fossil mural]

(and also $\forall x\neg \varphi$ is the same as $\neg\exists x\varphi$)

[cursive nymph]

hmmmm

[vital dew]

bee [it/its]

[cursive nymph]

but what's phi here then?

the whole
$$
x \in M \backslash \bigcap_{\lambda \in I} C_\lambda
$$
?

[fossil mural]

$\neg\forall\lambda\in I x \in C_\lambda$ is the same as $\exists\lambda\in I\neg x \in C_\lambda$

[vital dew]

bee [it/its]

Sweet Tea 🧋

[cursive nymph]

(big i) x?

[fossil mural]

$\forall (\lambda \in I) (x \in C_\lambda)$ is what i meant

[vital dew]

bee [it/its]

[fossil mural]

as in $\forall \lambda (\lambda \in I \to x \in C_\lambda)$

[vital dew]

bee [it/its]

[cursive nymph]

i mean....
ok, so, we rewrite
$$
x \in M \backslash \bigcap_{\lambda \in I} C_\lambda
$$

as

$$
x \in M \text{ and } \exists \lambda \in I \left[ x \not \in C_\lambda \right]
$$

and you suggest to rewrite the RHS as

$$
x \in M \text{ and } \forall \lambda \in I \left[ x \in C_\lambda \right]
$$
right?

[vital dew]

Sweet Tea 🧋

[cursive nymph]

tbh it does not pass my sanity check

[fossil mural]

...no

i, uh, you got a lot wrong there lol

we rewrite $x \in M \setminus \bigcap_{\lambda\in I}C_\lambda$ as $x \in M \land \neg \forall \lambda \in I [x \in C_\lambda]$

[vital dew]

bee [it/its]

[fossil mural]

then turn that into $x \in M \land \exists \lambda \in I [x \not\in C_\lambda]$

[vital dew]

bee [it/its]

[cursive nymph]

yeah, I wrote

$$
\exists \lambda \in I [x \not \in C_\lambda]
$$

straight away, since it's equivalent

[vital dew]

Sweet Tea 🧋

[fossil mural]

oh

ok well that equivalence is what i was suggesting

and it's equivalent because of de morgan's law

[cursive nymph]

but I still don't see how it solves the problem

[fossil mural]

well what we're looking for is $\exists \lambda \in I [x \in M \land x \not\in C_\lambda]$, right?

[vital dew]

bee [it/its]

[cursive nymph]

yeah

[fossil mural]

and what we have is $x \in M \land \exists \lambda \in I [x \not\in C_\lambda]$

[vital dew]

bee [it/its]

[cursive nymph]

which is exactly what you wrote here

[cursive nymph]

yeyeye

thank you!

so the main idea was to hide the infinity into the sets and don't work with it directly ig

[fossil mural]

yeah pretty much

[elfin heart]

consider the following function: $f(t) = tst$ for a fixed $s$. After n iterations of the function, how many $t$s and $s$ will the formula have?

for example:
1 iteration: $tst$
2 iterations: $tst\ s\ tst$
3 iterations: $tststst\ s\ tststst$

[vital dew]

kolmotchima

[elfin heart]

I know that it will have 2^n t's, but how many s?

[snow sleet]

because they alternate, if there are 2^n t's, there must be 2^n - 1 s's

[elfin heart]

thx

[warm stirrup]

I don't know how to do a) and is there smthg else then typing on the calculator for b), like a math calculation or math proof? thx

[stray reef]

well you can factorize x^2 - 3x + 2 as (x-1)(x-2)

and then you can apply CRT

[gritty garnet]

how would you apply chinese remainder to this

[stray reef]

$a\equiv 0 \pmod{10} \iff \begin{cases} a\equiv 0 \pmod{2}\ a\equiv 0 \pmod{5}\end{cases}$

[vital dew]

Ann

[stray reef]

with a = (x-1)(x-2)

and then note that with a prime modulus you can actually apply the zero product law

[gritty garnet]

either (x-1) = 0 or (x-2) = 0

what is this prime modulus property zero product property?

[stray reef]

congruent to 0 mod 5, more specifically

[gritty garnet]

sorry.

[stray reef]

p | ab <=> (p|a or p|b)

(in this p is prime while a and b are just integers)

[west ermine]

This name for that is weird. I would call that Euclid's Lemma/definition of prime elements (for rings - if you don't know what that is don't worry about it, unless you want to). I would then say that because of that, the integers mod p has no zero divisors, which means that ab=0 implies a=0 or b=0.

[mighty nest]

yup i essentially wrote a dfs with a slight change, im adding new vertices to the graph as i go
also the part about having 374 with jeff e is very very cool

[agile magnet]

Just make a new graph instead of adding vertices as you go

Cleaner + doesn't change the runtime

[mighty nest]

yeah I meant adding the vertices to the new graph 💀

[agile magnet]

Oh ya

And then you have to argue why dfs on the graph you made (in particular, DFS from which node in the new graph) answers the original question

[lost surge]

i understand the proof except for the notational part? anyone know why its max(epsilon) and not min? is writing for n greater or equal to 2 as well instead?

[compact yacht]

Maximum value between 2 and$\frac{1}{\epsilon}$

[vital dew]

Leu

[compact yacht]

It's not $\epsilon$ it's $\frac{1}{\epsilon}$

[vital dew]

Leu

[snow sleet]

it's because their work for replacing fractions was for n>=2. Look at their inequality 2n^3-n^2-1>n^3 for n>=2.

the other inequality n^2-2<n^2 held for all n>0.

so in order for both inequalities to be satisfied, we must have n>=2

and therefore n^* must be >=2

this also doesn't look like discrete math. Your question is best suited for real-complex-analysis channel

[lost surge]

thanks both of you for helping, i couldnt find the correct channel, because i thought i was doing real analysis and not complex, @compact yacht helped me understand by spelling it out in words.

[calm chasm]

S doesn't have a definition. So I'm not sure how to show its a subset of S intersection S.

[twilit sundial]

this is just definition pushing: if $s\in S\cap S,$ then $s\in S$ and $s\in S;$ that is to say $s\in S,$ so $S\cap S\subseteq S;$ meanwhile if $s\in S,$ then $s\in S$ and $s\in S$ obviously, so $S\subseteq S\cap S,$ and $S=S\cap S$

[vital dew]

elrichardo1337

[twilit sundial]

very similar approach for the union

[grizzled storm]

In a set of five distinct integers ranging from 1 to 8, there will always be a pair whose sum equals 9.

I have to prove this using the pigeonhole principle. While it's pretty obvious, how can I effectively write down why?

[stray reef]

well, why do you deem it obvious?

[grizzled storm]

1+8, 2+7, 3+6 and 4+5 are all sums that result in 9

[stray reef]

ok, and how do you guarantee that one of these sums will be possible to construct from your set of five?

[grizzled storm]

Picking 5 numbers from the set lands in one of these

[stray reef]

this is literally an application of php in all but name lmao

[grizzled storm]

Maybe just stating it is enough to show I know what I'm doing

But I'm never sure about this stuff when it seems too obvious lol

[dense wing]

Good textbooks to learn graph theory from an introductory level?

[odd heart]

I like Wilson

[true iris]

hello can someone help me please

at the question 2

basic the subject is in French I translated it into English

[stray reef]

que signifie l'écriture d'une matrice "sous forme de tableaux" ?

quelle est la différence entre cela et la manière usuelle d'écrire des matrices ?

[true iris]

je sais pas le prof a voulu préciser

[stray reef]

d'où viennent les e élevés aux nombres naturels ?

[true iris]

j'ai utuliser la definition donné

[stray reef]

non tu n'as pas

[true iris]

wn^(i-1)(j-1)

et wn=e^-2ipi/n

[stray reef]

$\omega_n^{(i-1)(j-1)}$, pas $e^{(i-1)(j-1)}$.

[vital dew]

Ann

[true iris]

j'ai pas simplifier

pour la matrice 3*3 j'ai mis des j et jbarre et j^2

[stray reef]

non tu as fait une grande faute

est-ce que tu vois la différence entre $e^{-\frac{2\pi}{3} \cdot 9}$ et $e^9$ ?

[vital dew]

Ann

[stray reef]

il y en a une énorme

[true iris]

oui il y a une différence

[stray reef]

oui

mais

[true iris]

juste j'ecris sur pc

avec la souris

[stray reef]

pk pas sur un papier ?

[true iris]

c'était juste pour vous montré

par apport a votre question

[stray reef]

ok

[true iris]

je vous envoi ma version papier il y a pas de soucis

[stray reef]

alors "forme de tableau" ne signifie rien de spécial

[true iris]

oui

[stray reef]

ok

j'attends ta version sur le papier alors

[true iris]

ok

[stray reef]

c'est quoi j ?

[stray reef]

est-ce que cette notation s'utilise toujours dans ce sens précis dans vos lectures ?

[true iris]

oui

[stray reef]

pourquoi y a-t-il un barre de conjugaison sur le j au centre ?

ah, attends ...

[true iris]

c'est bon non ?

[stray reef]

$\Omega_3$ sera $\bmqty{1&1&1 \ 1 & j^2 & j \ 1 & j & j^2}$

[vital dew]

Ann

[stray reef]

vu que $\omega_3 = j^2 = \overline{j}$ pas $j$

[vital dew]

Ann

[stray reef]

c'est tout inversé

[true iris]

ou il y a mon j barre en a wn^1

[stray reef]

les autres éléments sont mauvais

[true iris]

est la def que en a c'est wn=e^-2ipi/n

je vois pas pourquoi c'est faux

j de base =e^2ipi/3

en ici la déf wn=e^-2ipi/3

et a cet endroit en a un puissance a 1

quand en met au carré le moint s'enlève non ?

[stray reef]

$(\Omega_3)_{23} = \omega_3^2 = (j^2)^2 = j^4 = j$

[vital dew]

Ann

[stray reef]

pas j^2.

[true iris]

?

ah non

je me suis tromper

donc c'est quoi

[stray reef]

je peux me répéter

[true iris]

oui biensur

[stray reef]

mais je préférerais de ne pas me répéter

ou si tu veux je peux me répéter 97 fois

[true iris]

désolé

1 fois s'il vous plait

[stray reef]

$\Omega_3$ sera $\bmqty{1&1&1 \ 1 & j^2 & j \ 1 & j & j^2}$

[vital dew]

Ann

[true iris]

okay

est ce que en peut traiter la question 2 car je peut de temps s'il vous plait

[stray reef]

... je t'ai pas compris

mais y a 2 erreurs dans ton omega_4 aussi

[true iris]

c'est -1 et i

[stray reef]

le -i doit être -1 et le -1 doit être -i.

[true iris]

oui

est ce que vous pouvez m'aider sur la question 2

montre pout tout n que omega*omega barre=nI

moi je fait avec un cas n=2

que si i=j en a 1
Et si i!=j en a 0
Il faudrait que je utulise la somme des coefficient

[stray reef]

il n'y avait pas besoin d'examiner un cas particulier

[true iris]

oui je crois ta raison

sa va pas me servir a trouver la formule

[stray reef]

oui, donc c'est égal à $\sum_{k=1}^n \omega_n^{(k-1)(i-j)}$

[vital dew]

Ann

[true iris]

et je doit arrive a n*In

[stray reef]

il faut arriver à la valeur n si i=j et 0 sinon

le premier des deux doit être évident

le second est un peu moins

[true iris]

comment je peut faire pour avoir i=j si je peut juste bouger k

[stray reef]

bouger k ?

[true iris]

un changement de variable ?

[stray reef]

??

pas besoin ???

on examine deux cas

[true iris]

je veut dire par sortir le terme

[stray reef]

soit on calcule un élément sur la diagonale (i=j)

soit non (i!=j)

[true iris]

Donc on examine 2 cas

et en fait comment

[true iris]

oui

[stray reef]

pour le premier cas

si $i=j$, à quoi est égal le terme général de notre somme, dit $\omega_n^{(k-1)(i-j)}$ ?

[vital dew]

Ann

[true iris]

0

[stray reef]

non

[true iris]

ah

1

ah oui

[stray reef]

1, oui

et à quoi est égale la somme $\sum_{k=1}^n 1$ ?

[vital dew]

Ann

[true iris]

n

[stray reef]

merveilleux

on examine maintenant le deuxième cas

il y a un lemme qui nous aidera

soit $n \in \bN \setminus {1}$, soit $\omega_n$ une $n$-ième racine de 1 et soit $a \in \bZ$ un nombre entier qui \textbf{n'est pas} un multiple de $n$. alors $$\sum_{k=0}^{n-1} \omega_n^{ka} = 0.$$

[vital dew]

Ann

[true iris]

oula

en a n-1

comment

changement de variable

[stray reef]

oui fais en un si tu veux

[true iris]

désolé si je demande plus de précision c'est juste comme sa je comprend mieux

[stray reef]

je vais pas t'accompagner avec les manipulations algébriques

parce qu'au moment je n'ai ni le temps ni la patience

[true iris]

je suis désolé de vous dérange mille merci de pouvoir m'aider

[stray reef]

c'est pas de ta faute je suis juste fatiguée

[true iris]

Oui , c'est vrai a cette heure si en est plutôt fatigué

quand vous avez fait le changement de variable vous avez posez l= a quoi

jors l=k-1

puis avec en a l=0

[raw kindle]

Please double check my work. I'm not quite sure if I'm doing this right.

[errant bear]

looks good. id probably use a \cancelto or add a few words justifying dropping the -7/x^2 term if this is for an intro class @raw kindle

[raw kindle]

Okay, thank you!

[odd prism]

I honestly have no

I’m trying to solve this recurrence relation is this the correct thinking?

[true iris]

une explication s'il vous plait ?

[karmic prairie]

c'est la somme des premiers termes d'une suite géométrique

[crystal rune]

Is my graph theory proof correct? I feel like something is missing.

Question: Find a formula for the number of edges of a wheel graph, based on the number of vertices.
Formula: e=2(v-1) wherein v is the number of vertices and e the number of edges.
Proof.
Base case: Suppose v=4, the number of vertices of the smallest wheel graph. Therefore, 2(4-1)=3(2)=6, which is the number of vertices of W_4
Induction Step: Suppose 2(v'-1) is the number of edges of a graph with v' vertices.
We add a new vertex v_n to the graph. To ensure that the new graph is also a wheel graph, we add two new edges connecting v_n to two existing non-central adjacent vertices of the graph v_1 and v_2, plus another edge connecting it to the central vertex, minus the extra edge connecting v_1 and v_2, totalling 2(v'-1)+3-1=2(v'-1)+2=2(v'-1+1)=2(v'+1-1). Since the number of edges is equal to 2(v'+1-1), the induction step is now proved.

[light raven]

Looks ok. Do you know about Euler's formula V-E+F = 2?

[crystal rune]

i have heard about it don't really know what it is

[agile magnet]

Ehhhhh I have a few issues with this

1: you aren't doing induction properly. Your inductive step is completely backwards. You never "build up" for induction. Rather, you should take a Wheel graph W_n, and if you want to somehow do induction, break it down into a wheel graph W_n-1 and apply your inductive hypothesis to W_n-1.

2: There is a 10x clearer way to do this directly by counting

Here's my first hint for the 10x clearer way, how many edges in the cycle graph C_n?

[crystal rune]

1. I don’t understand why
2. the number of edges is the same as the number of vertices

[agile magnet]

the whole idea of induction is that you want to prove a statement about the nth object using the fact that the statement for the n-1th object is true

since you are proving a statement about the nth object

you should start with the nth object

induction is about taking a larger object, breaking it down into components, applying the IH to the components, and then using that to derive the statement for the initial larger object

Anyways, back to the cleaner proof

ok can you find a copy of a cycle graph in W_n? What edges occur in that cycle? How many edges are left over?

[crystal rune]

Yes, all vertices of a cycle subgraph are connected to one vertex in a wheel graph. The edges of the cycle graph plus the edges that are adjacent to that one vertex constitute the number of edges of the wheel graph.

i can now begin to see why this works

I'll continue this later; i need to go

[tame bronze]

For my discrete math class, had to solve a series of congruence but I got stuck, any tips on where I might've gone wrong?

[stray reef]

do you have access to the fact that if gcd(a,m) = 1 then ab ≡ ac (mod m) => b ≡ c (mod m)?

your arithmetic seems to check out unless i also missed something

bunch of numbers could have been made smaller

[crystal rune]

i think i can create a proof sketch:
A wheel graph W_v with v vertices contains a cyclic graph with v-1 vertices, and v-1 edges too. Notice that the vertices of the cyclic graph are adjacent to a single vertex m in W_v, and the number of such edges are equal to the number of edges of the cyclic graph. Therefore, adding the sum of the number of edges of the cyclic graph and the edges incident to m is equal to the number of edges of W_v, or (v-1)+(v-1)=2(v-1).

[ocean socket]

well ordering does not imply partial ordering, correct?

[cerulean radish]

Well ordering is a type of partial ordering

[ocean socket]

but why are we guaranteed an equivalence relation on our set. i could just have less than couldent i?

[odd heart]

Why do you want an equivalence relation?

[stray reef]

are you sure those words mean what you think they mean

[odd heart]

Well, the notion of equality induces an equivalence relation, but if you're doing ordering, then you're presumably working in a framework where the notion of equality isn't a problematic concept.

Just to clarify:

• when we say "partial ordering", we mean a relation that's transitive ($x\leq y$ and $y\leq z$ implies $x \leq z$, reflexive (for all $x$ we have $x\leq x$) and weakly antisymmetric (if $x\leq y$ and $y\leq x$, then $y=x$).
• a "well ordering" is a partial ordering that's in fact total (for every $x$ and $y$, we have $x\leq y$ or $y\leq x$, i.e. every pair of elements can be compared), and has the additional property that for every set $A$ there exists a least element, i.e. some $x\in A$ such that for every $y\in A$ we have $x\leq y$.

[vital dew]

Outsider

[odd heart]

Note in particular that orderings are always defined as what we'd traditionally call "weak" inequalities rather than strict.

So $x\leq x$ is always true when we're talking about orderings.

[vital dew]

Outsider

[ocean socket]

does a well ordering have to have less than or equal or can it have strict inequality only?

[stray reef]

< and <= are inter-definable, it doesn't matter which one you take as the basic one.

[odd heart]

The standard definition of ordering (including well-ordering) defines it as a "less than or equal" type of relation, but once you have that, you can easily define "strict inequality" based on that.

But the definitions, theorems, and proofs that you see, will probably be based on the "less than or equal" definition.

[stray reef]

on any partial ordered set, if any of <, >, <=, >= is given a meaning, the other three are automatic

[wet flame]

how are they concluding that xz belongs to L_pali ?

[undone lodge]

Help

[wet flame]

nvm its just from the pumping lemma condition

[stray reef]

http://nohello.net/

post the question(s) you need help with

don't just scream "HELP!!!" and expect everyone to drop everything

[agile magnet]

Yup looks good to me

[crystal rune]

thanks

[weary tiger]

There are some problems in combinatorics that consists about counting the number of subsets of a given set (let be a set A), such that a subset of A, (namely X), satisfy some property P(X), and we can do this by counting all the subsets of A and subtract all Y such that Y dont satisfy the property P.

But the powerset cardinality is defined in such a way that it counts the $\varnothing$ and then I thought, If the $\varnothing$ satisfy every property P(X) then we are counting a vacously truth in combinatorics.
It´s that so ? or we have to subtract that too?

[vital dew]

Ring_Homomorphism

[weary tiger]

here is the reference for that property of the empty set

(https://en.wikipedia.org/wiki/Empty_set)

and sorry if this is not the place , I didn't know whether to put this in combinatorics or logic section , so discrete mathematics seems a good place

[stray reef]

you're confusing $(\forall x\in\rien) P(x)$ with $P(\rien)$

[vital dew]

Ann

[grand hawk]

good yt videos?

[weary tiger]

ohhhh right , yes, but in the case the problem is about the x belonging to the subsets?

[stray reef]

your problem statement is general/vaguee af

P(Y) unambiguously establishes P as a set-level property

one for which P(∅) may or may not be true, but is not so automatically

[weary tiger]

yeah I see ,I was confused , thanks

[weary tiger]

consider all the subsets X of ${1 , 2 ,3 ..., N}$ such that for $x \in {1 , 2 ,3 ..., N}$ x is even
¿How many of those sets are for a given N?
in this case the empty set is a subset of ${1 , 2 ,3 ..., N}$ , and also for some some $x \in \varnothing$ , x is even. Should I count that or not (because is vacuosly true) or this is a dilemma like 0 is a natural number or not , etc.

[vital dew]

Ring_Homomorphism

[stray reef]

this is not a dilemma

the empty set DOES satisfy the property "all of my elements are even"

it's even in the name: vacuous truth

[weary tiger]

yes, so vacuosly truth are in some sense part of mathematics? by construction

?

[odd heart]

If it's vacuously true, it's still true.

That's why so many theorems/definitions have to explicitly exclude the empty set

[agile magnet]

This is why I hate the term vacuously true

Why does it need a special term

[weary tiger]

so like true but without any meaning, besides the facility of including that

[agile magnet]

It’s true lol

Idk what you mean by without meaning

[odd heart]

It's the difference between "correct" and "technically correct"

[weary tiger]

not wanting to bother any "pure mathematician" but consider the case I need to apply combinatorics in a computer program , etc (or any pratical apllication). so I need to get the possibilities and I will be counting a possibility I cant use

[fossil mural]

...what kind of program would break on the empty object but still have it meet the natural expression of the criteria??

that just sounds like you optimised it wrong

[weary tiger]

it is just a example

[fossil mural]

ok well that's just an example of my response

[odd heart]

I mean, I am a pure mathematician, and I also frequently hate the fact that the emptyset satisfies a lot of definitions due to peculiarities of logic, and isn't actually an useful exhibit of those definitions otherwise.

But it is what it is.

[fossil mural]

my general response is "why would that happen, what kind of practical application specifically doesn't work on the empty set for some reason"

[weary tiger]

I mean , consider a extreme example where for a budget i would need to count something, this will make me buy more

[fossil mural]

you're assuming that the empty set would have a nonzero price and that you would not actually need to buy it

[weary tiger]

but anyways it is more like a curiosity

because , since it is like convention for set theory, and would be rare to create a new set theory just for avoiding this

[fossil mural]

i really just don't see why vacuous truths would be any more likely than any other mathematical object to be the point where the real world doesn't match the abstractions

[weary tiger]

but this is equally dependent of construction

[weary tiger]

cause vacuosly truths in logic are a part of the construction it self of logic

[fossil mural]

what if your program spits out that actually you're going to need to spend $\aleph_1$ dollars, would you assume that the problem is it counted some vacuous object

[vital dew]

bee [it/its]

[fossil mural]

since presumably that's not a correct result, if you're planning to accomplish some finite task

[weary tiger]

thats funny

it is like , what is my college debt is?

when n->∞

[agile magnet]

Any reasonable algorithm working with combinatorial objects should be comfortable with empty/null cases

The empty tree is a tree, the empty set is a set, etc

Empty graph is a graph

[weary tiger]

null cases
that's it , has passed sometime since the last time I coded , so I had forgotten that, thanks for the example, before I have and intuitive idea of the type null , but now it makes a lot of sense

[fringe python]

hello

SOP=(M′⋅W′⋅T′)+(M′⋅W′⋅T)+(M′⋅W⋅T′)+(M′⋅W⋅T)+(M⋅W′⋅T′)+(M⋅W′⋅T)+(M⋅W⋅T)

[fringe python]

can anyone help?

[tame bronze]

thanks for reminding me of this but I'm not sure how this would help solve the question

[stray reef]

find a smaller number congruent to 203 modulo 11

[tame bronze]

sorry but how would you go about doing that

[stray reef]

what is the remainder of 203 mod 11?

[tame bronze]

5

Oh so I could get 57L ≡ 5 (mod 11)

which could get me 2L ≡ 5 (mod 11) where im stuck again since I'm not sure how to get rid of the 2

[stray reef]

5 is also congruent to 16 mod 11.

[tame bronze]

5 ≡ 16 (mod 11)?

[brave rock]

A different hint: 6 x 2 = 12 = ? (mod 11)

[stray reef]

yes

that is what i said

[tame bronze]

oo ok I got L ≡ 6 (mod 11)

If this is correct then I understand now thanks

[brave rock]

You have made a bad mistake

[tame bronze]

Oh

😦

[brave rock]

Try your calculations again

[stray reef]

show how you went from 2L ≡ 5 (mod 11) to L ≡ 6 (mod 11)?

[brave rock]

It could just be a trivial arithmetic error

[stray reef]

one must always watch out for trivial arithmetic errors

they befall us all

[tame bronze]

ok nevermind I made a bad mistake, I redid it and got L ≡ 8 (mod 11)

[half bronze]

can someone please explain this to me! like a kid because I have a learning disability:
While walking through a fictional forest, you encounter three trolls guarding a bridge. Each is either a knight, who always tells the truth, or a knave, who always lies. The trolls will not let you pass until you correctly identify each as either a knight or a knave. Each troll makes a single statement:

Troll 1: If I am a knave, then there are exactly two knights here.

Troll 2: Troll 1 is lying.

Troll 3: Either we are all knaves or at least one of us is a knight.

Which troll is which?

[fossil mural]

...do you mean you want an explanation of the solution, or are you confused about what the question is?

[tame bronze]

@stray reef @brave rock I got the right answer and understand it now thank you for the help 🙂

[half bronze]

the explanation of solution

[quiet arch]

Hey guys

Can you help me understand unit distance problem in graph theory?

[viral crown]

what's the statement?
are you talking about hadwiger-nelson

[quiet arch]

No, unit problem states the following: you have to construct a graph with maximal unit distances with given number of vertices say n

It is unsolved but what is the essence, i think the answers contradict the definition of a unit distance graph and makes you think the answer in K(n) complete graph when it's not

[viral crown]

why would you think the answer would be k_n? that only works for n = 3 and in n>=4 for k_n the distance isnt 1 for all

[quiet arch]

Give an example

[viral crown]

an example of a unit distance graph for n = 4?

[quiet arch]

Ok

[viral crown]

no im asking if that's what you want

[quiet arch]

Let it be n=4

Just for illustration

[viral crown]

sure

[lethal prairie]

Pretty sure troll 1 and 2 are knaves and the third troll is a knight

[viral crown]

so if you look here

[half bronze]

Yes I found that out I need an explanation

[viral crown]

this graph isn't complete because clearly V1 is not connected to V4

you can also note here that all the distances are unit

bc this is just the classic rhombus

[quiet arch]

And why isn't it?

Connected?

When in this cas ethe number of edges would be larger?

[viral crown]

if it was then the length of that edge would be 2

and not 1

or, wait, sqrt(5)/2, i think

not 2

that also seems wrong

maybe just sqrt5

[quiet arch]

Whatever nevermind

[lethal prairie]

Assume troll one is telling the truth and that he is a knave. If so, then proceed with the next statement: troll one is lying. Well, ideally that is true since Troll One has stated that he is a knave, however, if he is a knave then there aren't exactly two knights making both Troll One and Troll 2 knaves. The final statement just says we’re either all trolls or at least one is a knight and thus by default, you can assume troll 3 to be a knight

[quiet arch]

Thank you u saved me

[half bronze]

How can u assume by default troll 3 is a knave ?

[lethal prairie]

If they were all knaves then technically that makes Troll 3 a knight because of the contradiction being present OR at least one of them is a knight

[vestal bronze]

that doesn't make any sense

2 is saying that 1 is a knave, they can't be the same thing

1 and 3 are knights

3 is true and 1 ≠ 2, so there's 2 cases
case one is Knave Knight Knight
that's a contradiction, because then 1 is true
so Knight Knave Knight

[umbral glen]

Can someone help me solve this? The "hint" says write n choose r in terms of !, and then prompt them in a certain way so we can compare

[agile magnet]

ok idk what "prompt them" means but have you expressed 2n choose n and 2n choose k in terms of factorials?

[vital dew]

Spamakin🎷

[stray reef]

@umbral glen do you still need help with this?

[umbral glen]

No, i figured it our

thank you

[proven ibex]

should this first condition exclude the sink and source?

clearly since a is a source, there does not exist an arc (a, a)

[uneven violet]

For sure they should be excluded. It could be made clearer what domain v comes from in that condition.

(unless you include "the empty path" as a directed walk)

[proven ibex]

well since i've defined a directed walk as

A directed walk in a digraph is a sequence ${v_i}{i=0}^n$ of vertices such that $(v_i, v{i+1})\in A$ for $i = 0, 1, ..., n-1$. If all the $v_i$'s are distinct except perhaps $v_0$ and $v_n$, then it is a directed path

[vital dew]

Frosst

[proven ibex]

then i guess no

[uneven violet]

They don't really say anything about n, so I guess we can have n = 0? That would mean a walk can consist of a single vertex.

[proven ibex]

I should ask for a clarification here

[uneven violet]

Yeah, even if it's uninteresting corner cases, it's nice to agree on the terms.

[tiny zealot]

Can anyone help me to understand recurrence relations

I understand the idea but like not how to prove them

[grizzled storm]

I have to show that in a group of 20 random people at least 2 have the same number of friends.

I'm learning the pigeonhole principle but I'm not seeing how to apply it here

[uneven violet]

You can first consider how many friends a person can have within that group. Since there are 20 people, any person can have between 0 and 19 friends (both included).

But that’s still 20 numbers {0, 1, …, 19} for the number of possible friends a person can have, so we need to do more.

You can notice that if there exists a person with 19 friends in that group, then she’s friends with everyone. Hence there cannot be a person with 0 friends, and the number of possible friends for any person is thus in the set {1, 2, …, 19}. Since you have 20 people, and 19 possibilities for the number of friends, two people must have the same number of friends - by the pigeonhole principle.

See if you can do the remaining case - that there does not exist a person with 19 friends.

[grizzled storm]

Ohh this is pretty nice

[ocean socket]

lets say i give the natural numbers without a defined less than function. how can we define < in such a way it is possible to prove that say 1 < 2 starting from no intuitive notion of less than? i know its a binary relation, but when can we know x < y is true? is there some logical biimplication we can use?

[stray reef]

what is your defn of < ?

or are you asking for one

if the latter, do your naturals start with 0 or with 1? it will affect the definition slightly (not too much, but i don't want to be caught on a technicality!)

[ocean socket]

im asking for one. and lets say with 0

[stray reef]

$x < y \overset{\text{def}}{\iff} x \neq y \land (\exists z)(x+z=y)$

[vital dew]

Ann

[stray reef]

you need to have a definition of + on hand as well but this i believe you might already

then you need to prove that 1 ≠ 2 and that the equation 1+z=2 has a natural-number solution.

[ocean socket]

z also not 0 right? and z a natural?

[stray reef]

all letters are quantified over naturals

also z can't be 0 in light of the condition x ≠ y that i put down

ie whenever such a z exists, it will not be 0

[ocean socket]

ok nice.

how can this definition be extended to the reals?

[stray reef]

it cannot

[ocean socket]

so how do we do it there?

[stray reef]

the reals have to come with an order relation whose behavior is given axiomatically -- not only that of an order relation, but also that of compatibility with arithmetic in R

[stray reef]

multiple ways

you could for example start by declaring that R has a subset called P which satisfies the following properties:

• 0 ∉ P
• ∀x, y ∈ P: x + y ∈ P
• ∀x, y ∈ P: xy ∈ P
• ∀x ∈ R exactly one of "x ∈ P", "x = 0", "-x ∈ P" is true
  and then define a < b to mean b - a ∈ P

what are you doing that requires definition fuckery at this level?

[ocean socket]

thinking. its not homework but i want to learn and am curious. also couldent find this when searching.

[ocean socket]

is this the normal sense of less than? im not sure. if it isnt thats totally fine just wanna make sure im following. Im just not entirely sure.

[stray reef]

wym by "normal sense"?

[ocean socket]

intuitive

[stray reef]

...i don't really think anybody thinks about real number ordering this way tbh

like, the real numbers and their ordering are kind of a package deal

[ocean socket]

i mean if this definition results in the intuitive one. if they agree.

[stray reef]

however referring to the defn you may notice that P is intuited as the set of all positive numbers

if they did not agree why would i give this one to you lol

[ocean socket]

do you have any idea where i can go looking for lots of these kinds of constructions and definitions? just math starting from zfc or? and thank you!

[stray reef]

no, i don't know of any such place

besides maybe a good university analysis course

[twilit sundial]

generally it's not really worth your time to try to learn everything from literal first principles

if there are pathological cases which require you to be rigorous then by all means be rigorous

[ocean socket]

well even this definition i havent seen in analysis.

[twilit sundial]

but otherwise it's not always worthwhile

[little prism]

well it depends on what you mean "start from zfc". do you mean starting set theory from the complete beginning? in my analysis course we did basically construct R starting from peano+naive set theory. that doesnt sound unreasonable for an analysis course

[ocean socket]

well maybe im just fuming about what counts as analysis. have you constructed numbers from the bottom?. and have you been shown a definition like i asked for less than?

[little prism]

I think so? I cant quite remember. at some point you have to skip some details obviously. you dont have that much time

[stray reef]

nobody's that much of a bourbakist anymore idt

[little prism]

maybe if you had more time

[grand totem]

There are plenty of equivalent ways to do so. Some examples include:

• The least relation such that 0 < succ n and if m < n then succ m < succ n,
• The least relation such that n < succ n and if m < n then m < succ n,
• The transitive closure of the relation m ≺ n iff succ m = n,
• The unique relation for which m ≮ 0, 0 < succ n and succ m < succ n iff m < n.
  This is far from exhaustive but you get the idea

[twilit sundial]

i'm trying to figure out what the recursion should be here

i've seen a similar problem (where there are the same number of 0s as 1s in the entire string) which i know is related to catalan numbers, but not sure how to proceed when that constraint is removed

[twilit sundial]

experimentally it seems that it's $\binom{n}{\lfloor n/2\rfloor}$ but not sure how to prove that recursively

[vital dew]

elrichardo1337

[peak hatch]

Can anyone help me with this

[agile magnet]

so you want to design a recursive formula/algorithm to do this?

so the first step of any such problem is identify what decision

so the current digit could be a 0 or a 1

and then given that choice and perhaps some other information you need to track

[twilit sundial]

current digit as in

last digit?

[agile magnet]

errrr

say we've decided what the first i - 1 digits are

reading from left to right

[twilit sundial]

yeah

[agile magnet]

and now we want to decide what digit i is

it could be a 0 or a 1

what information do you need to make that decision?

[twilit sundial]

hmm maybe we separate the cases where

the (i-1) digit string has equal 0s and 1s and

the (i-1) digit string has more 1s than 0s

[agile magnet]

is that enough that you know it has more 1s?

or do you need to track how many more 1s

try to come up with a recursive definition

[twilit sundial]

hmm aight

i'm trying some small cases and listing the "ones minus zeros" values

[agile magnet]

this is not a recursive definition...

[twilit sundial]

yea ik

trying to find one from it

but im a bit lost as you can tell lmao

[agile magnet]

if we've placed the first i - 1 digits (reading from left to right) and are trying to decide what the i'th digit should be

what pieces of information do we need to track?

lets start there

one is the current digit, i

[twilit sundial]

the number of zeros preceding it + the number of ones preceding it? 😭

[agile magnet]

yea that would work

but we could do better, we just care about the difference right?

[twilit sundial]

yeah

[agile magnet]

how many more 1's than 0's we have seen

[twilit sundial]

that number has to be nonnegative

[agile magnet]

Ok so let Prefix(i, j) be the number of strings of length i such that there are j more 1s than 0s

does this make sense?

[twilit sundial]

yeah

[agile magnet]

Now try to write a recursive definition of this function

[twilit sundial]

p(1,1)=1, p(1,0)=0

gonna try to figure out the actual recurrence now lmao

prefix(i+1,j-1)=prefix(i,j)

prefix(i+1,j+1)=prefix(i,j)

hmm

[agile magnet]

Ok when computing Prefix(i, j)

the ith digit could be a 0 or a 1

[twilit sundial]

yea

i just don't know how to write these conditions recursively lmao

[agile magnet]

so if the ith digit is a 0, what do we know about the prefix of the first i - 1 characters?

[twilit sundial]

it has strictly more 1s than 0s, j-1>0?

[agile magnet]

I gtg but you are along the right tracks

if I have time later tonight I'll come back to this

[twilit sundial]

aight thanks lol

[north junco]

choosing randomly 3 points on a regular dodecahedron, whats the probability for it to be a right, but not isosceles, triangle?

sketching it out, i can see that to satisfy such, the 3 points must not be adjacent

but from there im stumped

[analog pebble]

How did you sketch it out that good...

[viral crown]

thats what i was thinking

like damn

[viral crown]

also quick question are you sure this isn't zero

[north junco]

no

there is at least 40

out of 1140

but im wondering if i missed out cases

also quick note, this is actually a misinterpretation of the original problem, it was asking of an icosagon, not dodecahedron

but i decided to continue anyway since with icosagon its easy

[muted bear]

how can I find the modular of super large numbers quickly without a calculator? for example 293829831mod7 or 3^929348mod4?

[viral crown]

ohhh you mean vertices of a dodecahedron

not any three points on it's surface

[viral crown]

something like this is prolly usually done w either a computer, fermat's lil thm, or to an extent euler's thm

there's probably other ways i cant think of off the top of my head

[muted bear]

not using a computer

[viral crown]

do you know whatever that number is base 10

finding n mod 5 is easy enough: look at the last digit and take it mod 5

idk anything abt mods in other bases or wtv

[muted bear]

so how would you go about solving this question?

[viral crown]

i would convert it into base ten and look at the last digit

assuming i knew how to convert it to base ten

[muted bear]

okay, so if it was mod 7, it would be much harder

or something other than 2 or 5

[viral crown]

naively yes but still not really

[muted bear]

okay how so then?

[viral crown]

if the number was large (~10-12 digits) i'd just divide by seven and the first decimal digit will tell me what the mod is

if the number im modding by is large

like say

if im trying to get

498372498274927347928947382979 mod 31892372198

or something inane

at that point i'll just use a computer bc life is short

[muted bear]

well yea but the idea is that it would be on a test without a calculator

[viral crown]

if something like that is on a test without a calculator then there's a trick and i would try to find it

[muted bear]

what about numbers to very high exponents, such as 2^(192318923) mod 4

is there a trick?

[viral crown]

in this specific case note that 2^(192318923) is (2^2) * 2^(192318921)

[muted bear]

and then what?

[viral crown]

thats 4 * 2^(192318921)

so by defn of mod it's 0

[muted bear]

okay, say mod 5?

[viral crown]

i'd bash using flt for a few minutes and if nothing quick came up i'd move on to the next problem

[stray reef]

FLT is best

2^(192318923) mod 5 = 2^(192318923 % 4) mod 5

big number % 4 = (its last two digits) % 4 since 100 is divisible by 4

ain't really that difficult imo

@muted bear do you still need help with that nonary mod 5 problem of yours

[muted bear]

this is what i did,

is that correct?

[stray reef]

this is alright, yes

but \cdot instead of asterisks

[muted bear]

this was months ago

im studying for a final

[stray reef]

also you don't really need to explicitly convert to base 10 here

[muted bear]

how so? and how would you go about problems like these?

[stray reef]

you can just view it as a linear combination of powers of nine

you know what 9 is congruent to -1 mod 5

so 9^n is congruent to (-1)^n

which makes adding up the remainders of 9^n mod 5, scaled by the nonary digits, easy

also wait.

you fucked up.

the last digit has place value 1 not 9

[muted bear]

i got the right answer somehow

but yes, it should be 9^0 right

[fossil mural]

tbh i think what happened is you did something essentially random and hit the 20% chance of getting it right anyway

given that there are only 5 possible answers

[muted bear]

yep looks like it

[fossil mural]

there are multiple mistakes in the way you expanded out the number, and then "only looking at the last digit" isn't correct either because 9 is not 0 mod 5

so essentially your method amounts to "9 * the last digit" and in this case that happened to be correct

[fossil mural]

the expression you wrote is 38707000410 which is not the same as 38007000041

[stray reef]

i have a legit solution typed up

also i think one must understand exactly why the last-digit shortcut works in base 10 but NOT in base 9

@muted bear do you think you understand that point? or would you like to have it explained

[muted bear]

yes, i understand, but the idea was that the number was converted to base 10

[fossil mural]

it wasn't though

that number in base 10 is 13563437239 which looks nothing like what you wrote and would also be really annoying to compute by hand because you have to work out a load of powers of 9

[stray reef]

ok wait i think this is important to go over

explain in your own words: why does the base-10 last digit tell us the remainder of a number mod 5, but the base-9 last digit doesn't?

[muted bear]

because any number ending in 5 or 0 in base 10 would be in the same congruence class mod 5

[stray reef]

why is that? why is it that if two numbers end in 5 and 0 in decimal, then they're congruent mod 5?

[muted bear]

since 5 divides any number ending in 5 or 0

?

ie the mod would be equal to 0

[stray reef]

why does 5 divide any number ending in 5 or 0 in decimal?

"in decimal" is extremely important here.

[muted bear]

i guess since 5 is exaclty half of the base?

im not exactly sure how to put it in words i just know it instinctually

[stray reef]

you don't know it instinctively, you memorized it without proof.

[stray reef]

this is close-ish.

it's because 5 divides the base.

and so all powers of 10 are congruent to 0 mod 5.

thus, if you write out the number as a sum of powers of 10 according to its decimal expansion,

all of the terms from digits other than the last will vanish

[muted bear]

so 4 would divide any number ending in 0 base 8

[stray reef]

yes

augh, shitty internet.

@muted bear anyway the idea is that the 9^n terms wouldn't vanish as the decimal ones would.

however 9^n is congruent to (-1)^n mod 5.

so you can still simplify the sum by a lot.

do you see what im talking about?

fyi i am more than ok to write it out more explicitly if you want/need me to, so don't hesitate to ask

[muted bear]

yeah, i think I understand now

topic switch, could someone explain this?

[stray reef]

have you seen big O notation before at all?

[muted bear]

yeah

i just dont understand the "give a fully mathmatically precise definition"

O(n) means that the time scales linearly with the input

but that wouldnt get full credit

[stray reef]

have you seen the formal defn of big O?

[muted bear]

maybe, but i can't recall it

im assuming that's all its really asking

[stray reef]

yes it is

basically look it up on wikipedia lol

[twilit sundial]

still need some help on this: it's not entirely clear how i should even set up the recursion

i've tried examining the last digit and then trying to do stuff with the n-1-digit string that precedes it

but am having trouble translating that into a recurrence

if last digit 0: n-1 digits before have strictly more 1s than 0s

if last digit 1: n-1 digits before have no fewer 1s than 0s

[twilit sundial]

still haven't made any progress 😭 any help? (i am very bad at code)

[grizzled storm]

So I think I got it, I assume there are just these 2 cases?

[uneven violet]

Cool. Yeah, there's only these 2 cases: Either there exists a person with 19 friends, or there does not exist a person with 19 friends.

[uneven violet]

When generating the binary string, and when you are at some bit, my idea is to have a parameter k that denotes the difference between the number of 1's and the number of 0's before this bit. We must always have k>=0.

If you let F(n,k) denote the number of binary strings of the required form of remaining length n, and where there has been k = (number of 1's) - (number of 0's) before it, then you are looking for F(n,0).

As you say, the first digit must be a 1, so you already have F(n,0) = F(n-1,1).

If k > 0, then the next digit can be either a 0 or a 1, so F(n,k) = F(n-1,k-1) + F(n-1,k+1).

[cursive nymph]

in words, I think it was that (abs value of) f must be eventually not greater than the linear function n |-> n times some constant

or think magnitude of f instead of |•|

[fossil mural]

metamath https://us.metamath.org/mpegif/mmset.html does this and is also computer-formalised
so it's a somewhat ridiculous level of detail but the advantage is that it's never going to be insufficiently detailed, given that if they use literally anything that they didn't define the computer would complain

[ionic lodge]

i am having some trouble here with inclusion exlcusion principle
i am using it to find number of primes less than or equal to 100
so as the standard algorithm says, I only need to check for primes smaller than sqrt n
hence I made 4 sets, each divisible by 2,3,5,7
then using the principle, i found the cardinality of the intersections required
but I am getting that there are 22 primes in 1 to 100, not 25?

[stray reef]

show your calculations?

i think i might know why you are off by three, but im gonna need to see your work anyway to be sure.

@ionic lodge

[ionic lodge]

oh
i already resolved it in one of the help channels
and yes your hunch is right on the mark
it was because of unity and counting 2,3,5,7 as non-primes

[stray reef]

ok right yeah

that's what i thought would be the case

include 2, 3, 5 and 7 themselves (+4) and exclude 1 (-1)

[ionic lodge]

yup

is this a common beginner's mistake btw?

[stray reef]

idk about beginner

it's just a simple miscount

it's not the kind of mistake that makes you redo all your work

it's one that can be recovered from

[ionic lodge]

yeah that's true ig
thanks anyhow

[grizzled storm]

Another pigeonhole problem breaking my head.

A guy drinks 42 coffees in January, at least 1 a day. I have to show there must be a set of consecutive days when he drinks exactly 17 coffees

[stray reef]

imagine him making a table with 31 columns (one for each day) and two rows

one for "coffees i have drunk thus far, today included"

the other for "the above + 17"

[grizzled storm]

Thanks I'll try that

[grizzled storm]

Did it. First row is redundant since it is just the day, not seeing what I can infer from the second one unfortunately

[stray reef]

wrong on both counts

the guy drinks at least one a day, not exactly one a dday.

anyway, think about what it means if the same number appears twice in the table (excl. dates)

[ocean socket]

How would one go about proving a certain set, does not result in russell paradox? or is really a set? or isnt an element of itself? lets say i construct a "set", made from all sets of a certain type. how can i prove whether that is a genuine set or not? i cant find anything on google, so i would appreciate even just a source.

[viral crown]

generally in zfc we have regularity and pairing which together can show that no set can contain itself

[ocean socket]

sure, but that doesnt stop me from trying to make one mistakenly? so how can i check myself?

[viral crown]

ohh i see

well

you'd prove the theorem "For all sets $A,$ we have $A \not \in A$" and then if you had a set $B$ s.t $B \in B$, you would say "$B$ cannot exist because it contradicts the above theorem"

[vital dew]

valley

[ocean socket]

sure so how can i actually determine if it contradicts that theorem? like how do i even begin? like lets say im not sure whather b is in b or not. but i want to prove it isnt.

[viral crown]

im confused

you already know b isnt in b

becuase of the theorem

how could you be not sure if b is in b or not?

[ocean socket]

because im trying to make a set, but that doesnt mean its really a set

[viral crown]

is this abt like

classes

[ocean socket]

prove the set of all sets that contain 1 as an element is an actual set, and not contradictory. might be a more specific example. If im not thinking about it wrong.

[stray reef]

then you have to decide if you're working in zfc, where everything is a set, or not, in which case 1 might be an object of a different type

and in the former case you have to also decide whether or not 1 itself (which is then a set) belongs to your set

if it does then you might be in trouble

but then would imply $1\in 1$ so maybe not

[vital dew]

Ann

[viral crown]

if you can construct that set from the axioms of set theory, then it's a set, is how i would do it

[stray reef]

basically you need to be very explicit about the axioms you are starting with

cause what is and isn't allowed is dictated entirely by them

so trying to say anything without a clear list of axioms is moot

[ocean socket]

sure, so say we work in zfc, and i define the set as following, the set S of all sets B is in S if and only if 1 is in B. where we define 1, as just the intuitive number i think will do.

[stray reef]

just the intuitive number 1
no can do

in zfc everything is a set

[viral crown]

just define 1 as ${\emptyset}$

[ocean socket]

yeah, and the intuitive number can vbe formalized

[vital dew]

valley

[stray reef]

well how are you formalizing it

is the question

[ocean socket]

sure go ahead with what valley said.

[odd heart]

That is certainly a very good definition of 1, but I'd quibble with calling it "intuitive"

[ocean socket]

If my original definition is unclear i can go write it out more logically if needed

[compact yacht]

he said 1 is intuitive not the definition

[compact yacht]

"the set S of all sets B is in S if and only if 1 is in B" this is a false statement

[ocean socket]

how is it possibly false? its a definition of a set S?

[viral crown]

also i would like to say this doesn't fall prey to russell's bc for it to contain itself, it would need to contain ${\emptyset}$, and as we have ${\emptyset} \not \in {\emptyset}$, we're good

i think

[vital dew]

valley

[odd heart]

Also if you're following ZFC, you literally can't define a set that would be its own element since that's impossible in ZFC

[ocean socket]

sure its intuitive why this is alright atleast to me, but how do i actually prove it so i can deal with constructions where i cant tell?

[odd heart]

You could make a mistake, but asking how to avoid it is akin to asking how to avoid division by zero. Just need to make sure you're not making a false argument, which is a sweeping statement but what can you do.

[viral crown]

like i said earlier if you can construct a set with the axioms of set theory, it's a set

[compact yacht]

It doesn't define S that's an statement

[viral crown]

so just show that this set is constructible like that and you're good

i still do think that this might actually be a class but im not fully sure

[ocean socket]

it can be atomic i think

[compact yacht]

the definition of a set must distinguish for every set if it is or not in S

[compact yacht]

in this case you are just stating that a particular set is in S

[storm pumice]

can I ask a question specifically about discrete math here as well or does it need to be through the math-help?

[snow sleet]

you can ask any discrete math questions here. That is precisely what this channel is for.

[weary tiger]

Confusion about how this Cartesian Plane represents the relation.
Context: Define a relation C from R to R as follows: For any (x, y) ∈ R × R,
(x, y) ∈ C means that x^2 + y^2 = 1.
c. Draw a graph for C by plotting the points of C in the Cartesian plane.

[storm pumice]

In the exam we had to prove a vertex coloring with max 4 colors concerning a (1,1,1,2,3) Graph but when I put it into the term I got 3,37 which is smaller than 4 and therefore false. Surprise, surprise, it was wrong so im wondering if I have misunderstood the concept? If anyone could maybe give their insight that would be great

[snow sleet]

that circle in the xy-plane illustrates the relation C because it is a plot of every ordered pair (x,y) that satisfies the equation x^2+y^2=1.

[weary tiger]

i know..but is there a reason thats its circular?? like couldnt it be any other shape

[snow sleet]

think back to calculus. x^2+y^2=1 is precisely the graph of the unit circle.

centered at the origin and has a radius of 1

[weary tiger]

OHHHHHHHHHHHHHHHHHHHH

oh my god im being dumb

okay thank you SOO much

[compact yacht]

You can write complement as an intersection

[calm chasm]

Hold on. Need to make that make sense.

[calm chasm]

You mean like S\T = S intersection T^c?

[compact yacht]

Yup

[calm chasm]

Yee

I'm going to use that

But I think I screwed up writting the definition out for S^c \ T^c

[compact yacht]

What you got?

[calm chasm]

Just so you have context

For when I write U

I first wrote the lhs as this (x ε U Λ x ~~ε ~~ S ) Λ (x ε U Λ x ε T)

[calm chasm]

^

wait

I think I see it

that doesn't follow my ven diagram

x has to be an element of T

right?

Cause the venn diagram I drew is just shading in T (excluding the intersection part of T.

[compact yacht]

Yes

[calm chasm]

okay

for the rhs

x wouldn't be an element of U right?

that makes sense to me right now.

[compact yacht]

It would be, U is the universe set

[calm chasm]

Are you sure? Because to me this is the venn diagram

Like I know U is the universe set.

Well I guess if x isn't in the universe set, then it couldn't be in T

[compact yacht]

T is in U then once x is in T it is in U as well

[calm chasm]

agreed

[sonic shadow]

What is meant by write my answer as a finite series?

Is it $\frac{-1}{1-x}$?

[vital dew]

dulg_n

[sonic shadow]

Or do I literally write out the sum?

$\sum_{k = 0}^{n}{(-1)^k x^k}$

[compact yacht]

Maybe it meant sequence?

[vital dew]

dulg_n

[sonic shadow]

Like this?

Strange, seems rather too easy

oughtta be a trick

[compact yacht]

Probably (-1)^k x^k

I think

[compact yacht]

The first one is not convergent

[sonic shadow]

no, in a generating function, you are actually solving for the function s.t. the coefficient appears in the power series

[compact yacht]

Aaaah I see

[sonic shadow]

Its like, instead of solving an equation by reducing to its power series, and then gathering data about the coefficients of the power series, you are actlly going backwards

[compact yacht]

That's not supposed to be here btw

[sonic shadow]

rlly?

damn

Where then?

[compact yacht]

Probably calculus or real analysis

[sonic shadow]

Actually, the point is, these are meromorphic functions, ie they need only be convergent somewhere

Damn, this is from my combinatorics course

[compact yacht]

Combinatorial structures then I think

[sonic shadow]

I think this is too basic for combinatorial structures

[compact yacht]

I don't know if I understood it

[compact yacht]

ALL that's finite

[sonic shadow]

Yes, i think that literally is the answer

[compact yacht]

Nvm then :V

[sonic shadow]

well, for example, if our sequence is a constant sequence $(r)_{n=1}^{\infty}$

[vital dew]

dulg_n

[sonic shadow]

Then the generating function is $\sum_{n=1}^{\infty} rx^n$

[vital dew]

dulg_n

[sonic shadow]

But this is merely the geometric series, so $\sum_{n=1}^{\infty} rx^n = \frac{r}{1-x}$ defined for each $x$ such that $|x| < 1$

[vital dew]

dulg_n