discrete-math

[sour arrow]

That is 6 ways to make a set. That makes sense - every penny you don't choose forces you to choose a nickel instead

Now, 6 ways to get a set of 5 coins. But one of those sets has no pennies, which isn't allowed.

@sterile flint
Note the product on the left is up to k+1. You can just pull that "k+1th" set factor of the product

[slate marten]

i see

[sterile flint]

Ahhhh Okay I see the relation

[slate marten]

with the restriction, the different sets of coins with at least 1 penny would be C(6,5)?

[sour arrow]

No. That's without the restriction

C(6,5) - 1
With the restriction

[slate marten]

those numbers seem small to me, maybe I am misunderstanding the question

[raw birch]

It's small because the order doesn't matter and you're taking a relatively big part of it.

If you think of the Tartaglia's triangle, bigger numbers are on the center that is. Lower numebrs are attained when the set is small or when it is big but you take a great part of it

[slate marten]

okay that makes sense , the C(6) is unclear atm

[sour arrow]

You're right, C(6) is very unclear

What?

[slate marten]

uh

[sterile flint]

Whats the explaination for the last simplification

Ik it says substituting but idk how they got (k+1)

[weary tiger]

list out some terms

(1+1/1)(1+1/2)(1+1/3)....(1+1/k)

now combine the fractions

@sterile flint

[sterile flint]

It should be k not k+1

So (1+1/1)(1+1/2)(1+1/3)....(1+1/k) right?

[weary tiger]

ok now combine the fractions

[sterile flint]

By combining fractions do you mean just simplifying them?

So 1/1 would be 1

[weary tiger]

1/1+1=2/1

1/2+1=3/2

[sterile flint]

Yep

How does that become (k+1)

Would the fractions in this case be the k?

[weary tiger]

$\frac{2}{1}\cdot\frac{3}{2}\cdot\frac{4}{3}\cdot\frac{5}{4}$

[vital dew]

sanath1237:

[weary tiger]

you know that this is 5

[sterile flint]

Yes

[weary tiger]

because you cross out the 2s, 3s and 4s

[sterile flint]

Yep

[weary tiger]

$\frac{2}{1}\cdot\frac{3}{2}\cdot\frac{4}{3}\cdot\frac{5}{4}...\frac{k+1}{k}$

[vital dew]

sanath1237:

[weary tiger]

now what would this be

[sterile flint]

1/1?

If the pattern continues

k and k would cross out

Leaving the 1/1

[weary tiger]

leaving k+1/1

@sterile flint

[sterile flint]

How do you get the k

Doesnt the k/k cancel out?

So it becomes 1/k

[weary tiger]

yeah the k/k cancels

leaving the numerator

[obtuse lance]

go back to this example sanath gave and look carefully at what is cancelled out, do it yourself:

https://cdn.discordapp.com/attachments/496785905474994186/700478302133157928/539181475996893204.png

[sterile flint]

2 and 2, 3 and 3, 4 and 4

[weary tiger]

right

and whats left?

[sterile flint]

5/1

[weary tiger]

so its the last numerator over the first denominator

[sterile flint]

Oh I see now

But doesn't k+1/k just simplify to k/k + 1/k

That was what confused me

[weary tiger]

you good now?

[sterile flint]

Yeah okay I get that concept

Thanks

[quartz gull]

You all guys are pretty smart damn

I need to be Math major soon

[night crescent]

Can someone prove f(x)= -x+3 is injective, surjective and bijective?

[gleaming zephyr]

what does it mean for a function to be injective

surjective

and bijective?

[night crescent]

I mean how can I prove this function if it's injective, surjective and bijective

[gleaming zephyr]

well whats the definition of an injective function

[night crescent]

That's what I'm trying to find out

[stray reef]

you don't know the definition of an injective function?

also, f(x) = -x+3 does not by itself define a function. what's your domain and what's your codomain?

[night crescent]

I do, but I need further explanation with this example

the domain is R

[stray reef]

and i am guessing that so is the codomain

[night crescent]

Yep

[stray reef]

okay

great

$(\forall x_1, x_2 \in \bR)(f(x_1) = f(x_2) \implies x_1 = x_2)$

[vital dew]

Ann:

[stray reef]

this is the definition of your function f being injective

it could be stated instead as $(\forall x_1, x_2 \in \bR)(x_1 \neq x_2 \implies f(x_1) \neq f(x_2))$

[vital dew]

Ann:

[stray reef]

and from an intuitive standpoint, we say a function is injective if it never maps two different inputs to the same output

[night crescent]

So that pretty much means if the results are different then it's injective*?

[stray reef]

no, that's too vague.

[weary tiger]

if it has an output for every input, and an input for every output, its bijective

[stray reef]

no

not only is that also vague, it seems closer to surjectivity than to bijectivity.

[gleaming zephyr]

the function is faithful

to its elements

[stray reef]

meh

[gleaming zephyr]

boom i won

[stray reef]

that's even worse somehow

[gleaming zephyr]

XD

[stray reef]

and introduces a new term

which will just get anyone learning this further confused

[gleaming zephyr]

i mean u can think of faithful more as

okay nvm

[weary tiger]

am i wrong

[stray reef]

@night crescent the important thing when proving a function is injective (or surjective) is to not overthink it

proving a function is injective is just like proving any other "for all" statement

@weary tiger you're vague.

[gleaming zephyr]

ann slightly off topic

for the last time

can u send me ur gt pset

[stray reef]

it's pinned in this channel

[gleaming zephyr]

ty

[night crescent]

@stray reef Okay. So I have to at least get one value to prove the statement is wrong

?

[stray reef]

....what

that sentence doesn't make any sense

[night crescent]

Dunni

I'm even more confused ._.

[stray reef]

you have your function f: R -> R defined by f(x) = -x+3.

and you're trying to prove that this function is injective.

yes?

[night crescent]

yes

[stray reef]

okay

so by the definition of an injective function

you need to prove $(\forall x_1, x_2 \in \bR)(f(x_1) = f(x_2) \implies x_1 = x_2)$

[vital dew]

Ann:

[stray reef]

in other words, you need to prove $$(\forall x_1, x_2 \in \bR)(-x_1 + 3 = -x_2 + 3 \implies x_1 = x_2)$$

[vital dew]

Ann:

[stray reef]

are you able to do that?

@night crescent?

i might've just gotten ghosted.

[night crescent]

No haha

So I have to take any two values here?

[stray reef]

do you know how to prove "for all" statements?

x1 and x2 are supposed to be arbitrary

[night crescent]

so x1=1 , x2=0

[stray reef]

no!

[night crescent]

🤦‍♂️

[stray reef]

do you know how to prove "for all" statements?

statements of the form (∀x ∈ X)(P(x))?

[night crescent]

Well If i want to prove it false, then I must get one value to make the statement false? right?

At least one

[stray reef]

but i'm not asking you to prove it false.

i'm asking you to prove it true.

or attempt to do so.

look

you need to prove that for all real numbers x1 and x2, if -x1+3 = -x2+3, then x1 = x2.

[night crescent]

Then I have to loop thru all real numbers tho

[stray reef]

no, you do not!

[night crescent]

Okay so what's the deal ._.

[stray reef]

"if $-x_1 + 3 = -x_2 + 3$ then $x_1 = x_2$"

[vital dew]

Ann:

[stray reef]

this is what you want to prove

maybe it's wrong of me to explicitly say the universal quantifiers because they're scaring you

but when doing algebra you are essentially working with universally-quantified variables anyway

[crude otter]

hey guys i have a few questions

oops let me change my name

Okay

Is it okay for a compelete bipartite graph to be like K1,12 or K12,1 ?

only one vertex in a set

[stray reef]

i believe that'd just be called a star

[crude otter]

yea that explains why i can't find any graph like that ..

thanks

[weary tiger]

does this make sense

[weary tiger]

what does this definition mean by relation?

[sour arrow]

It's defining the word "relation" in the definition

A relation from A to B is a subset of A×B

[weary tiger]

oh,

[sour arrow]

With a bit less formality, a relation between A to B can be thought of as a set of arrows starting at a member of A, and ending at a member of B

[weary tiger]

is A x B powerset

[sour arrow]

Each arrow notated as (a,b)

[weary tiger]

hmmm okay im gonna have to let that sink in

[sour arrow]

A×B is the cartesian product of A and B

[weary tiger]

cartesian product i totally forgot that word

its the combinations

between two sets

if im not mistaken

[sour arrow]

Each element of A×B is a combination of two elements, one from A and one from B

[weary tiger]

brilliant, thank you

[sour arrow]

Np. Feel free to ask if you have any more questions about it!

[weary tiger]

will do 🙂

[weary tiger]

for a relation to be transitive does the transitive property have to apply to all pairs where (a,b) and (b,c) imples (a,c)

or only for at least 1?

[fossil pewter]

All

[weary tiger]

okay tyvm

[weary tiger]

im confused on what partitions are on equivalence relations

[humble bridge]

do you guys help with building automata here?

[dawn loom]

20% of designated hitters strike out their first time up at bat in a game. Of those who do
strike out their first time up at bat in a game, about 50% are able to get on base at least once
before the game ends. Let S = strikes out first time up Let B = gets on base at least once
before the game ends. Use probability notation in terms of the events S and B when
answering this question. What is the probability that a designated hitter strikes out his first
time up and gets on base at least once before the game ends?

For this problem

Its P(BnS) P(B|S) * P(B)

Right

Whats P(B)

I think P(B|S) = .5, is that correct

[dawn loom]

Any ideas?

[raw birch]

im confused on what partitions are on equivalence relations
@weary tiger A partition of a set is a colection of disjoint nomempty subsets whose union is the total set. For example, a partition of N={1,2,3...} is {{2,5},{1,3,4,6,7,8,9,...}} another partition is {{1,2,3,4...}} another partition is {{1},{2,3},{4,5,6},...}.

I can guess you read something like: The quotient set of an equivalent relation over a ser is a parition of the set. What that means is that given a nonempty sef X a set and ~ a relation on X, the ser X/~={[x] : x in X} is a partition of X.

That is proved as follows.

If I take x in X, [x] is nonempty because x belongs to [x].

If I take x,y in X, x not related with y we have that [x] and [y] are disjoint because supposing the contrary there exists z in [x] and [y] but that means x~z and z~y. By the transtitivity of ~ we have [x]=[y] which is a contradiction.

And X=U[x] over x because every element of X belongs to its class of equivalence.

[low agate]

Hey guys i've asked a question in a question channel but Ill repost it here
Is R anti-symmetric? Once again, this means that two distinct elements do not relate to each other.
https://cdn.discordapp.com/attachments/490557019623915520/701086478712832020/unknown.png

[stray reef]

is it true that if x R y and y R x then necessarily x = y?

i.e. is it true that if x^3 = y^3 and y^3 = x^3 then x = y?

[low agate]

yes

for this relation it is, correct?

does that mean it is anti-symmetric?

because I thought equivalence relations were not supposed to be anti-symmetric

[pale epoch]

why?

the prototype of all equivalence relations "=" on the real numbers is antisymmetric

[low agate]

so equivalence relations are symmetric and anti-symmetric?

[pale epoch]

that is not what i said

[low agate]

i am confused about what you said

[pale epoch]

equivalence relations are symmetric, transitive and reflexive

but they can be also antisymmetric

[low agate]

so equivalence relations must be symmetric, transitive, and reflexive, but they can have any of the other properties as well?

[pale epoch]

yes

(if the other property is still possible)

[low agate]

gotcha

i have another question as well if youre willing to help

[stray reef]

just post it

[low agate]

I started it, and I do not understand why R would be reflexive

here is what my professor posted about this:

in case that is not a universal way of writing the modulo operator

[stray reef]

any number is congruent to itself modulo 4

$d(x) \equiv_4 d(x)$ for all $x \in \bN$

[vital dew]

Ann:

[stray reef]

is this what you are having trouble understanding

[low agate]

yes

i understand what it means

i think

[pale epoch]

check your definition of what divides means

[low agate]

but i dont know how its reflexive

[pale epoch]

surely 4 divides 0

[stray reef]

$R$ is reflexive if and only if $(\forall x \in \bN)(xRx)$

[vital dew]

Ann:

[stray reef]

$xRx$ iff $d(x) \equiv_4 d(x)$

[vital dew]

Ann:

[pale epoch]

also lol @ "in the world of mathematics"

[low agate]

yes lol he was talking about it in reference to coding previously

but how is it reflexive

if i choose an x like 1

[stray reef]

do you or do you not agree with the statements i wrote up there

yes or no

[low agate]

yes

[stray reef]

do you agree that any number is congruent to itself modulo 4

[low agate]

how is it?

5%4 is 1

5 is not congruent to 1

or 5

i mean

im confused

[stray reef]

"congruence modulo 4" is not an OPERATION, it's a RELATION

[low agate]

does that mean essentially that both sides are modded by 4

[stray reef]

no

hm

hds

h

hh

if you want to phrase it in terms of the % modulo operator as in C/C++

we say two numbers x and y are congruent modulo 4 when x%4 == y%4

[low agate]

ah

that makes sense

so it would be reflexive because any arbitrary x in N % 4 is the same as that same x in N % 4

[stray reef]

bad wording but yes

[low agate]

lol my b

[stray reef]

tbh the congruence modulo n relation is more fundamental than the modulo operator

[low agate]

ok

would $5 \equiv_4 1$ be true

[vital dew]

dlkj:

[low agate]

because the are both congruent by modulo 4

[pale epoch]

ye

tbh just use the definition your prof gave you: $x \equiv_4 y \iff 4 \mid (x-y)$

[vital dew]

Lochverstärker:

[low agate]

alright thank you

[pale epoch]

and 4 divides 4

[low agate]

right that makes sense

im pretty sure i get it now

there is a good chance i will be back later with more relations questions to ask

thank you guys

[wise hinge]

there is toonies and five dollar bills in a wallet that has a total of $100
1) I need to write an equation that represents the each equation 2) isolate the variable for the quantity of toonies and then five dollar bills 3) then determined the possible combination algebraically for the amount of toonies and 5 dollar bills

please dm me if anyone knows

[modest zealot]

wtf is a toonie

[wise hinge]

its a 2 dollar coin

[modest zealot]

oh

ask this in #prealg-and-algebra

[ancient basin]

I'm a bit stuck in this question. I'm trying to do proof by mathematical induction, but I can't manage to get it right.

[robust mango]

@ancient basin Still stuck?

[faint narwhal]

you are close, can you show that 4k(k+1) is always a multiple of 8?

[weary tiger]

think about k(k+1)

what can you say about it

what

explain what you mean

why

[stray reef]

why unless k=0

is it

you tell me

do you guess or do you know for certain

[weary tiger]

... or is it?

[stray reef]

it's sloppy

whether or not it receives full marks is up to the prof but it feels like there's a missing step

like "among k and k+1, one will always be even and the other odd. the product of an even number and an odd number is again even. therefore k(k+1) is even for all integer k"

[weary tiger]

or just use induction on k to prove k(k+1) is always even

[paper belfry]

any help:

https://cdn.discordapp.com/attachments/342724530747473933/701494890239885432/Screenshot_22.png

https://cdn.discordapp.com/attachments/342724530747473933/701494888704901160/Screenshot_21.png

[ancient basin]

Follow-up on my question from earlier today. I realized that I didn't use the right definition of odd integers. However, I'm still stuck even with the right definition.

Still trying to do mathematical induction, but I can't get the different sides to be the same.

[pale epoch]

huh

so 2n+1 is supposed to be your integer

(in the assumption)

then you try to show it for 2n+3?

@ancient basin

[ancient basin]

Yeah

[pale epoch]

ok, then why is the RHS 8(2n+1)+1

that is not the statement you are trying to prove

it is also wrong

[ancient basin]

So you mean k isn't the odd integer? It's just some integer?

[pale epoch]

yes

otherwise the statement becomes $4n^2 + 4n + 1 = 16n+9$, which is wrong

[vital dew]

Lochverstärker:

[ancient basin]

Since for P(2n+3), the integer k would be different than P(2n+1), I assume induction is probably not the way to go?

[pale epoch]

it is

[ancient basin]

I got here, not sure the relation between the two different k

[pale epoch]

ok so

just factor out the 8 in the last line

on the LHS

and please remove the RHS of every line in the induction step

that is what you want to prove

you can add $=8k+1$ once you are done and know what the $k$ is

[vital dew]

Lochverstärker:

[ancient basin]

Got here, but not sure how m+n+1 is equal to k

[pale epoch]

look back at the statement you want to prove

you just want to show that the square is equal to 8k+1 for some integer k

is m+n+1 an integer?

it's not like you are given that k, you have to find it

[ancient basin]

Ohhhh, okay. I see, thanks a lot for the help!

[pale epoch]

you're welcome

[main marlin]

Is this the appropriate channel for finite state automata questions?

[sleek swallow]

No, it’s only appropriate for infinite state automata questions.

[main marlin]

ah shit

i've been caught red handed

[noble wasp]

anyone know modern algbra?

[sour arrow]

Ya

[ancient basin]

in b), can anyone tell me what they mean? I'm a bit confused by the notation

[sour arrow]

@ancient basin
f : A → B
Is a function that takes every element in the set A, and maps each to some element in the set B

[ancient basin]

Oh okay, so it asks how many permutations there are?

so 2^n

[sour arrow]

So f takes each number from 0 to n, and assigns 0 or 1 to each

Which is not what I'd normally call a permutation, but you're right there are 2^n such functions

[ancient basin]

Alright, thanks :)

[mild eagle]

Guys is discrete structures hard?

cuz i heard alot of rumors about it

[pale epoch]

no, it's easy

[sleek swallow]

@mild eagle discrete structures are very soft, actually

[main marlin]

@mild eagle depends on your teacher and the subject you're covering

[obtuse minnow]

Show for any odd n, "n^5 - n" is congruent to zero mod 120.

[weary tiger]

Induction

[stray reef]

uh nope

lcm(2,3,4,5) is not 120

[obtuse minnow]

(btw, that's not original. It was on a GRE:Mathematics practice test.)

[spark oyster]

uuuh right

i'm not good with numbers after all

[obtuse minnow]

Answer: || Factor: n(n^2+1)(n+1)(n-1). Either n, n-1, or n+1 is a multiple of three. n^2 + 1, n-1, and n+1 are all divisible by 2. Either n, n+1, n - 1, or n^2 + 1 is divisible by 5. ||

[spark oyster]

ah yeah okay, i wasn't too far off at least; you can check divisibility by its separate factors with this nice representation

you just have to watch out that you have sufficiently many factors of 2

divisibility by 5 also follows from little fermat

[obtuse minnow]

okay well that's it for me. Gnoite!

agreed with Fremat's Little Theorem.

[pale epoch]

well

a path is usually a trail with distinct vertices

and a cycle has all vertices distinct except beginning and end

but those definitions are non-standard i guess, so

[raw birch]

"congruence modulo 4" is not an OPERATION, it's a RELATION
@stray reef It can be seen as an unary operation but I agree that this is not usual and confuses more than helps

[stray reef]

[raw birch]

XD

[pale epoch]

so a path cant have repeated edges and repeated vertices?
@iron crescent check your definitions, ultimately it doesn't matter and defintions are not standard

[west quarry]

Hey can anyone help me with this induction question?

I’m not sure if I screwed up the simiplyfing or what

[near prawn]

this is bad

youre assuming what you need to prove

[west quarry]

@near prawn wdym? I thought simple induction was to prove it’s real for all values, in this case it was n ≥ 1

[near prawn]

you cant say the lhs is equal to 9^(k+2)-9 all over 8

thats what you need to show

[spark oyster]

well it's basically the order of what you're writing down that's wrong

it's a fine way to try and understand the problem, but you shouldn't write it down like that in the final proof

but that's a very common thing people do at first

in any case, 8 * 9^(k+1) is not equal to (8 * 9)^(k+1)

the left hand side is one eight times (k+1) nines

the right hand side is (k+1) eights times (k+1) nines

but you're very close to getting something nice; basically, you need to understand why 9^(k+1) + 8 * 9^(k+1) is 9^(k+2)

hint: distributivity

[weary tiger]

Hi, I'm working through the introduction to sets for Hammack's Book of Proof. Suppose A = {1,2,3,4} and B = {a,c}. We want to find the Cartesian Product of : (A x B) x B

Do we distribute the elements in the final product, as in: would the first entry be represented best as (1, a)a or (1a, aa)?

[spark oyster]

Hi! There's no distribution in the cartesian product, so definitely not the latter 🙂 But the first version is also not how you should write it; you have two cartesian products, so elements in there will have two pairs of brackets

e.g. your element would be written ((1,a),a)

[weary tiger]

Regarding the bracketS: Ah, that's obvious in hindsight. Thanks 🙂

[spark oyster]

no problem!

[mild eagle]

Could you guys recommend any yt playlist?

[stray reef]

for what

[weary tiger]

@iron crescent what are you struggling on with it?

How do you show something is an equivalence relation

2 out of 3 parts of the definition should be trivial and the other should follow from using the definition of two graphs being isomorphic

(composition of bijective functions is bijective)

[mild eagle]

Could you guys recommend any yt playlist?
@mild eagle
For discrete structures, I want to get a head start on it

[sour arrow]

Did you just tag yourself haha

[lilac pivot]

the quote feature of discord

automatically tags the person who wrote the message

which in this case was themself

[near prawn]

Did you just tag yourself haha

[white jetty]

Can anyone give me an example of a relation on the set of text strings that is not reflexive, not antireflexive, not symmetric, not antisymmetric, and not transitive?

[weary tiger]

xRy if the first character of x is the same as the last charcter of y @white jetty i

or if one of them is empty i guess

[white jetty]

Hi

I was thinking about something like {"aks", ""} before

but idk if that's right

[weary tiger]

dunno what that even means but the relation i said works im p sure

[white jetty]

okay, I'll use ur answer first and I'll figure something out later

@weary tiger thx man

[weary tiger]

do you understand why it isnt all of those properties?

for instance it isn't reflexive because "ab" isn't related to "ab"

[white jetty]

yeah

by {"ask", ""} I mean I was thinking like two strings, one is empty and the other one is not

[weary tiger]

i mean though

thats not an example of a relation

i didnt really see how it's related to the question

[ancient basin]

Just a quick theoretical question that I'm confused about: are all strongly connected graphs also weakly connected?

[weary tiger]

Yes

If a graph is strongly connected then there exists a path between every pair of vertices

if you change all the directed edges to undirected edges then the same path still exists between each pair of vertices so it is weakly connected by definition

so strongly => weakly

@ancient basin

(weakly doesn't imply strongly though and to see that you can consider a graph with two vertices and a directed edge between them)

[ancient basin]

Alright, thanks for the explanation!

[bleak kite]

An inventory consists of a list of 100 items, each marked available or unavailable. There are 55 available items. Show that there are at least 2 items in the list exactly 4 items apart. I know how to solve it, but I don't understand why it works. I used the pidgeonhole principle, but I don't have an intuitive understanding of why it works. Would someone mind explaining this to me?

[wispy ridge]

In a sense, the pigeonhole principle generally talks about "pigeonholes" to fill with "pigeons."
In this case, the "pigeonholes" are the 100 spots for items and the "pigeons" are the 55 items themselves.

The pigeonhole principle divides the pigeonholes such that you assume, for contradiction, that there can be up to one "pigeon" at each set, and shows a contradiction.

Let's see how this applies here.
We have 55 pigeons to fit, so we'd like to show that we have 54 at most of these groups.

It now remains to be asked - what are these groups of pigeonholes?
These groups are:
Slot 1 - slot 5
Slot 2 - slot 6
Slot 3 - slot 7
Slot 4 - slot 8

and then:

Slot 9 - slot 13
Slot 10 - slot 14
Slot 11 - Slot 15
Slot 12 - slot 16

and so on.

Notice that once you get to slot 92 with slot 96, which are 96 / 2 = 48 pairs, you have:
48 + 4 = 52
groups of "pigeonholes."

Now, let's suppose that we fill those 4 blank spots that don't have any pairs.

We now have 51 pigeons left for the other 48 pairs.
According to the pigeonhole principles: We have more "pigeons" than "pigeonholes," and so we get that at least one group will have at least 2.

What does it mean to have at least 2 pigeons in a set that looks like:
slot x - slot x + 4
?
It means that they are 4 items apart.

Yup, I'm a moron. Sorry.
By the way, it could be that they meant 4 items between them, in which case, this solution is wrong.
The idea should still be the same, so I hope it gives a tiny bit of intuition.

[weary tiger]

think it must mean what ur saying tbh

[wispy ridge]

Then ignore the numbers in the above solution.
The correct pairings are:

Slot 1 - slot 6
Slot 2 - slot 7
Slot 3 - slot 8
Slot 4 - slot 9
Slot 5 - slot 10

and then:

Slot 11 - slot 16
Slot 12 - slot 17
Slot 13 - slot 18
Slot 14 - slot 19
Slot 15 - slot 20

And so on, until:

Slot 91 - slot 96
Slot 92 - slot 97
Slot 93 - slot 98
Slot 94 - slot 99
Slot 95 - slot 100

Now, note we have 50 such pairs. (those are the "pigeonholes")
Since we have 55 "pigeons" then at least one of them must include at least 2 "pigeons."
This means there's a pair with two slots 4 items away from each other that have items in them.

[inner gyro]

isnt d_n undefined

with n = 0

i dont understand how they can assume that

1 <= i <= k

when the original problem said to prove 0 < d_n <= 1 for all ints n >= 0

so shouldnt it be 0 <= i <= k

but when i = 0 then that means d_0 which is undefined no?

[sour arrow]

Check the structure of a proof by induction. Assuming that it holds for all integers less than k is a standard move

[inner gyro]

right

but my question is

[sour arrow]

Basically, let's say it holds for all integers less than k

Then show that it holds for k + 1

[inner gyro]

we are to assume that 0 < d_n <= 1 for all ints n >= 0

but d_0 is undefined

[sour arrow]

Where is this happening?

[lyric pumice]

@bleak kite That can be shown purely formulaically.

[inner gyro]

i can understand if they meant

n >= 1

[sour arrow]

Oop, you're right that's not likely supposed to be that way

[inner gyro]

but n>= 0 makes no sense to me

is it safe to assume that the textbook made a typo?

[sour arrow]

Note you can still prove it.
d(k-2) = d(k)/d(k-1)

But that's not teaching how to do induction lol

[inner gyro]

yea the purpose was to use induction

but is it safe to assume that the textbook made a typo on the n >= 0 part?

because i literally cant understand the inductive reasoning the textbook provided

if n >= 0

which is here

[sour arrow]

Yes that's a typo. Your base case is n = 1 and n = 2

[inner gyro]

okay

got it

but also

the first line of that answer

says

let P(n) be the inequality d_n <= 1

but they also excluded the 0?

the 0 < d_n <= 1

is that also another typo

[sour arrow]

I think that's half of the proof

You can do the other half with 0 < dn

[inner gyro]

that was actually the end of the proof

thats all they wrote

oh what the hell

i just realized

this answer key gave the answer to the wrong question....

ok well nvm then

thanks for answering my question

atleast i know im not going insane now

[ancient basin]

Anyone know how I can prove that conclusion ii) is false? I previously answered that it can't be true since nothing implies that it is true. But I lost marks since they wanted me to prove it.

[undone python]

You need to give a counterexample (in my reading of the question). For example, there are two students. One is good at counting and prob. One is good at Q-logic and programming. This satisfies the premises, but conclusion ii) is false.

[arctic jewel]

You know, I was reviewing old material and I'm really blanking on
"Distribute 5 cards out of 52 cards to 3 players. How many ways can this be done?"

I'm not looking for answers, just on what to look up.

This is permutation right?

[stray reef]

the problem is a bit understated

the answer will depend on whether we're allowing one or more of the three players to have no cards at all

and i wouldn't think about "this is a permutation problem" or "this is a combination problem" at all bc those are not useful classifications ime

[arctic jewel]

I'm just trying to keep some of this info active in my mind, but I understand the sentiment. Talking semantics won't help much.

and it's the first thing that goes memory wise.

[stray reef]

mm

nPk and nCk are basically just shortcuts for counting certain kinds of arrangements under certain conditions

in some sense so is the factorial function

i know this isn't universal but i kind of stumbled upon nCk and nPk by myself at some point before even knowing they had those names. just by playing with arrangement counting problems with the multiplication principle in mind

[arctic jewel]

I suppose that's sort of like a brute force method of thinking.

[stray reef]

sorta?

that was years ago for me

[arctic jewel]

Well I'm gonna review my old textbooks/notes for more info.

I'm really blanking on alot of this subject. I really never used it again, mostly.

Thankfully I scan alot of stuff, so I can look back. Even back then.

[arctic jewel]

I did end up finding a similar problem in my old notes. @stray reef

[stray reef]

uhhh

bad wording

that counts the number of ways to give 4 players 5 cards each

[arctic jewel]

Oh I know, it's a bad game of deciphering for me.

and these were my notes. Granted this probably was copied from my professor at the time.

So by my old logic it's
C (52,5)×C (47,5)×C (42,5) and then so on.

[stray reef]

yeah assuming your problem meant 5 cards each to 3 players

[arctic jewel]

Yup, based on that assumption.

Well thanks Ann. If I have anymore stupid questions, I'll be back.

I have a whole other page of confusion, but I'll spare you that for another day.

[lyric pumice]

@arctic jewel Your problem is solved by considering 5-card sets from 52 cards and 5-card multisets from 3 people.

[noble wasp]

anyone know modern algebra, if so please pm. i am willing to give you donation or pay you.

[near prawn]

i only know historical algebra sorry

[olive hamlet]

prehistorical algebra gang gang

[west hedge]

i prefer algebra from the first 10^{-32} seconds after the big bang

[pale epoch]

you could start by computing P(U)

you check each element, see if its an upper bound and count

what is the definition of upper bound?

[velvet linden]

i tried lagrange but it gets too long

[pale epoch]

you could do it with a hasse diagram as well, i guess

which?

[weary tiger]

how do i simplify (j+1)! - 1 + (j+1)

hmm strange

trying to do inductive step in proof

that doesnt get me to (j+3)! - 1

[pale epoch]

how are those elements upper bounds of {4,10}

well, except the last one

an upper bound of a set has to be greater or equal than all its elements

ye

root the tree

then the structure should be pretty obvious

actually its not as simple as i thought

nice question though

ok, i think i solved it

might steal as a homework exercise

or exam question 👀

depends on what the curriculum was and the rest of the exam

it's ok, had to think more if there are other solutions

it's not like you need deep theory to solve it

what is m

but like the only thing that would prevent me from asking this on an exam is that im not sure how to give partial credit

hm

i don't think that's correct

i started with

and now notice that it is impossible to add just 1 vertex

you always have to add 2 to a vertex of degree 1

like

so you always have 4+2x vertices

x now tells u how often you perform this move

each time the move is performed, you lose 1 leaf and gain 2 new ones

so net gain of 1 leaf

so 4+2x=200, solve for x

i like that question though

i will put it on homework

🤷 it happens

[compact mural]

combinatorics is frustrating but at the same time super satisfying

its frustrating in the sense of "um, why cant i figure this out"

but once you do, god that feeling is great

[modern void]

hey!

is anyone on?

have a question about graph theory

[obtuse minnow]

just ask

[vital dew]

Frank:

[north jewel]

I'm confused because

But this definition allows

...which is not true

sorry, i meant to send this definition of transitivity (source: wikipedia)

did i do something wrong or are these symbols ambiguous to some extent? ://

[north jewel]

anyone?

[north jewel]

oh fuck i made a really stupid mistake

ignore everything above lol

the proof makes a bad assumption that y exists

[weary tiger]

U study at the VU? @iron crescent

[wicked basin]

hi can someone pleaes help me with a problem?

https://media.discordapp.net/attachments/679541799471153212/702702976141361252/deathh.PNG?width=719&height=613

i dont think i did it right

sry handwriting is trash im using my mouse

[weary tiger]

have you learnt stars and bars

12C3 is saying how many ways is there to pick 3 things from a collection of 12

not how many ways to assign 12 things to 3 groups

[wicked basin]

what is stars and bars

[weary tiger]

it's a counting method to find out how many ways there are to place n objects into r bins

which is what you want here but with 12 objects and 3 bins

[wicked basin]

oh so is the anser 3^12?

[weary tiger]

nah the answer for the first one is 14C2* but i cba to explain a whole method to you just read https://en.wikipedia.org/wiki/Stars_and_bars_(combinatorics)

or someone else will come along and explain it maybe

but for the second part you can simplify the problem by just starting each dog with 2 bones then considering how many ways there are to distribute 6 bones amongst 3 dogs

[white sundial]

Is it possible that you can help me summarize Binomial Theorem, Probability Axioms, and Expected Value? Please?

[stray reef]

that is a lot to summarize

[quartz gull]

Can someone help me with this?

[pale epoch]

certainly $K \in \mathcal{O}(K)$?

[vital dew]

Lochverstärker:

[lyric pumice]

@wicked basin Use multisets.

[wicked basin]

i am stuck on c

pls help

[weary tiger]

You assume that $a_k=2^{k-1}$

[vital dew]

same:

[weary tiger]

Then have that $a_{k+1}=(1+a_1+a_2+.....+a_{k-1})+a_k=a_k+a_k=2\cdot a_k=2^k$

[vital dew]

same:

[low agate]

is a relation anti-symmetric if the only element in the relation is (0,0)

[pale epoch]

ye

[weary tiger]

how do i argue this ;0

[pale epoch]

why this question again

[weary tiger]

cus that isn

enough the justify?

[charred cargo]

?

Does this look like the correct graph?

@weary tiger

sorry to bother you but mind helping me out

?

[weary tiger]

@charred cargo

[charred cargo]

?

[weary tiger]

wait

im v confused

whats the definition of an endpoint

[charred cargo]

hold up

this is what my book says

"Vertices b and e are the endpoints of edge {b, e}. The edge {b, e} is incident to vertices b and e"

[weary tiger]

e_3 must be a loop then

i guess

but literally the only time it mentions loops in graph theory

where i've learnt it

is here lol

[charred cargo]

I was thinking its a loop too

[weary tiger]

but doesn't make sense otherwise

are you allowed to have loops

because that's all it can be

[charred cargo]

doesn't say it cant

[weary tiger]

because if goes between two points it has 2 end points

[charred cargo]

k but here's the problem with v sub 2 being on its own though

the next question is:

Find three different walks from v1 to v3 and specify whether each one
of them is a path/trail from v1 to v3.

https://media.discordapp.net/attachments/496785905474994186/703000512043417600/JPEG_20200423_175301.jpg?width=395&height=702

if that point v sub 2 is a loop then how can there be 3 walks to v sub 3

?

[weary tiger]

wtf

[charred cargo]

there is only one

[weary tiger]

can u just screenshot the whole question

[charred cargo]

Its a wonky one

maybe i drew the graph wrong but i doubt it

Maybe you can visualize it better than I

[weary tiger]

nah u havent

i genuinely think its wrong

the weird thing is though

no matter where e3 goes

[charred cargo]

Bruh why does this keep happening to me 😂

[weary tiger]

there isnt 3 walks from v1 to v3

[charred cargo]

The last work sheet was fucked up too

Oh well

I'll assume it's a truck question

And just say it's impossible or something

Trick question

[weary tiger]

nah its not a trick

its literally just wrong

[weary tiger]

how should i begin to prove f is a total function?

[weary tiger]

hello

i need help

[hallow blaze]

hi can I get help pls

[lyric pumice]

Yes.

[hallow blaze]

so I had a problem

How many different locations are needed for six drug stores located at the distances shown in the table, of two drug stores cannot be within 15 miles of each other?

its a graph coloring problem

ended up with a graph with 6 vertexes and 5 edges going into each one

how do i find the minimum

is the minimum 6?

[regal yew]

Using properties of boolean algebra, how can I go from (c' + b) * c + a * (b + a') to (c' + b) * (c + a) * (b + a')?

They're equal, but I can't find the property to actually go from the first to the second.

@lyric pumice

[lyric pumice]

Show us the table.

[regal yew]

They're equal, I just need the property to go from the first to the second.

There's no property to just... add parenthesis... that I can tell

[lyric pumice]

There is an addition rule.

[regal yew]

Associative?

[lyric pumice]

a --> a+b

[little nacelle]

can somoene help

https://cdn.discordapp.com/attachments/328208536029102081/703227669994668061/unknown.png

[empty forum]

can someone tell me which logic is correct

prizes (20)
checkmark (3)
(3)20 = 60

OR

prizes(20)
checkmarks 3 (3)
checkmarks 2 (2)
checkmarks 1 (1)
checkmarks 0 (0)
(3*2)20 = 120

[weary tiger]

how many ways are there to CHOOSE 3 prizes from 20

[empty forum]

so 60

ok

[weary tiger]

no

both of your answers are completely wrong

[empty forum]

really

[weary tiger]

yeh

for the first checkmark

you have 20 choices

for the next 19

[empty forum]

ohhhh

[weary tiger]

one after 18

but then

[empty forum]

(20 x 19 x 18)x3

?

[weary tiger]

idk why u keep multiplying by 3

201918 is the ways to pick 3 but includes order

[empty forum]

because you have to leave 3 checkmarks

[weary tiger]

20x19x18 is the way to pick 3 including order

[empty forum]

ohhh

[weary tiger]

but we dont want to include order

so need to divide by 3!

[empty forum]

we are not including a counter

need to divide?

(20x19x18)/3?

[weary tiger]

3! = 3x2x1 = 6

have you learnt about the Choose function

like nCr

[empty forum]

no this is the way hes been instructing it

maybe im misinterpretting it

[weary tiger]

someone else can probs help out better it seems like you've learnt it in a kinda weird way

but the answer is (20*19*18)/6=20C3=1140

[empty forum]

ohh so we divide by 6?

[weary tiger]

yeh its because

20x19x18 counts each selection 6 times

because

imagine if we pick boxes 1,5,8

it picks

158

185

518

581

815

851

which are all the same

so we have to divide by a factor of 6 because we don't care about order

[empty forum]

mind helping me understand a different example then?

if it isnt too much

[weary tiger]

yeh sure i can try

dunno how much help ill be

[empty forum]

this is what i thought of so far

[weary tiger]

yeh exactly

that's it

this example is slightly different because in this one the ordering does matter

[empty forum]

ooo!! ok

[weary tiger]

like in this example

1357 and 3571 are two different pins

but in the last one

picking boxes 1,3,5 is the same as picking boxes 3,5,1

[empty forum]

okok

is it ok if i ping you for help

if im stuck

[weary tiger]

yeh sure

[empty forum]

so for this one it asks for at least one even

im forgetting how this works but this is like a problem where i have to make the word problem i think

[fossil pewter]

Total - all odds

[weary tiger]

(and conveniently you just worked out how many there are with all odd)

[empty forum]

oh

thinking about this wrong again aren't i

[weary tiger]

why did you divide by 5

but there are 10,000 possible combinations

of 4 pin code

[empty forum]

there are 5 possible odd digits

i just took the odds out was my logic

leaving evens

it wants at least one even nmv

nvm

uhhh what would it be?

this is passing me by

[weary tiger]

So you know that all codes either have at least 1 even number OR they have 0 even numbers

[empty forum]

ohhhh

so its either or

[weary tiger]

Can you work it out from there?

[empty forum]

need my hand held a little just for this one if you dont mind

is it...

0,2,4,6,8 (5)
first 1-4 = 4
2nd 1-3 =3
3rd 1-2 = 2

4x3x2?

i exlcuded the 0

actually not sure why i did that

[weary tiger]

there's quite a few problems

first of all you missed a 6 in your list

[empty forum]

ohh shit

[weary tiger]

but the main problem is

what you're calculating there

is the number of pins that have ALL even numbers

but what we want is all the pins that have ATLEAST 1 even number

[empty forum]

ohhh

[weary tiger]

But you know that every PIN has either 0,1,2,3,4 even numbers in it

And we are looking at the number of ways that a PIN can have 1,2,3,4 even numbers in it

But we already know the number of ways a PIN can have 0 even numbers in it because that means all the numbers are odd

and you worked that out in the previous question

So you have that

number of all odd pins + number of pins with atleast 1 even number = total number of pins

[empty forum]

so if we arrange that to

is the total number of pins ranged 0-9

120 + n = 10000?

no can't be simply that

[weary tiger]

120 + number of pins with atleast 1 even number = 10,000

[empty forum]

yeah

[weary tiger]

yeh

and thats what ur working out

[empty forum]

wait is that number 10000/2?

wait no thats all the even numbers

it has to be at least 1

so

0,1,2,3,4
(10000/2)
(5000/2)
(2500/2)
(1250/2)?

120 + 625 = 10000

745 possible combinations?

sorry if im seeking validation from you. I just can't do this problem lol

[empty forum]

Teacher just sent out the solution list for the homework

Was almost right haha

[ornate dagger]

If I have a Hamiltonian circuit, and I remove the last traversed edge from the path that makes the circuit, the remaining graph will always have a Hamiltonian path with endpoints the endpoints of the edge I just removed right?

I've been trying to think of a counter example, but I've been unsuccessful

[stray reef]

yes

that is true

[azure lichen]

seems pretty obvious to me too. a hamiltonian circuit goes once through every vertex, and removing one edge still leaves you with a path with that property

[hallow blaze]

what is D and why?

[pallid lintel]

Hi, im trying tp prove this lemma. Would it be reasonable to say: If we assume for contradiction that T is a spanning tree of G/e, and T U {e} is not a spanning tree of G. Then this necessilary implies that when we added the edge {e} to T, this created a cycle in T U {e}? Or is that something we need to prove as well.

once i show it creates a cycle i have a previous lemma that says T will be have a cycle in G/e (contradiction)

cycle=circuit. I know a lot of people use different terminology in graph theory

[pallid lintel]

for other direction i just got the answer from following definition of contraction.

[split ruin]

Hey, I'm stuck with this one thing

If you roll two dice and multiply the results, how many outcomes are there?

There's less than 36, because primes for example

But is there any way to generalize this or solve it logically?

[stray reef]

are you asking how many distinct products there are

[split ruin]

yeah

[stray reef]

aside from manual counting i don't really see a way to go about doing it

1 2 3 4 5 6 8 9 10 12 15 16 18 20 24 30 36

17 distinct products ig

[split ruin]

yeah thanks! was hoping there was some general solution but ig not

[short wyvern]

Could you please suggest any websites or links where I could find exercises with +- elaborate correction on the topic of Partially ordered sets?

[inner gyro]

so we have to show that (k+1) is true and so we have to end up w/ something like

((k+1)^2+k+1)/2

would it be wrong

for me to

rewrite ((k+1)^2+k+1)/2 as (k^2+3k+2)/2

and instead prove that

[serene basalt]

prove it for n=0 and then prove it for n+1 assuming n

for n+1 you're showing that $\sum_{i=0}^{n+1} i = \frac{(n+1)^2+(n+1)}{2}$

[vital dew]

skymoo:

[inner gyro]

got it

how do i go about proving this

[stray reef]

do you know how to prove two sets are equal

[inner gyro]

by showing that they're subsets of each other

would this be a proof by cases?

[pale epoch]

i don't see why you would split this into cases

[inner gyro]

oh right

nvm

i was thinking something along the lines of

if we prove that s_n holds integers, naturals, and rationals then it is a subset of real numbers

[pale epoch]

uh

each individual S_n is a subset of R by definition of the [a, b] notation

[inner gyro]

oh

[fickle notch]

what's the difference between using set builder notation and showing two sets are subsets of each other to prove two sets are equal? aren't they essentially the same method?

[sour arrow]

You're much safer relying on the first method, as set constructions get more complicated

[fickle notch]

what's the difference though? i find that set builder notation involves proving two sets are equivalent by converting the first set to the second set, but through proving subsets you're also converting the first set to the second set along with the second set to the first set, yet somehow you confirm each set is a subset of the other

[sour arrow]

Nuu with subsets there is no conversion

[weary tiger]

Graph theory is discrete math yes

[sour arrow]

If you prove that A is a subset of B, then you've shown that A "fits within" B.

If you prove that B is a subset of A, then you've shown that B "fits within" A.

Showing both means that A and B are the same set.

@fickle notch

[fickle notch]

oh

[sour arrow]

Sorry, go ahead @weary tiger

[weary tiger]

I'm curious if with this definition it is feasible to use a computer to graph this.

Let S_0 = {0, 1}.

For each i >= 1, define:

T_i = {{x, y}: x, y in S_{i-1}}.
S_i = {{x, y}: x in T_i, y in S_j or T_j for some j < i}.

Then let f(n) = |S_n| + |T_n|.

You can turn this construction into a graph by making all the elements of S_i, T_i vertices, and placing an edge from v to w if v is an element of w.

But just up through steps 0,1,2,3

[charred cargo]

channel's dead right now huh?

b should be impossible right?

[weary tiger]

^^^

[idle violet]

helo ann

cobinatorics

combinatorics pdf book

[pallid lintel]

b is not impossible. i can think of infinitely many walks and one path

v1v4,v3=path. v1,v4,v1,v4,v3= 2nd walk. v1,v4,v1,v4,v1,v4,v3 =3rd walk.

[frosty epoch]

v3 also has an identity on it

you could just go e1,e2,e3,e3,e3,e3,e3

except e3 is canceled this year so maybe you cant

[pallid lintel]

no you cant? e3 is a loop

its disconnected from the other 2 edges

[frosty epoch]

oh i thought it was on v3

my b

[languid quarry]

(10 pts) Solve the recurrence relation: an=3an-1+1 with  a1=0.
Solution.
(10 pts) Let f : R→ℝ be function defined as f(x) = 5x + 1. Find its inverse f −1
Solution.

Hard stuck on these problems

[stray reef]

is that first one meant to be $a_n = 3a_{n-1} + 1$

[vital dew]

Ann:

[orchid pawn]

@languid quarry

[languid quarry]

yeah

formatting got messed up my bad

Solved the second one already but first I am lost

[pallid lintel]

hey, been a while since i did weighted tree's but i'll try. assume that minimum weight isnt a tree, it contains a cycle. We can delete edges within the cycle and still maintain connectivity to the vetices of such a cycle

thats idea of proof

[pallid lintel]

in other words cycles contain unnecessary weight

[quiet steeple]

Give a counterexample to prove that the statement f
−1
(B ∩ f(A)) =
f
−1
(B) ∩ A is false.

[north jewel]

Using the alphabet ${A, B, C, D, E, F}$, how many strings begin with $F$ and do NOT end with $EB$? Repetitions are not allowed.

[vital dew]

Frank:

[north jewel]

The way i did it was: # strings starting with F - # strings starting with F and ending with EB = 1 * 5 * 4 * 3 * 2 * 1 - 1 * 3 * 2 * 1 * 1 = 114

is this a good way to think of it? Is there another way to do it? I suck at counting and im trying to get better at it lol

[near prawn]

yea that seems like a sound method

[north jewel]

are there other sound methods?

[near prawn]

thats prolly the quickest tho

[north jewel]

i was trying to think of it without subtraction, but i couldn't think of something that seemed correct

hmm ok ty

[lyric pumice]

3!(5*4-1)

@north jewel

@near prawn

[north jewel]

can you explain?

[lyric pumice]

Start from the end of the string.

There are 5 options for the last character.

There are 4 options for the second to last character.

[north jewel]

oh, and you're subtracting the case it's EB

[lyric pumice]

Eliminate 1 for the case of EB.

[north jewel]

and then 3 options for 3rd character * 2 options for 2nd character * 1 option for 1st = 3!?

[lyric pumice]

Select among the remaining letters (exclude F) as normal permutations.

[north jewel]

ah, i see thanks!

[weary tiger]

@north jewel didnt you only count the 6 letter strings

dont you need to count them all

[north jewel]

hmm. i'm surprised no one noticed, but the question is actually asking for the # of 5 letter strings lol

whoops

answer should still be correct

[inner gyro]

what kind of function is this

i thought that one to one functions mean that for every x there exists some y

and onto functions is for every y there exists some x

in this case the book states that the definition i said above is wrong for one to one functions
they said a function is one to one if f(a_1) = f(a_2) and a_1 = a_2

if thats the case

this pic wouldnt be one to one

but i dont think it is an onto function either because the v in the codomain doesnt have an x

so this would be neither a onto or one to one?

[pallid lintel]

suppose a=-3, and b=3. square them. both =9, so its easy to see you can have function that isn't surjective or injective

and you are right

[inner gyro]

gotcha thanks

[static basalt]

Need clarification on the part "in decreasing powers of y". What does this mean when I'm using the binomial theorem?

[sour arrow]

(in decreasing powers of y)
ay^6 + by^5 + cy^4 + dy^3...

Basically, what's the y^4 term?

@static basalt

[static basalt]

@sour arrow I figured that but why would they mention it specifically if that is the only variable?

since the powers would decrease to 0 anyway

[sour arrow]

The 3rd term is different if you list the powers in ascending order

ay^0 + by^1 + cy^2 + dy^3...
So if it's ascending order, you want the y^2 term instead

@static basalt

[static basalt]

ah I see, It's just that the rest of the questions of this problem set have been in descending order anyway

[last sigil]

It is general convention to have decreasing powers

[static basalt]

^ Yeah it was just confusing why it had to be mentioned in this specific question but not the others

[nimble plover]

can someone explain how they get this answer?

the original question is 22x = 29(mod 67)

i found the numbers to be 1, and -3

[spark oyster]

Is there any single step in that screenshot that confuses you?

[nimble plover]

yes! I don't know how it goes from 22x=29(mod 67) to suddenly -3x29 = 47(mod67)

so i have my two numbers, 1 and -3 and the gcd is equal to 67x1 - 3x22 which is 1

and then im stuck

[spark oyster]

So what's going on in that screenshot, what happens there is: You know that 22x = 29 mod 67, so you can also replace it in that equation, so -3 * 22x = -3 * 29 mod 67

[nimble plover]

so just multiply both sides by -3?

why -3 and not 1?

[spark oyster]

Yeah, basically

[nimble plover]

i know 1 won't change it in this case, but if it was 2 for example

[spark oyster]

Yeah, you could do it for any number

The useful thing is just that -3 * 22 = 1 mod 67

[nimble plover]

so i get -3 * 22 = -3 (mod 67)

[spark oyster]

No, that's not true

[nimble plover]

multiplying by -3

[spark oyster]

What equation did you multiply to get that?

[nimble plover]

22x = 1 (mod 67)

the original

[spark oyster]

that's not what you have tho lol 😄

you have 22x = 29

[nimble plover]

ooh shit, i got that from the youtube video i was trying to learn it from

[spark oyster]

haha no worries

[nimble plover]

so i have 22x = 29(mod 67) and then *-3 both sides

and that's it?

[spark oyster]

yes, exactly

And it looks like magic, but the reason it works is because we found the number -3 to exactly make everything good here

[nimble plover]

and 1 works too?

[spark oyster]

You could multiply the equation with 1, 2, 50, 10234, yeah; but not all of these numbers will make the equation easier

[nimble plover]

okay, so i have -66 = -87(mod 67)

[spark oyster]

missing an x

but yeah

[nimble plover]

i thought x was -3