discrete-math

[stray reef]

yeah

the remainder of a mod 5 can only be 0, 1, 2, 3 or 4

they raise that to the second power in each case

[empty vale]

right, i get that, but that also implies that the remainder of a^2 repeats itself like the one for a?

[stray reef]

yes

and it does

[empty vale]

so, for this particular case, i just make a table with all the possible remainders of (a) when divided by 5, which can only be 0,1,2,3,4 and only look for the cases where the remainder is 2 or 3 then raise it to the power of 2 to them apply the r_5() function to the result and compare with a^2 congrugent -1 mod 5, since mod (-1, 5) = 4 for both cases, i am done?

oh, wait, it's just the application of this property right?

[cerulean wind]

induct on the number of chords, m.

there are two cases:

1. the (m+1)-th chord intersects no existing chords
2. the (m+1)-th chord intersects existing chords

remember, n depends on where the (m+1)-th chord is going, so in the second case, let n be the number of intersections among the already existing m chords, and let n_m be the number of additional intersections you get after adding the (m + 1)-th chord. in the second case, you will want that (m+1) + (n + n_m) + 1 is the new number of regions

[stray reef]

yes with n=2

[stray reef]

no, what you're looking for is when r_5(a^2) = 4.

[empty vale]

oh, alright

thanks ann

[orchid solar]

Does anyone know where I can read the stability proof of mantel's theorem like proving that if G is a graph with n vertices, triangle free and having at least ⌊𝑛^2/4⌋−𝑘 edges, 𝐺 can be made bipartite by removing at most 𝑘 edges.

[weary tiger]

and if it intersects no existing chords then what happens

it creates 1 extra region

[cerulean wind]

right, it divides one already existing region into two, so you only need to add one to the total number of regions

and we always add one because no three lines ever intersect at the same point

[weary tiger]

yes

but, when there is a point of intersection doesen't it add two regions?

[cerulean wind]

i think its better to think about it like this:
for each intersection that your new chord creates, it will divide some number of regions into two regions. the 'original' region is already accounted for, so you just need to account for its new companion region after it gets split.

this is accounted for by adding the number of new intersections coming from the chord you just added, and adding one more for the additional region created when the chord intersects with the perimeter of the circle for the second time

[cerulean wind]

you don't always add two regions for each new intersection

(referring to the pictures above)
if you did, then the picture on the right should have 8 regions (2 new intersections) but it only has 7

drawing the new chord in pieces may make my explanation more clear

[weary tiger]

so in that case the red line creates 3 new regions

it intersects 2 chords

so it creates 2+1 regions

so we can generalize and say

every chord with k intersections creates k+1 regions

but here it says we have n points of n tersections

but not how many intersections per line

but is it safe to assume that n intersections create n+1 regions?

[cerulean wind]

lets say you wanted to add one more chord. it could intersect all of the existing chords, it could intersect none. so the number of new intersections depends on the placement of the new chord. thats why i introduced n_m here

and yes, your generalization is correct. if your new chord intersect at k spots, then you will add k + 1 new regions

k new intersections, 1 new chord

[weary tiger]

ok

[weary tiger]

and what does n_m do?

i didnt understand that part

[cerulean wind]

that is supposed to be the number of new intersections introduced by the (m+1)-th chord

just convenient notation for when you do the inductive proof

[weary tiger]

so n_1 is 1 new intersection

n_2 is 2

etc etc

[cerulean wind]

no, n_m is the total number of new intersections introduced by the (m+1)-th chord.

so if the red chord is the (m+1)-th chord (m = 2 here), then n_m = 2

[weary tiger]

ah i see

and the green line is the 0th chord?

[cerulean wind]

probably best to say (0 + 1)-th chord, so 1st chord (if you assume green was drawn first)

[weary tiger]

yes

so now, do i need to do a summation?

of n_m?

[cerulean wind]

well, i haven't worked out a non-inductive proof

[weary tiger]

oh we use induction

[cerulean wind]

that one does not involve the use of sigma notation

i found it easiest to use induction

[weary tiger]

so you check when m = 1

?

[cerulean wind]

so, how many intersections are there

[weary tiger]

0

1 + 0 + 1 = 2 regions

[cerulean wind]

nice

[weary tiger]

so then you assume it holds for case k chords

k + n + 1

[cerulean wind]

remember, n depends on where the k chords are placed

[weary tiger]

true

[cerulean wind]

but anyways, continue

[weary tiger]

the hard part is how to account for what n depends on (where the k chords are placed)

[cerulean wind]

refer here

[weary tiger]

so you say that m+1 + n+ n_m + 1 is the new number of regions

where n_m is the new number of intersections

but how do i you know how many new number of intersection are created per run through

i refer to a run through as drawing a chord

so for ex: 1st case: draw one chord -> 2 regions created automatically

2nd chord drawn has two cases: it intersects with chord one or does not.

if it does: then it adds n_m (=1) + 1 regions (2 regions)

if it does not: then it adds just one region

so thats the hard part. let's say I give you a list of chords: {a1,a2,a3,a4.... a_m}

and i assign a value to each which corresponds to how many new intersections it creates

a_1 is always 0

a_2 can be 1 or 0

a_3 can be 0,1, or 2

a_4 can be can be 0,1,2,3

a_5 can be 0,1,2,3,4

but all these numbers must add up to n since there are n points of intersection

and as you can see there is a pattern

a_5 can be assigned to (0, 1.... 5-1)

so a_m can be assigned to (0,1,....m-1) new intersections created

now how do i present this mathematically

or, I can say, for example that a_5 can intersect with at most all the previous chords drawn. But we don't know if it intersects 0,1,2,3 or all lines

so thats where i am confused

because I am thinking of it this way, and I can't present it mathematically

[cerulean wind]

you don't need that for any of the previous 'runs'

so, lets say that this formula holds for m chords

say you have a configuration of m chords in a circle now and you are about to add the (m+1)-th chord

[weary tiger]

yes

it can intersect with 0, to m (all) chords

[cerulean wind]

let n be the number of intersections already there

if chord m+1 intersects with nothing, then you just need to add one new region, right?

[weary tiger]

yes

if it intersects with 1, we add 2 regions

if it inetrsects with 2 we add 3 regions

and if it intersects with m we add m+1 regions

[cerulean wind]

let n_m be the number of chords that the (m+1)-th chord intersects with. how many new regions do you create?

[weary tiger]

n_m + 1

[cerulean wind]

okay, so whats the total number of regions now

[weary tiger]

ah i see

im starting to get it

[cerulean wind]

just add it to m + n + 1

so that you get ||(m + 1) + (n + n_m) + 1||

[weary tiger]

we basically fixed a point in time where n intersectiions and m chords are already there so (m+n+1) regions

[cerulean wind]

yes!

[weary tiger]

and then we said, ok we add 1 more chord

i see

so we have $m + n + 1 + \sum_{n=0}^{m} (n + 1)$

[vital dew]

Derivative

[cerulean wind]

there's no sum

[weary tiger]

oh

ah true

[cerulean wind]

n captures all of the intersections when there are m chords. you're only introducing n_m new intersections

[weary tiger]

yeah true

my bad

[weary tiger]

so yes this is the answer

and n+n_m is just the new n

[cerulean wind]

correcto mundo

[weary tiger]

and m+1 is the new m

yes i see how the inductive way works

i was trying to present the non inductive way

but the inductive way is like fixing a point in time

where we already placed our chords and we are adding 1 more

but i would assume the non inductive way is not like that.

the non inductive way would always be looking into the future

but i would like to see how the non inductive way works although the inductive way is very good and comprehensible

the non-inductive way is necessary if we are trying to derive the formula, not prove it

[cerulean wind]

you can think of it as fixing a point in time, but really what's happening is that we have m+1 chords, just remove one of them to drop you down to the case where there are m chords

[weary tiger]

ah so thats the non inductive way

[cerulean wind]

guess and check always counts as a derivation lol

[weary tiger]

true

[cerulean wind]

no, i was describing the inductive way

[weary tiger]

yes

[cerulean wind]

just two different ways to think about it

[weary tiger]

would the way i proposed be the non inductive

although I have not even presented it mathematically

the way i said is we have m chord a_1 to a_m

a_1 intersects with 0

a_2 with 0 or 1 (all)

a_3 with 0 or 1 or 2 (all)

a_4 with 0 or 1 or 2 or 3 (all)

so for each run, we use the previous possibilities PLUS the new possibility

so thats why we need a sum, but what is that sum, I do not know since the difficult part is assigning which possibility (or case) occurs. Although, we know that the cases need to add up to n. So for example, if we know there are 5 intersections and 10 chords. Well, this means means that we can have the sum 0 + 1 + 2 + 3 + 4 + 0 + 0 + 0 + 0 + 0

[cerulean wind]

this is describing a recursive relationship

it will essentially use the same insight that we had in the inductive proof

[weary tiger]

ah i see. But my way is more of the programming way

i dont think it can be expressed mathematically

although, it could be expressed as the number of solutions to a certain equation

so let's say we have 10 chords and 5 intersections

[cerulean wind]

sure, if you let r(m) be the number of regions with m chords, then you have r(0) = 1 and r(m+1) = r(m) + n_m + 1

and you could use this idea to write a program that keeps tabs on the variables you’re tracking

[weary tiger]

yes

it can also be though have as a distribution problem

10 chords, 5 intersections (n) for example

then we have the equation $m_1 + m_2 + \dots + m_{10} = 5$

[vital dew]

Derivative

[weary tiger]

but m_1 to m_10 can only hold a certain amount of numbers

m_1 is always 0

m_2 is always 1 or 2

anyway, i think ill just stick to the inductive method

although I would really like to learn the non inductive method.

maybe i can find one on the internet

the next problem i need to solve is very similar to this one, only except of circles, I am dealing with polygons so the problem will be even harder 💀

[cerulean wind]

good luck!

[weary tiger]

thanks!

[viral ice]

Hello!

¬(a → ¬b) ∧ ¬b → ¬a

How can I prove this expression using only the logical rules?

I already did

1. ¬(a → ¬b) hypothesis
2. ¬b hypothesis
3. ¬(¬a ∨ ¬b) 1. conditional.
4. a ∧ b 3. De Morgan.

But I'm stuck, not sure where to go from here or if I did something wrong.

[sand pelican]

Would it be correct to say "Two sets A and B have the same cardinality if and only if there exists a bijection ) from A to B"?

[viral ice]

Yes

[fossil mural]

well you have a ∧ b, so you can conclude b from that

you also have ¬b

which is a contradiction so you're done, a contradiction implies anything

[sand pelican]

the precise definition of cardinality of a set is the number of elements in a set.

[fossil mural]

that is not precise at all

like what even is a "number"

[sand pelican]

"...the number n of distinct elements in a set, n being a non-negative integer", my bad

[fossil mural]

...ok so what does it mean for a set to have n elements

also by this definition the cardinality of an infinite set just isn't defined?

which would make your earlier statement wrong, there is a bijection between $\mathbb{N}$ and $\mathbb{N}$ but it doesn't really have the same cardinality as itself if it doesn't \textit{have} a cardinality

[vital dew]

bee [it/its]

[sand pelican]

I see, so my "precise" definition of cardinality was wrong, which makes my initial claim wrong, too

[fossil mural]

well your initial claim is correct with the actual definition of cardinality, it's just wrong with the incorrect definition you gave

[sand pelican]

Yes thats what I mean

[versed granite]

Integers:
Multiplication of integers:
Show in general that the definition of multiplication is independent of the choice of representatives from an equivalence class.

This was my idea so far:
$$(a,b)\sim(a',b') \wedge (c,d)\sim(c',d')$$
Def:$$a+b'=b+a' \wedge c+d'=d+c'$$
Def: $$(a,b)\odot(c,d)=(ac+bd,ad+bc)$$
z.z.: $$(a,b)\odot(c,d)\sim(a',b')\odot(c',d')$$
$$= (ac+bd,ad+bc) \sim(a'c'+b'd',a'd'+b'c')$$
$$=(ac+bd)+(a'd'+b'c')=(ad+bc)+(a'c'+b'd')$$

now i am kinda stuck and dont know how to finish the proof

[vital dew]

Benschko

[versed granite]

We also got a hint:

At one point we should add $b'd+a'd$ to the equation.

[vital dew]

Benschko

[heady oak]

this is some typo right?

[fossil mural]

yes, it should be $10^N-1$

[heady oak]

should be 10^{N} -1

[vital dew]

bee [it/its]

[fossil mural]

and you can see with the example $999 = 10^3 - 1 \neq 10^{3-1} = 100$

[vital dew]

bee [it/its]

[heady oak]

right

probably the might have fixed in newer editions.

[quiet eagle]

I have read the term "incidence vector". How do you put all the Information of an incidence matrix into a (column) vector, without just stacking the whole incidence matrix into one column? Or maybe incidence vector means something different?

My solution: combine each v,w to e ={v,w}

[viral ice]

Mathematicians say that "a sentence P is stronger than a sentence Q" if Q is true always when P is true, but not the other way around. (In other words, "P is stronger than Q" means that P -> Q is always true, but Q -> P is not true, in general.) Create the truth tables to show that:

a v b is stronger than a

How can i create this truth table? I used variables "a", "b", "a ^ b", "a ^ b -> a", "a -> a ^ b" o show that a v b is stronger, is that correct?

My professor did this to show that a ^ b is stronger than a, so I only changed the or to and to create the truth table, is this correct?

[weary tiger]

Anyone can give me hint

[cerulean wind]

try going from 4 to 5

see if you notice anything

[twilit sundial]

ah this one’s a classic

consider the nC4 term separately from the (n-1)C2 term

[cerulean wind]

i would try to find a recurrence relation (an alternative would be to use v - e + f = 1 and solve for f)

[raven ember]

hey

how do we approach this?
the question is whether is argument is valid or no

[plain shoal]

we have f:A-->B and h:B--> A and h ∘ f is Inverse function how to prove that f ∘ h is inversible too. how can this be proved

[stray reef]

@plain shoal what language did you translate this from

[plain shoal]

hebrew

[stray reef]

also this problem is nonsensical as stated -- if f and h are both A -> B, then f ∘ h doesn't exist

[plain shoal]

oh sorry

[stray reef]

might want to post the original hebrew in case there's somebody here who speaks it

[plain shoal]

h from b to a and f from a to b

[plain shoal]

i dont have it it was on my exam yesterday

[stray reef]

so you have f: A -> B and h: B -> A, and h ∘ f is an invertible function

is that right?

[plain shoal]

yesh

[stray reef]

i don't think it follows that f ∘ h is also invertible

[plain shoal]

we have to prove that f ∘ h is also invertible

[stray reef]

let A = {1}, B = {2,3,4,5,6}, f: A -> B defined by f(1) = 2 and h: B -> A defined by h(anything) = 1

then h ∘ f is the identity function on A, but f ∘ h is the constant function 2 on B. and this is not invertible.

so either you are missing something or your professor is evil

i think the first option is much more likely

[plain shoal]

I can't prove it by this?
because it is invertible so it is onto and one on one, and if it is onto, for every b we have a and for every a we have b, because the function h ∘ f goes from A to A and this can prove that both f and h is onto, and if we have an invertible function and one of the base functions is onto then the other has to be one on oneso i did it for f and then did it for h and they proved that both h and f are onto and one on one so f ∘ h has to be invertible

[plain shoal]

nvm i understand your point

thank you for helping

[hard citrus]

the proof I'm trying to do is "show that when adding two same signed 2's complement numbers, we can ignore the overflow bit"
when trying to prove it i got to the conclusion that it's right only when in the solution the two MSB are the identical (i.e. 11 or 00) but i cant prove it for the cases where these are not identical (01 or 10)

can someone explain to me if they noticed something I'm missing?

[stray reef]

doesn't the most significant bit tell you the sign of the number tho

[weary tiger]

For which thing?

The square to pentagon?

The only thing I notice is that the square has only one diagonal coming out of each edge

And the pentagon has two

Hexagon has three

[twilit sundial]

hint: what happens when you draw in a new diagonal and it intersects an existing diagonal in the interior of the polygon?

[weary tiger]

It creates 2 more regions

A diagonal with k intersections creates k+1 regions

I am solving a recurrence relation, and it seems that it is hard to get the variables if I don't rearrange the roots. (r - 1)(r - 3)(r + 2) is hard, while (r - 1)(r + 2)(r - 3) is not

[stray reef]

wym "get the variables"

why does rearranging the factors make any difference at all @weary tiger

[weary tiger]

You see, one of my classmate factored
an = 2an-1 + 5an-2 - 6an-3 or (x³ - 2x² - 5x + 6 = 0)

his result is (r-1)(r+2)(r-3)

Using synthetic division, I also did the process, but my result is
(r - 1)(r - 3)(r + 2)

My roots are 1, 3, and 2.

I am not sure either; my algebra is just awful, but it appears that I can easily get the variables if I rearrange the roots to (1, 2, 3). I heard that arrangement doesn't matter, but I think when it comes to recurrence relation (homogenous), it seem that it affects the result or difficulty.

[stray reef]

1, 3 and -2?

you two have achieved the exact same factorization. where is this difference that you claim exists?

i do not see any difference at all.

and again

what does "get the variables" mean

your notation has some minor hiccups and so does your wording, and i still do not know what you mean by "get the variables". are you translating from another language?

[weary tiger]

This is for a second-order recurrence relation, but in this part.

[stray reef]

oh, so the part where you actually write down the sequence as $$a_n = c_1 r_1^n + c_2 r_2^n + c_3 r_3^n$$ that's the one you're talking about?

[vital dew]

|Ann⟩

[weary tiger]

a0 = 7
a1 = -4
a2 = 8

By using my roots, my result is a fraction (this is the part where I start to wonder if I am doing it right)

[weary tiger]

Yes

[stray reef]

and you're saying that rearranging which root of the characteristic equation comes first somehow affects the difficulty of subsequent computations at all?

I start to wonder if I am doing it right
gonna need to see ALL of your work, formatted in a legible and follow-able manner.

[weary tiger]

Yes, I believe so.

[weary tiger]

Alright, after this assignment. I'll show you

I just need to finish this cause I've been trying to solve that Issue for like 2 hours straight

[weary tiger]

@stray reef I saw that he obtained those variables using a different method; perhaps I ought to first ask him how he accomplished it.

[graceful canopy]

hey, i have a little question there, can i just say for #21, that the premisses are false. so the implication is true ?

since 0 is not greater than 1 ?

[stray reef]

the premise of "n is a positive integer >1" is false

so yeah, P(0) is true and exactly for the reason you stated

(vacuous truth)

[graceful canopy]

ok yeh pref

thx

[graceful canopy]

I have a question concerning functions, how f(x) Z->Z=x^{3} is onto?

like x^{3} = y but. how sqrt3(y). is element of Z ?

really?

ohh yesss

ayt thx

i am dumb

but its one-to-one right ?

ayt thank you

[ocean socket]

Do we consider the empty set as "a family of non-empty sets"?

[brave rock]

Sure

It is a set (i.e., a family) and every element in it is a nonempty set

[graceful canopy]

the empty set is always a subset to any non empty sets right ?

[brave rock]

Every element in it is also a black dog that lives in shropshire

[brave rock]

The empty set is a subset of all sets, yes.

It is not an element of all sets, n.b.

But it is a subset.

[graceful canopy]

but if we have the set { {} }

[brave rock]

The set containing the empty set, yes

[ocean socket]

so by the axiom of choice there exists a choice function on the empty set? i am seeing differing answers online.

[brave rock]

Yes, it is the unique map from the empty set to the empty set.

[ocean socket]

well, alright thanks just wanna make sure. 👍

[brave rock]

Did you have a follow-up to this?

[graceful canopy]

nono i was gonna say. the empty set is an element of this set

but can we say that even the empty set is a subset to this set, because as we said the empty set is always a subset to any sets?

[brave rock]

Yes and yes

[graceful canopy]

is this funciton onto?

and srry its in french

like I have x+y = a and x-y =b. but then after I have like y = (a-b)/2. which is not an integer

[opal crescent]

oui en effet c'est mal barré pour que ta fonction soit surjective

[graceful canopy]

ahh nice

[opal crescent]

regarde un peu 2y = a-b

[graceful canopy]

exact

so c pas surjective parceque ca. appartient pas au Z

[opal crescent]

si tu veux que (a,b) soit atteint par ta fonction, ça te force a-b pair

[graceful canopy]

ah donc jdois faire les cas ou pair - pair, impair- pair, ...

[opal crescent]

nan

mais t'as des contre-exemples tout faits pour la surjectivité maintenant

[graceful canopy]

mais j arrive pas comment trouver des contre exemple, genre si j ai 2y = a -b ?

jfais comment pour trouver un contre exemple avec ca ?

[opal crescent]

^^

[graceful canopy]

ahhh oui

ptn

[opal crescent]

il se passe quoi si a-b est impair à ton avis

[graceful canopy]

mhmm. c bizz si je prends a = 4 et b = 3

a-b est impair, mais

(7,1) ?

ahhh non c la sortie ca

[opal crescent]

h(7,1) c'est (8,6)

dommage

[graceful canopy]

j y arrive pas

jpeux pas que la diff entre les deux soit impair

ahhhhhh jpeux juste dire la sortie (5,6)

c impossible a couvrir

[opal crescent]

oui enfin 4, 3 c'était très bien aussi

sure

[graceful canopy]

yaaaahhh,

ok parfaiit merciii!

[graceful canopy]

petite question comme ca, t de montreal ?

est ce que t a poly par hasard ?

[opal crescent]

nope

[graceful canopy]

ah merde

[opal crescent]

je suis pas mal loin de montreal

[graceful canopy]

ahh okok bon bah jme suis dit peutetre

[opal crescent]

à des milliers de km

[graceful canopy]

t de france ?

[opal crescent]

yeah

[opal crescent]

tu peux toujours tenter ta chance dans les channels de discute

il y a + de monde anyway

[graceful canopy]

true, mais bon jvais arrter de parler de ca ici haha

[versed granite]

Show that the relation (𝑎, 𝑏)~(𝑐, 𝑑) : ⇔ (𝑎 + 𝑑, 𝑏 + 𝑐) is an equivalence relation. (Reflexivity, Symmetry and Transitivity)

I am stuck with transitivity :

$$(a,b)\sim(c,d)\Leftrightarrow(a+d,b+c)$$
$$(c,d)\sim(e,f)\Leftrightarrow(c+f,d+e)$$
We have to show that:
$$(a,b)\sim(e,f)$$

[vital dew]

Benschko

[grand totem]

(𝑎, 𝑏)~(𝑐, 𝑑) : ⇔ (𝑎 + 𝑑, 𝑏 + 𝑐) doesn't make much sense, it's supposed to be (𝑎, 𝑏)~(𝑐, 𝑑) : ⇔ 𝑎 + 𝑑 = 𝑏 + 𝑐

And a hint for the transitivity proof would be to add the two equations together that you get from (a,b) ~ (c,d) and (c,d) ~ (e,f) and see if you can cancel some terms to end up at a + f = e + b

[versed granite]

Hmmm maybe my teacher made a mistake. I am going to ask her. thanks

and thanks for the hint.

it works like that really well

[twilit sundial]

as a start, look at how the LHS behaves

[deep vector]

what is LHS?

[coral parcel]

Left-hand side.

[deep vector]

ahhh okey! Thank you

[deep vector]

He tried to see that, but he couldn't come up with anything.

[coral parcel]

Well, start by plotting sketching it.

[pearl ermine]

hey i need help with this -> Caitlin and Olivia are playing a game. Caitlin starts with a pile of 1000
pennies and Olivia starts with a pile of 500
pennies. On each turn, one of them flips a quarter. If the quarter comes up heads, Caitlin gives Olivia a penny. If the quarter comes up tails, Olivia gives Caitlin a penny. The game ends when one of them runs out of pennies. (It will probably take a while.) What is the probability that Caitlin wins? answer comes out as 2/3 if i boil the situation down to Catilin having 2 coins and Olivia having 1 coin, but i am not sure if this generalization is employable here.

[stray reef]

ok so just to format that in a more readable manner:

_Caitlin and Olivia are playing a game.

• They each start with a number of pennies: Caitlin starts with 1000, and Olivia with 500.
• On each turn, they flip a coin. On heads, Caitlin gives Olivia a penny, and on tails, Olivia gives Caitlin a penny.
• The game ends when one of them runs out of pennies.

What is the probability that Caitlin wins?_

(newlines are a thing, btw. shift+enter)

anyway

here is how you can think about this game

point 1: the game state is entirely determined by Caitlin's balance, since there's a fixed number of coins in the game (1500) and they only change hands, but no coins are brought from elsewhere.

point 2: caitlin wins precisely when her balance hits 1500.

point 3: it will be productive to think about not just caitlin's chances of winning from her actual starting balance (1000), but from all possible balances between 0 and 1500 inclusive.

@pearl ermine

1. do you understand these points?
2. would you like me to elaborate further on point 3, or do you want to try it yourself?

[pearl ermine]

i didnt understand pt 3

[stray reef]

ok, so

imagine caitlin wins the first round, and her balance goes from 1000 to 1001.

after this, her probability of winning the game is exactly the same as if she had simply started the game with 1001 coins.

do you agree or disagree with this?

@pearl ermine ?

(i have more stuff to say after this but i need you to be on the same page about this simple point)

(dont overthink it)

[pearl ermine]

yea but it it because of some sort of symmetry?

[stray reef]

no symmetry here

its more like the chance of caitlin winning from, say, 1001 coins are the same no matter how she got to 1001 coins.

(nothing special about the number 1001 obviously)

[pearl ermine]

so the probabilities are independent of the number of coins Catilin or Olivia have, like does the probability remain same for catilin 1001 and olivia 499? and so on?

[stray reef]

"caitlin 1000 and olivia 499" cannot happen.

also no

you misunderstand

the probability of caitlin winning does depend on her balance

but it depends on only that, and nothing else

do you see what im saying

yes or no

[pearl ermine]

so it doesnt depend what Olivia has at all?

[stray reef]

olivia's balance is always 1500 minus caitlin's.

so considering her balance doesn't give us any more info.

[pearl ermine]

k, but why does catlin winning, depend only on her balance? (sorry if the questions seem obvious, im new to these type of questions, tying to wrap my head around)

[stray reef]

the coin that they flip is fair and the result of each flip is independent of any past flips.

so there's nothing else that could affect the chances of caitlin winning.

agree or disagree?

[pearl ermine]

yea but what if olivia has greater number of coins than katlin, at some point in the game, wont this coin ratio affect catlins chances of winning?

[stray reef]

so let me get this clear

you're asking whether, say, caitlin's chances of winning are the same in the following two scenarios:

1. Caitlin gets to 1100 coins without losing too much
2. Caitlin first loses coins all the way down to 300, but then regains her way back to 1100

is that what you're asking? yes or no

(these numbers have no sacred significance. i just made up an example of two scenarios where caitlin got to the same total but by different paths)

[pearl ermine]

yes in both cases, why would her chances of winning be the same, one-> at a point when she has 300 coins (< olivias coins), then at a point when when she has 1100, (> olivias coins)

[pearl ermine]

i know

[stray reef]

im not saying "caitlin has the same chances of winning from a 300 coin balance as she does from 1100"

im saying that at any point in the game, caitlin's chances of winning depend ONLY on her CURRENT balance, but not on any past ones!

do you agree with this or not?

[pearl ermine]

ah i see yes

[stray reef]

ok

now that we're finally in agreement on this

the idea i wanted to suggest is as follows:

for each k between 0 and 1500 inclusive, denote by w(k) the probability of Caitlin winning when starting from a balance of k coins.

our goal will be to find the value of w(1000).

we know w(0) = 0 and w(1500) = 1, and we know something else that i will tell you after this.

do you understand why w(0) = 0 and why w(1500) = 1?

[pearl ermine]

is it because she already won the game if she has 1500 coins if w(1500) - 0 so she wins 100 percent of the time and if w(0) olivia is the bound to be the winner, so catlin has 0 chance of winning in that case?

[stray reef]

your wording is broken in several places, but yes.

ok

now here comes the hard part.

for each $k$ from 1 to 1499, we have the following: $$w(k) = \frac{1}{2} w(k-1) + \frac{1}{2} w(k+1).$$ do you understand why this is so?

[vital dew]

|Ann⟩

[pearl ermine]

all i understood from this equation is w(k) is the probability of Catlin winning, rest went over my head

[stray reef]

you cannot just omit the most important words from my definition like this!

w(k) is the probability that Caitlin wins when she starts with k coins!

[pearl ermine]

sorry sorry

[stray reef]

do you understand the meaning of w(k) now?

[pearl ermine]

i meant that yea

yes

[stray reef]

so then are you saying that w(0)=0 and w(1500)=1 also went over your head?

or do you understand those.

[pearl ermine]

yes yes , i had bad choice of words there

[pearl ermine]

i understood them, i even elaborated how

[stray reef]

you said

rest went over my head

i thought this meant i had to re-explain some shit.

[pearl ermine]

no no

i am talking about the right hand side of the equation

[stray reef]

ok so basically then this

all i understood from this equation is w(k) is the probability of Catlin winning, rest went over my head
was a very long way of saying "no, i dont understand that"

ok

do you know the law of total probability?

[pearl ermine]

not familiar with it

[stray reef]

$P(A) = P(B) \cdot P(A|B) + P(B')\cdot P(A|B')$

[vital dew]

|Ann⟩

[stray reef]

this is the version that we need for our purposes.

does this look familiar?

[pearl ermine]

does this have some connection with P(A U B) = P(A) + P(B) - P(A ∩ B)? this is also another formula used in probabilities.

[stray reef]

very distant, if any.

we cannot proceed if you do not understand this law though.

it is impossible to bypass.

[pearl ermine]

k what does the law state?

[stray reef]

i have already told you

but to elaborate on the notation a bit:

for any two events $A$ and $B$ with $P(B) \neq 0$ we have $$P(A) = P(B) \cdot P(A|B) + P(B')\cdot P(A|B')$$

[vital dew]

|Ann⟩

[stray reef]

is this what you wanted me to say?

[pearl ermine]

yes continue

[stray reef]

in our case, A is the event "caitlin wins" and B is the event "the coin shows heads"

starting from a balance of k coins, there are exactly 2 ways for Caitlin to win:

• get a tails [1/2], then win from k+1 coins [w(k+1)].
• get a heads [1/2], then win from k-1 coins [w(k-1)].

[pearl ermine]

okay

[stray reef]

do you understand $$w(k) = \frac{1}{2} w(k-1) + \frac{1}{2} w(k+1)$$ now?

[vital dew]

|Ann⟩

[pearl ermine]

yes i do

sort of recursive

[stray reef]

you can rearrange this equation into the following:

w(k+1) - w(k) = w(k) - w(k-1)

and that gives you that w(0), w(1), ..., w(1499), w(1500) is an arithmetic progression

[pearl ermine]

yes it does rearrange into that, but how does it generate an arithmetic progression?

[stray reef]

do you know what an arithmetic progression is

y/n

[pearl ermine]

yes i know

but how does this boil down to arithmetic progression?

[stray reef]

well, what is an arithmetic progression according to you?

[pearl ermine]

numbers increasing by the same amount for example 2, 6, 10, 14 ......

they share the same common difference

[stray reef]

yeah, so

w(k+1) - w(k)
and
w(k) - w(k-1)

are both differences between adjacent terms in the sequence

and our equation says they're the same

and in fact you can apply it over and over to say e.g. w(2)-w(1) = w(3)-w(2) = w(4)-w(3) = w(5)-w(4) = ...

do you see now?

[pearl ermine]

ah i see

then

[stray reef]

w(k) is an arithmetic progression, its 0th term is 0 and its 1500th term is 1

it should be almost obvious what w(k) will look like

[pearl ermine]

sum of all the terms from 0 to 1500?

[stray reef]

what? no

nobody even brought up adding any of them together...

[pearl ermine]

i meant probabilities

[stray reef]

but again nobody's saying to add them together

.. w(k) = k/1500

it is just this

nothing more nothing less

[pearl ermine]

why did u divide k by 1500? is it because 1500 is the total number of coins?

[stray reef]

w(0) = 0
w(1500) = 1

what linear function passes through (0,0) and (1500,1)?

its just this

dont overthink it

youre overthinking it rn every single step

[pearl ermine]

trying to understand thats why im asking questions on the way

ok thanks, so the result is 2/3, but why is the result same for katilin having 1000 coins and olivia having 1000 coins, the same as katlin having 2 coins and olivia having 1 coin?

[stray reef]

thats... just how it works out?

like if you want to do it in full generality you will find that if Caitlin starts with x coins and Olivia with y coins then Caitlin's chance of winning is x/(x+y)

[pearl ermine]

is there any concept of symmetry here that cascades from the result of 2 coin : 1 coin -> to 1000 coin : 500 coin (bothh are 2/3), or is it jusut bceause how the formula works out?

[coral parcel]

It's just how it works out.

At least there's no "deeper reason" that is reliable enough that it's safe to trust it for other similar-looking problems.

[pearl ermine]

oh okay thanks

[pearl ermine]

thank you for taking you time and explaining the solution.

[mild juniper]

for this one, it suffices to show that (a,b) exists by the axiom of pair right? since (a,b,c) = ((a,b),c) and so on?

[coral parcel]

There are different possible definitions of how to represent (a,b,c) and (a,b,c,d) with pure sets, but if yours is (a,b,c) = ((a,b),c), then your plan is correct.

[mild juniper]

yay

[weary tiger]

anyone know how to solve this combinatorial problem

or just give me a hint

first give me a hint actually

and then, I'll try for 20-30min and I will be back

sometimes hints can work very well haha

[coral parcel]

Probably something like add the vertices of the polygon one by one, and keep careful track of of many of the old diagonals intersect each of the new diagonals in each step as you go along.

(I haven't done this myself, but it's the first thing I would attempt to make work).

[weary tiger]

what do you mean by add vertices?

can i use induction?

[coral parcel]

For example, imagine you draw the n=5 figure by first drawing an n=4 one (the black lines in this image) and then add a new vertex and the red edges. This introduces 3 new faces outside the old figures and makes 2+2 new cuts inside the old figure, which increse its number of faces by 4.

(Yes, this would end in a proof by induction on n).

[weary tiger]

ah i see

let me try

like how am i supposed to know how to do that lol

like i didnt even know i could do that hahah

so difficult

[coral parcel]

Perhaps try to find a combinatorial argument that the number of the new intersection points (which I've marked in green here) is exactly (n-1) choose 3? And for each of those intersection points, one of the existing faces from the n=4 case get split into two.

[weary tiger]

hmm

ok

from what i see thinking about it this way is

#1, we always draw the n-1 shape first

#2 for n=5, we have initially 2 lines diagonals (as in the n=4), but then when we draw the n=5 shape, we add 2 diagonals + 1 that was used to draw the n=4 shape

so for n=6, we draw the n=5 shape, which gives us 9 diagonals (from the n=5), then when we convert the shape to n=6, we get 3 added diagonals + 1 that we used to draw the n=5 shape

so we are always adding the diagonals from the n-1 shape to the n shape

now in terms of interior regions, this is harder.

we always have the regions from the previous shape inside

now for n=5, we add 2 diagonals, which intersect 3 lines. We know that a line with k intersections adds k+1 regions

so each line has 2 intersections

2+1=3

3+3 + 6

6+4 = 10

so we have an inductive relationship

fix a place in time, where an n-gon has been drawn

we are adding the n+1-gon

[coral parcel]

Part of my suggestion was to count the new pink regions separately from the new regions that arise in the blue areas -- unless I'm mistaken, these turn out to correspond to the two binomial coefficients in the problem. A line with k intersections adds just k new blue regions, rather than k+1.

[weary tiger]

ah

well idk

why the blue regions?

[coral parcel]

Each of of the new slices through the blue are ends in a green dot in the end of it that's nearest to the new vertex.

[weary tiger]

i dont understand

[coral parcel]

Each of the purple arrows here adds a new blue region. Each arrow ends at a new intersection, and each new intersection has an arrow ending at it. So the number of new blue areas is the same as the number of new intersections.

[weary tiger]

ok

• the 1 red area created per line

but we dont count that or we do but its implied?

[coral parcel]

The sum of the red regions added in each step becomes the (n-1 choose 2) term in the final result.

The sum of the new blue regions becomes the (n choose 4) term.

[weary tiger]

how?

[coral parcel]

In the final n=umpteen figure, each internal intersection has been the endpoint of a purple arrow in exactly one step.
(Assuming we start at n=3 instead of n=4 as the problem suggests).
How many internal intersections are there in an n-gon?

[weary tiger]

n

[coral parcel]

No.

[weary tiger]

for n=5 there are 5

but for n=4 there is 1

[coral parcel]

Note that I have as good as claimed there are (n choose 4) of them.
I'll leave you some time to see why that is the case.

[weary tiger]

ah but how do the number of lines have to do with the number of regions?

[weary tiger]

n choose 4 is tough to understand tbh

idk im not good with shapes

i cant imagine the shapes

but i can imagine objects like $a_1, a_2$ etc

[vital dew]

Derivative

[coral parcel]

(Hint: if you stand at an intersection there are 4 directions you can go in, each leading to ...)

[weary tiger]

a vertex

so i can establish a bijection or something

[weary tiger]

well i am lost hahah

why is this problem so difficult?

[coral parcel]

Can you see why (internal intersection points) correspond to (unordered sets of 4 vertices)?

[errant bear]

i think it would be helpful for derivative to replicate this but with a hexagon

[weary tiger]

i tried

but i dont understand my own drawing

[weary tiger]

i cant unfortunately

maybe my mind does not want to see

let me try to see

yes i do see

because for a hexagon each intersection point, we can move to 4 vertices

I SEE

yesss

so for example for a hexagon

the internal intersection point can move in 4 directions

for each internal intersection points, we create a 4 letter combination

and there are 6 object

$\binom{n}{4}$

[vital dew]

Derivative

[weary tiger]

YES

and for the INTERNAL INTERSECTIONS a line with k intersections creates k regions!!!!

so there is a bijection!

therefore the $\binom{n}{4}$ lines create $\binom{n}{4}$ regions!!!!!!!!!!!!!!!!!!!!!!

[vital dew]

Derivative

[weary tiger]

so we have the first part of the argument

now for the second one

[weary tiger]

btw how did u draw this pentagon so nicely?

[coral parcel]

I copied your image and drew over it in Gimp.

[weary tiger]

ah ok

[weary tiger]

so did i get the first part of the argument?

[coral parcel]

Yes.

[weary tiger]

but are you sure i got it? so each intersection creates a 4 object sequence, and the total intersections is n choose 4 for the internal region.

is the total intersection of internal region n choose 4?

[coral parcel]

If you didn't get it yet, I'm afraid you need to get the rest of the way without my help; I need to sleep now.

[weary tiger]

wait 1 sec please. because im actually not sure, are there n choose 4 intersection in the internal region?

ah yes u r right

good night

for the second part ill ask other helpers

<@&286206848099549185>

please help me with the second part of this problem

ok

so i trying to prove it combinatorially

as you can see with our conversations, we basically drew the pentagon from a 4 side polygon

like so

and we observed that in the internal region (blue region), there are $\binom{n}{4}$ intersections

[vital dew]

Derivative

[weary tiger]

also, every red line (new line), has 2 intersections in the blue region and adds 2 new blue regions

so a line with k intersections adds k blue regions

@blissful wagon do u see?

ok

thanks

welp i am screwed

i memorized the krebs cycle

thats not very good mitochondria is not powerhouse

mitochondria is where the reactions happen

it generates ATP from chemiosmosis

from the electron transport chain

so why cant you solve this question?

[cerulean wind]

this is not productive/constructive

[weary tiger]

well i am close to an answer

[cerulean wind]

just ignore him

[weary tiger]

its just the $\binom{n}{4}$

[vital dew]

Derivative

[weary tiger]

this is the amount of intersections in a polygon with n sides

but i dont see how this equals the amount of regions on the internal (blue) region

yes, each line with k intersections creates k blue regions.

[coral raven]

<@&268886789983436800>: @blissful wagon

[fossil mural]

...nobody was intimidated, and you didn't demonstrate any intelligence

[fossil mural]

other than like, ability to produce english sentences

[hazy pine]

stop feeding the troll and just ping mods next time

[weary tiger]

and since there are $\binom{n}{4}$ intersections, then aren't there $\binom{n}{4}$ blue regions created?

[vital dew]

Derivative

[weary tiger]

but, created from what?

from the previous n-1 polygon

idk

but if n=5 then 5C4 is 5

but it does not create 5 regions, it creates 4??

it does not make sense

i dont see how the $\binom{n}{4}$ comes in

[vital dew]

Derivative

[weary tiger]

for n=5 those 5C4 intersections create

[coral raven]

hmm

maybe it's just like

for a given intersection, how many regions have that intersection as a vertex?

[weary tiger]

4

always

ever intersection connects to 4 vertices

whats the difficulty level of this problem?

like nobody could solve it 🤣

if nobody here can solve it then how am i supposed to solve it 🤣 im just a simple man

i have inundated this channel the past few days hahaha

welp

thats that

[weary tiger]

is anyone available?

maybe tmr morning

good night all!

[coral parcel]

After sleeping on this, I've concluded that it was a detour of me to speak about blue and pink regions like this. Scratch all that, and start over, without even induction:
We start by just the outer edge of the polygon, and then add the inner diagonals in a random order. Each time we add a diagonal, draw an arrowhead where it crosses a diagonal we've already drawn, as well as in one of the ends of the diagonal. This way we can see that each arrowhead corresponds to cutting one region into two. Since we started with a single region, the number of regions at the end is one more than the final number of arrowheads.

Each intersection between inner diagonals has exactly one arrowhead (since one of the two intersecting diagonals that was drawn last, and when we drew that we added an arrowhead at the intersection). I've claimed that there are (n choose 4) of these intersection, though it sounds like you still need to convince yourself of that.

The vertices of the polygon don't all have just one arrowhead -- some have none, some have more than one. But each inner diagonal contributed exactly one of these arrowheads, so we can count these arrowheads by counting the inner diagonals themselves.
There are (n choose 2) - n inner diagonals (why?), so the final number of regions should be

1 + (n choose 4) + (n choose 2) - n
Now it's a matter of algebra to prove that this is equal to (n choose 4) + (n-1 choose 2).

[silent pine]

I know this is an oddly specific question, but does anybody know a place where I can find exercises with answers for relations, more specifically ones about finding transitive closure? Either that or a calculator so I can make up ones myself and check them. I wanna practice for my exam but cannot find any exercises

I've been looking into random books like Rosen's Discrete mathematics and its applications but it doesn't have solutions so I have no idea whether I'm solving stuff right or not

[coral parcel]

I don't have any particular suggestions for exercise sets, sorry. But a random piece of advice if you're finding transitive closures in particular challenging:
One pitfall students often fall into here is to try to work out the solution simply by staring at a list of pairs and following rules. For this kind of task it is vitally important that you draw a picture of the situation with one dot on the paper representing each element of the set and an arrow between the elements of each pair.
Once you have made that drawing, reading out the transitive closure is just a matter of asking yourself for each point, which points can I reach from here by following one or more arrows?
For problem sizes that are likely to show up in exams, this can generally be done by eye, and that is both faster and less error-prone than applying rules symbolically to a list of pairs. (You may need to go through a few attempts at laying out the drawing such that related points are near each other on the paper -- but that will still be faster overall).

[shell yew]

why n choose 4?

wait

I see

so for every 4 points

there is always one set of intersecting lines

[coral parcel]

Any pair of intersecting diagonals can be specified uniquely by stating the endpoints of those diagonals.

[shell yew]

makes sense

[coral parcel]

Yes.

[shell yew]

I was just thinking about how not all diagonals intersected

but I realised that that wasn't a problem anyway

[shell yew]

(above the n=5 case of course)

[shell yew]

wait there's a problem

no wait

is there?

hold up

yeah ok not a problem

just want to mention that there are cases where it's not just the vertices that have multiple arrowheads

ok I''ll remove this

sorry

sorry for the ping
I didn't realise the "no 3 diagonals are concurrent part until now"

but what if we allow that though

like what if we counted the regions of a regular polygon

[silent pine]

Thanks. I do try both methods usually, the thing with drawing dots is that I sometimes get confused and don't notice possible connections but generally it is indeed a lot easier than doing a ton of compositions until you reach one that is equal to some of the previous ones.

[weary tiger]

here you drew 2 diagonals

and the rest are arrowheads

so the arrowheads represent the regions created?

i was thinking of establishing a bijection

[coral parcel]

There's probably more than one way to do it, but this is what I could come up with. ¯_(ツ)_/¯

[weary tiger]

i found one way

in the problem before this one

it said that the number of regions created by drawing m chords with n intersections is m+n+1

[coral parcel]

(Actually, there's definitely more than one way to do it. A completely different way would be to say in the final graph we have (n choose 4) nodes of degree 4 each and n nodes of degree (n-1) each, then apply the Euler characteristic to find the number of faces and do algebra to show the result equal to the desired formula).

[coral raven]

yeah that's what i was thinking with the comment about 'how many regions to each intersection'

[coral raven]

per oeis it's nice for odd polygons but gets messy for even

[weary tiger]

your answer is actually an extension of another problem

you incribe the polygon in a circle

Can someone help me confirm this?

[stray reef]

well, this typesetting leaves a lot to be desired

but also 2^2 * 1^2 isn't 8.

[weary tiger]

oh crap, I made a mistake.

[weary tiger]

@coral parcel you incirbe it in a circle. I proved before that the number of regions created in a circle is m+n+1 where m is the number of chords, and n is the number of intersections. We established that there are n choose 4 intersections. There can also be n choose 2 chords formed in the polygon. but we need to subtract by the n regions formed by the adjacent vertices. so we get: $\binom{n}{4} + \binom{n}{2} + 1 -n$

[vital dew]

Derivative

[weary tiger]

and you get exactly what you proposed

i just said it in a different way

[coral parcel]

Ah, yes, if you already have the m+n+1 result, then that was essentially what my arrowhead argument was there to establish.

[weary tiger]

yes i had forgot to say that

i didnt know that this problem was an extensionn of the previous result

live and learn

these problems are very very difficult

[weary tiger]

anyone good with putnam questions?

[coral parcel]

#competition-math, also https://dontasktoask.com/

[weary tiger]

ok thanks

what does this mean in math

For example: $d | n^2$

[vital dew]

Derivative

[weary tiger]

what does that vertical bar mean

[brave rock]

Divides

So a | b is read "a divides b"

Now this may seem a bit odd, but this has a different definition to the one you may be thinking of.

$a \mid b$ is defined to mean that there exists an integer $z$ such that $az = b$.

[vital dew]

Boytjie

[brave rock]

If you are doing a first course in proofs or number theory, this definition will have been given to you, and you should check through your notes.

[weary tiger]

ok thanks

i am not taking a course in proofs or number theory

i am doing combinatorics

[rapid shale]

$ \binom{n + r - 1}{r}

[weary tiger]

yes

thats the number of solutions to an equation in the form x_1 + x_2 + ... + x_n = r

which is like putting r identical objects into n distinct boxes

[rapid shale]

can you explain me how this formula came, it's actually Combinations with repetition formula.

[weary tiger]

it comes from binary

let me show you

[rapid shale]

i don't wanna cram this formula, so i thaught it's better for me to know how this formula came. I'm unable to think of it.

[weary tiger]

yes let me show you

its bijection from binary

1 is the bar seperating the boxes

and 0 represents the identical objects

notice there will be a total of r + n -1 (objects and bars)

and we just choose r 0's for the objects

[rapid shale]

thanks!

[weary tiger]

no problem

[weary tiger]

can i get some help with (i) so that I can do (ii) myself

i know how need to use modulo

theres something with congruence

[stray reef]

list all the possibilities of remainders for a, b and c mod 3 which add up to 0

[weary tiger]

like a,b,c are congruent mod n or something

[stray reef]

for example, 0, 1 and 2 would work. or 2, 2 and 2

[fair cliff]

hi, anyone knows about game theory here

desparately needs help

[weary tiger]

no repeats allowed

a b and c are different

[stray reef]

sure but they can still have the same remainder mod 3 while not being the same number.

like {2,65,122} would be a valid set

[weary tiger]

i see

i need to learn modulo

since i never took a course in discrete math

[weary tiger]

can you show me the notation?

so basically, i need all possibilities where the remainders of a mod 3 = 0 and b mod 3 = 0 and cmod3 = 0

[stray reef]

not only those tho.

idk what you want "the notation" for

[weary tiger]

for the equation i need to set up

i dont know what equation i need to set up

here is a proposed solution

There are 2 cases to this problem

Case 1: All numbers are congruent mod 3. There are 3 congruence classes with 664 numbers

this is $3\binom{664}{3}$

[stray reef]

there are more than 2 cases actually

[vital dew]

Derivative

[stray reef]

well ok

[weary tiger]

then case 2 is all number distinct mod 3

[stray reef]

your first case subsumes what i would have considered as three

[weary tiger]

ah can you tell me the subcases?

because i dont understand this solution

[stray reef]

0+0+0, 1+1+1, 2+2+2 and 0+1+2 are in fact the only ways to get 0 mod 3

there is no other way

if two of your numbers are congruent mod 3, the third is forced to be congruent to them as well

[weary tiger]

ah ok

here is the thing

i have not learned congruence

[stray reef]

then you are fucked

[weary tiger]

i am basically learning on the job

[stray reef]

how much of a "this needs done yesterday" factor is there

[weary tiger]

?

i dont understand

[stray reef]

how near is your deadline

for this assignment or whatever it is

[weary tiger]

oh i have this problem to solve by tuesday

and 2 others (which are not related to this problem)

[stray reef]

ok, then you might want to take a little detour and learn some basics of modular arithmetic

[weary tiger]

i watched a video, but i could not see how this connects to the problem

[stray reef]

maybe watching a single video isn't enough then?

[weary tiger]

yeah true

but in the solution what do they mean by distinct and congruent

i thought congruent means they have the same remainder

[stray reef]

can i see the entire solution in full

[weary tiger]

yes

[stray reef]

so that there is no mincing of words

[weary tiger]

ok

this uses a different set

[stray reef]

ok right

[weary tiger]

{1....18}

[stray reef]

so yes, congruent means same remainder

and

all numbers must be different mod 3
means all three of your numbers' remainders must be different from each other

[weary tiger]

ah i see

[stray reef]

(which means you must have exactly 0, 1 and 2 bc those are the only possible remainders at all mod 3)

[weary tiger]

i see

[stray reef]

in mod 4 it is kind of more complicated tho.
0+0+0
0+1+3
0+2+2
1+1+2
2+3+3

[weary tiger]

yes thats the next part to the problem (part ii)

and what does the solution mean by congruence classes?

they basically did 18/3 congruence classes = 6 numbers per congruence class

3 congruence classes

[stray reef]

a congruence class is the set of all numbers congruent to some fixed number

mod 3 in this case

[weary tiger]

i see

[stray reef]

so for example the congruence class of 4 mod 7 would be {..., -10, -3, 4, 11, 18, ...}

in principle taken from Z, but in your case it's narrowed down to only the set you're choosing numbers from.

[weary tiger]

i see

i will have to do a bit of moldular arithmetic

to learn all that

and hopefully I will be able to answer this question and understand the solution

[stray reef]

i think i have a set of basic problems on hand that i composed for a tutoring client of mine when he was learning about it

but unfortunately it's in russian

[weary tiger]

i never took a discrete math course and I jumped to combinatorics

biggest mistake ever

haha

[weary tiger]

ah ok its fine i will try to ask a friend for a textbook on the topic. my friend takes dicrete

[nova turtle]

Me too, but it wasn't a mistake

Taking honors combo rn

Probs my fav class ever

But tbf im a math major not a cs major

[weary tiger]

ah ok

i should have done discrete first it would have helped me with the notation

[prime flicker]

i need help, how would i start this problem

[obtuse lance]

maybe try a smaller problem that's similar and see if you can work that out manually to check your reasoning

sounds like stars and bars type of problem

[snow junco]

6 digits sum to 9 means very limited set of solutions

[prime flicker]

is there another term for the stars and bars because weve never learned it in class

and its not in the text book either

[twilit sundial]

“balls and urns” is another name i sometimes hear

the name is not important, the idea of “inserting dividers” is

[weary tiger]

anyone know the technical definition of what it means to say integer multiple of something

like for ex: 100 is an integer multiple of 10

since 100 / 10 = 10

[coral parcel]

a is an integer multiple of b if there exists an integer k such that a = k·b.

[weary tiger]

ah i see

thanks

[coral parcel]

(Whether k is allowed to be zero or negative here can vary with context -- but in most cases you can get away with assuming that if b is something that it makes sense at all to multiply by a negative integer, then that is fair game for an "integer multiple" too).

[weary tiger]

ye im just looking for positive stuff

can i use any modulo things?

[coral parcel]

If you're concerned about being misunderstood, you can say "positive integer multiple".

[weary tiger]

yes

[weary tiger]

yes i can

basically a mod b = 0

i am asking this because i am working on a solution to a certain (tough) problem

which requires this confusing mathematical language

ill present a potential solution soon!

k well i am stuck

so i found the cardinality of n (unsimplified) is 100^2

because the prime factorization of 10^99 is 2^99 * 5^99

now, to find the cardinality of m here is what i am trying to do, but to no avail

so, a multiple of 10^88 must be between 10^88 and 10^99 inclusive. This gives 10^99 - 10^88 + 1 numbers in this list

now we know that a multiple of 10^88 mod 10^88 = 0

and we know that the clock is like so {0,.... 10^88 -1}

now, we have to see how many turns

there are 10^99 - 10^88 + 1 numbers between 10^88 and 10^99,

i must be using the wrong mod base

no i am not

so there are a total of 10^99 - 10^88 + 1/ 10^88 turns

[tight hound]

Why don't you use the fact that the exponents of 2 and 5 in the prime factorisation of such a number must both be ≥88?

[weary tiger]

thus we have 10^10 numbers

[tight hound]

Makes it much easier

[weary tiger]

yes true

but i wanted to use modulo for some reason

but yes doing it that way, we see that the exponents x,y need to be between 88 and 99 inclusive for it to be a divisor of 10^99 and multiple of 10^88

which we would obtain

(99-88+1)^2 / 100^2

= 9 / 625

i guess that modulo does not work?

i want to use it i think it would give a nice solution

[stray reef]

...

i mean

why not just...

there are 10^99 / 10^88 numbers out of the 10^99 which are divisible by 10^88

you tried to shoot a sparrow with a cannon but instead the cannonball landed somewhere at or near your house

[obtuse lance]

I think tau( 10^99 / 10^88 ) would count them if I'm not mistaken (tau the number of divisors fn)

[stray reef]

oh positive divisor of 10^99

my bad i misread the problem

[weary tiger]

yes

i found the total positive divisors of 10^99

thats 100^2

but, now i need to find the total positive divisors of 10^99 that are also multiples of 10^88

thats why i said we can use modulo

basically we are trying to find numbers p such that p mod 10^88 = 0

where the clock runs from {0, ...., 10^88 -1}

there are 10^99 - 10^88 + 1 numbers between 10^99 and 10^88

thus, we will have (10^99 - 10^88 + 1) / 10^88 total turns of the clock

[obtuse lance]

the multiplicativity of the divisor function annihilates this problem

[weary tiger]

i dont understand

[obtuse lance]

how'd you work out that 10^99 has 100^2 divisors

[obtuse lance]

the numerator is worked out the same way with a slight fix to what Ann gave us here

[weary tiger]

i did prime factorization

its 5^99 * 2^99

you can do it, its very long but thats what you get

[obtuse lance]

here let me give you a tool

the divisor function tau(n) is the number of divisors of n and it satisfies the property tau(ab)=tau(a)tau(b) when gcd(a,b)=1

[weary tiger]

i never learnt that

[obtuse lance]

so you just need to know for a power of a prime p, tau(p^k) = 1+k and this gives you everything

[weary tiger]

tau and gcd i never learnt

[obtuse lance]

ah never learned gcd?

[weary tiger]

no i never took discrete

im doing combinatorics without having done discrete

haha

not recommended

[obtuse lance]

I would say it's something people learn in elementary school so it's ok to learn it now

[weary tiger]

greatest common denominator

but i dont know how to apply it lol

[obtuse lance]

not knowing how to compute the divisor function easily just makes your life harder since you're already doing it

tau(10^99) = tau(2^99 * 5^99) = tau(2^99) tau(5^99) = (1+99)(1+99) = 100^2

[weary tiger]

yes but theres another way

look at this

[obtuse lance]

no

look at this

[weary tiger]

$\prod_{i=1}^n k_i + 1 = (k_1+1)(k_2+1)\dotsb(k_n+1)$

[vital dew]

Derivative

[weary tiger]

thats the total number of divisors of a certain number

[obtuse lance]

tau(10^99/10^88) = tau(10^11) = tau(2^11 * 5^11) = tau(2^11) tau(5^11) = (1+11)(1+11) = 12^2

[weary tiger]

where k_1, k_2, k_3 are the exponents

[obtuse lance]

yeah, that's exactly what I'm computing too

that is the same tau function I'm describing and using

[weary tiger]

yes but i didnt learn the tau function

[obtuse lance]

maybe it goes by a different name for you

[weary tiger]

ah what does it do?

[obtuse lance]

it is exactly the same thing

[weary tiger]

oh

[obtuse lance]

that's what my work is showing

[weary tiger]

ah

wow

thats cool

[obtuse lance]

yeah

[weary tiger]

i like your solution

its really cool

tau is a powerful function

[obtuse lance]

there are a lot of functions that simplify this way, they're called multiplicative functions where you can separate it apart when the gcd of the two factors is 1

the sum of divisors, the euler phi function, and there are others

[weary tiger]

ah i see

i have one question

[obtuse lance]

yeah very useful for sure

[weary tiger]

why tau(10^99/10^88)?

thats the number of divisors of 10^99 divided by 10^88

why do that?

[obtuse lance]

cause multiples of 10^88 look like k*10^88, and since it's a divisor of 10^99 so k10^88 | 10^99

so you can throw out what they have in common, k | 10^11

[weary tiger]

ah i see

[obtuse lance]

we're really just counting divisors of that

yeah

[weary tiger]

ok

whats the symbol of tau?

[obtuse lance]

$\tau$

[vital dew]

Merosity

[weary tiger]

because i dont think i can right tau on latex

ah i see

ok

[stray reef]

you can write all greek letters in latex

except for omicron, bc that is identical to latin o in shape

and some of the capitals, for the same reason

[weary tiger]

i see

well thanks for showing this!

[obtuse lance]

yeah you're welcome

[weary tiger]

I have finally finished my assigment (actually nvm i have 1 problem left💀 )

31 problems

took me like 3 months

hahah

but in my assignment i have a few semi-unsolved problems

1 semi-unsolved questions, 1 unsolved question

[weary tiger]

yes so i need help with this question:

so above is my solution to the first method

but now i need help showing that $\sum_{k=1}^n k^2 = |T|$

[vital dew]

Derivative

[weary tiger]

i was thinking induction on n

[obtuse lance]

it's a shame this has such a nice proof not counting them

[weary tiger]

?

what do you mean

i did the proof the counting way