discrete-math

[weary tiger]

Again I would think of this more intuitively, you'll bog yourself down thinking of all of this as just variable juggling

[verbal silo]

Hello! how can i show that there exists a natural number n such that 11|(2^n-1)

[weary tiger]

I understand what you're saying completely but I'm hope to be thorough for homework and not making any sort of leaps in logic

Why can you "just" rename variables to something else? Because they are variables whose name was arbitrary in the first place. I could have called q Y instead. I could have drawn a little symbol of a fish or a Chinese character instead. It will behave the same

ok, got it.

Awesome!

thanks for being patient with me haha. this is all very new.

Oh my pleasure good luck with it all :)

@verbal silo What have you tried so far?

[verbal silo]

i got 2^n congruent 1 (mod 11)

[weary tiger]

Nice

An often useful trick when you are working with congruences is to repeatedly multiply both sides by the same thing

Because you can just reduce it mod 11 or whatever you are working in

So you can clench your cheeks and hope that your prof made it easy to find some power of 2 congruent to 1 just by multiplying 2 by itself over and over and over again mod 11

It's not a rock solid method but it often works out pretty nicely

Have you seen that before? I can demonstrate if not

[verbal silo]

no! I actually havent 😭

it would be great and i would be really thankful, if you have the time!

[weary tiger]

Sure thing

https://i.pinimg.com/originals/69/64/2b/69642b3b07d28e51862389d1afc8be13.gif

2 mod 11 is 2
2*2 mod 11 is 4
2*2*2 = 2^3 mod 11 is 8... etc
but note that after this step the magic happens
2^4≡16≡5 mod 11

and so 2^5≡5*2= 10 mod 11, etc

try to keep going on your own

you might just find something ≡1 mod 11 (what you wanted)

[errant bear]

(what if i'm not good at looking for things)

[verbal silo]

okay!

[weary tiger]

when you are done I found a more reasonable proof than just proof by example if you're interested
for a time-constrained exam or something I would recommend this sledgehammer smashing method though lol

[errant bear]

oh wow didnt know you were fermat 😳

[weary tiger]

We need to determine whether or not this equivalence hold. Does anyone know how to go about this question?
I have searched for these kinda questions but couldnt find them anywhere.
Can anyone pls help me with it?

[weary tiger]

<@&286206848099549185>

[pallid lintel]

https://gyazo.com/3d644fe37c3755083ff21e4130027a03 if i find r(5,5) would i get a phd in math? r(6,6) would be fields medal worthy perhaps?

I'm trying to prove r(3,3) in an extremely difficult way compared to the paragraph length proof that is normally given hehe.

[vapid oyster]

1.P → Q )
2) ~R۷S
3) P ۷ R
Therefore Q → S

is this the correct solution for this
4. Q New premise
therefore S
5. ~P Modus tollens 1,4
6. R Disjunctive 3,5
7. S Disjunctive 2,6

[stray reef]

did you really just use an eastern-arabic digit 7 for the or symbol?

[vapid oyster]

i just copied the sign on google hahah

is it correct?

[stray reef]

okay so like, for future reference,

∨

[unreal stump]

https://gyazo.com/3d644fe37c3755083ff21e4130027a03 if i find r(5,5) would i get a phd in math? r(6,6) would be fields medal worthy perhaps?
@pallid lintel Probably no

[stray reef]

this is the proper logical or symbol. if you don't have it available then you can type the latin letter v or the letters or

anyway, what's your argument again

[vapid oyster]

I'm trying to solve it via conditional proof

[stray reef]

$\frac{P \to Q, , \neg R \lor S, , P \lor R}{Q \to S}$ this?

[vital dew]

Ann:

[vapid oyster]

yes

[stray reef]

ok so in your first step you add Q as a premise and change the conclusion to S, yes?

[vapid oyster]

yeah

[stray reef]

step 5 is invalid

[vapid oyster]

after that i used modus tollens to get ~P

[stray reef]

modus tollens would be $\frac{P \to Q, , \neg Q}{\neg P}$

[vital dew]

Ann:

[stray reef]

but you have Q, not !Q

[vapid oyster]

oh wait no the conclusion was ~Q implies S sorry

[stray reef]

the plot thickens

[vapid oyster]

so the new conclusion was ~Q therefore S

my bad

[stray reef]

ok this seems to hold up now

[vapid oyster]

After getting ~P i used disjunctive to get R

i'm not sure if i did the 7th step correctly

[weary tiger]

What does the number 6 on top of the sequence mean?

[gritty crescent]

Umm that the sequence terminates at n=6, I guess

It starts at n=1(as indicated in the subscript) and terminates at n=6(as indicated in the superscript)

[stray reef]

the n=1 and 6 together mean that n ranges from 1 to 6

so the 6 indicates the index of the last term in the sequence

[vapid oyster]

@stray reef is what i did correct?

[stray reef]

yes

[vapid oyster]

thank you

yes
@stray reef

[weary tiger]

thank you @gritty crescent @stray reef

[weary tiger]

Could someone explain to me index shift? I don't really get it

[karmic nymph]

$(A \oplus B) \oplus B = A$

[vital dew]

Yes:

[karmic nymph]

could someone help me prove this without a table?

Could someone explain to me index shift? I don't really get it
@weary tiger looks like regular series algebra

[unreal stump]

A xor B =A'B+AB'

Use that

[karmic nymph]

im aware of that

(A-B) U (B-A)

[weary tiger]

OH I think I get it now

It's just changing the index accordingly

[karmic nymph]

(A-B) U (B-A) XOR B

hmm i guess i can illustrate it on venn diagrams and see that its A

[weary tiger]

Discrete math is so hard...

I think I'll fail this unit...

[karmic nymph]

are you a CS major?

[weary tiger]

yes

[karmic nymph]

same

[weary tiger]

1st year?

I

[karmic nymph]

yep

[weary tiger]

I've just started last month

[karmic nymph]

just started this week

[weary tiger]

Ooooh

[karmic nymph]

I like discrete math lol

[weary tiger]

how are you finding discrete math so far?

[karmic nymph]

Good

[weary tiger]

It was ok at first, wasn't too hard to catch up

[karmic nymph]

I have a background in mathematics already so i enjoy this

[weary tiger]

but as the unit went on it became increasingly difficult to a point where I can't really understand the lecture slides anymore

[karmic nymph]

Are you learning from a book?

[weary tiger]

No, from lecture slides

[karmic nymph]

oh

[weary tiger]

I have a mathematical background as well

[karmic nymph]

My teacher is really bad so im just learning from the Rosen book lol

[weary tiger]

Did SL Math for the IB

oh u r studying from the rosen book too?

[karmic nymph]

oh i did IB equivalent

yep

[weary tiger]

noice

[karmic nymph]

Im on chapter 2

[weary tiger]

did u do SL math as well?

or HL?

[karmic nymph]

HL

[weary tiger]

if u r finding this easy u r prob doing HL

yeah

no wonder

[karmic nymph]

I did A level further math which is UK equivalent of HL IB

so yeah not too bad

What chapter are you on?

[weary tiger]

A levels and IB are the only 2 pre-graduate curriculmn that I respect

they're both very rigorous

AP is a fucking cakewalk

SAT is for kindergardens

[karmic nymph]

lol I think A level is pretty easy too lol

but yeah AP and SAT are easy

[weary tiger]

Yeah but at least A levels is somewhat more difficult than AP and SAT

[karmic nymph]

yep

[weary tiger]

and u hear americans complaining all the time about it

[karmic nymph]

lol yes

[weary tiger]

just shows their standards...

ah anyways, sorry for the rant

[karmic nymph]

lmao

[weary tiger]

I haven't used the rosen book yet, since I'm basing off my learning from lecture slides

Is the rosen book actually good?

[karmic nymph]

Youre European right

[weary tiger]

Like, do you understand it better?

No

[karmic nymph]

yes I like rosen book, very good

Better than my teacher lol

[weary tiger]

xD

Mind if I ask which uni u r in?

[karmic nymph]

King's College

[weary tiger]

damn that's pretty good

[karmic nymph]

not really lol, it has only has good Reputation

nice

[weary tiger]

It's fairly prestigious but not as prestigious as king's college I think

[karmic nymph]

i have heard of about uni of sydney

so you guys start uni in august?

[weary tiger]

yep

[karmic nymph]

i started on 28th sep

[weary tiger]

yeah..

anyways I'm gonna try to go through the ross bookk

[karmic nymph]

yep have fun lol

[karmic nymph]

$\bigcap_{i=1}^{\infty} A_i$

[vital dew]

Yes:

[karmic nymph]

A_i = {0,i}

wouldnt it be {0,1} AND {0,2} AND ... AND {0,i}

so null?

[stray reef]

$\rien \neq {0}$

[vital dew]

Ann:

[karmic nymph]

wait why is it {0}

[stray reef]

a point is in $\bigcap_{i=1}^{\infty} A_i$ precisely when it is in every $A_i$ at once

[vital dew]

Ann:

[stray reef]

and don't you agree that 0 ∈ {0, i} no matter what i is

[karmic nymph]

oh right

I was thinking about comparing subsets

tnx

[stray reef]

wym comparing,,,

[karmic nymph]

comparing is a bad word, i mean errr

I was looking at the subsets as a whole but nvm i understand now

[vapid oyster]

can someone help me solve this using indirect proof

1. A → ( B and C )
2. B → ( D and E )
   Therefore A or D

[stray reef]

show that the premises $$A \to B \land C, , B \to D \land E, , \neg A \land \neg D$$ lead to a contradiction

[vital dew]

Ann:

[stray reef]

which... hold up, do they?

[weary tiger]

What does "f: (-2,3)" mean?

[stray reef]

...your question reads as if you saw the word function and asked "What does func mean?"

the notation $f: (-2,3) \to \bR$ means ``$f$ is a function from $(-2,3)$ to $\bR$'' (i.e. this notation establishes the function's name, domain and codomain in that order)

[vital dew]

Ann:

[vapid oyster]

@stray reef uhmm how about the steps? also the conclusion was ~A or D my bad

[stray reef]

YIKES

hurgh

i mean do you really expect me to do the working out for you

[vapid oyster]

well i'm a little lost on what to do when it comes to indirect proof

all i know is the new conclusion will be ~(~A or D)

[stray reef]

no

you add ~(~A or D) as a premise, and the new conclusion is Falsum

[vapid oyster]

ohh

what do i do after?

[stray reef]

de morgan, and-elim, or-intr, MT

[verbal silo]

Can some one help me out with how to apporach this problem

[stray reef]

pick a low integer of your choosing, say 10

try to prove that this inequality holds for n ≥ 10

[verbal silo]

but wouldnt i have to plug in everynumber greater than 10

after

since im trying to prove for all?

[stray reef]

are you familiar with induction

oh god you multiposted

[vapid oyster]

de morgan, and-elim, or-intr, MT
@stray reef -elim -intr?

[stray reef]

elimination

introduction

[vapid oyster]

elimination
@stray reef is this disjunctive syllogism?

[stray reef]

??

idk what that's supposed to mean, but i'm referring to the derivation of P from P&Q

[verbal silo]

no 😭

[vapid oyster]

idk what that's supposed to mean, but i'm referring to the derivation of P from P&Q
@stray reef is it like this
P and Q
therefore P?

[stray reef]

sure

[vapid oyster]

how about introduction?

[stray reef]

P therefore P or Q

[brave lava]

https://i.imgur.com/O0AohLD.png

any help?

[vapid oyster]

P therefore P or Q
@stray reef Ohh okay thankss

[brave lava]

<@&286206848099549185>

[daring beacon]

can someone explain to me how the qu turned positive when it went to 6(ii) to 2(i),3(i)

I'm using this as a reference

q* not qu

[weary tiger]

I think it might have just been a typo, but that doesn't really matter, right? at that point you already have "p or not p", so "or" that with anything else and you still have a tautology yeah?

[daring beacon]

yeah thanks

[brave lava]

https://i.imgur.com/YffMQEI.png

can anyone please help me

[static maple]

write the statement: if an integer is positive then it equals its absolute value.

I put

for every x in natural numbers, x = abs(x)

while the "correct" answer is

for every x in integers, x > 0 => x = abs(x)

but are these not the same?

[sick swallow]

Lol x>0 is not natural numbers

Also you can do x>=0

[static maple]

what are natural numbers then?

[sick swallow]

Bruh

[sick swallow]

Oh wait it says x is an integer

[static maple]

yep

[sick swallow]

But yea that is obviously equivalent

[static maple]

well in that case rip 6% of my grade

[weary tiger]

Could I get some help with this problem

[sick swallow]

It is probobly some syntax error

[static maple]

its human graded

[sick swallow]

Maybe he is french

Where they include 0 being natural

[static maple]

@weary tiger what those down arrows

or?

no

[honest barn]

0 should be a natural number

[static maple]

idk what they are

[sick swallow]

0 should be a natural number
@honest barn

[honest barn]

Actually I strengthen my statement

0 is a natural number

[weary tiger]

It's NOR @static maple

[sick swallow]

Yea it did literally define it in the question

[weary tiger]

Pierce's arrow

[static maple]

change the nors in the final statement to not ors, distribute with demorgans, combine with associative?

cant think that far ahead

sorry to steal your question but i do have one more problem

for every x and y in D, x^y is in D

i said this was true for D = natural numbers

and i believe it works for 0 as well so i dont see where i went wrong here

[sick swallow]

If the set is closed under multiplication

Which obviously isn’t true for every set

[static maple]

natural numbers are closed under multication tho?

[sick swallow]

Yea of course

[static maple]

so why is that statement false for the domain of natural numbers?

i can submit a regrade request but i need to make sure im right

[sick swallow]

Did it say it is distinct from x and y

[static maple]

"prove an infinite domain such that the statement is true"

[sick swallow]

What does the bottom image mean, countable?

[static maple]

its my answer

Domain in which its true = fancy N i cant type

[weary tiger]

@static maple What would not or look like?

Would both p and q be negated?

[static maple]

ℕ is what we learned for natural number

[sick swallow]

Yea it is

[static maple]

@weary tiger its in the problem

yes both are negated

[sick swallow]

But yea, natural number satisfy this condition

[static maple]

regrade request time

thanks

[sick swallow]

Lol it seems the people who marked this test don’t know about natural numbers

[static maple]

regardless of if natural numbers include 0 thats still true

x^0 = 1 which is in N, and 0^x = 0 which is in n

oh

im willing to bet their argument is 0^0 is indeterminate

and therefore does not have to be in N

[sick swallow]

Yea 0^0 is undefined

[static maple]

guess i should have written N /= 0

[sick swallow]

That is like saying R/i

[static maple]

i lost 10% of my grade because these people use the other definition of natural numbers

thanks guys

[honest barn]

Yea 0^0 is undefined
@sick swallow eh

In quite a few situations you define it to be 1, or 0, depending on what you need

But that’s usually for things where you do sums and don’t want to special case some weird edge case

(I’m partial to saying it’s 1 tho)

[static maple]

the question is if i can prove 0^0 is in natural numbers

[static maple]

you can get rid of the other down arrow if you want too

[sick swallow]

well u cant because it is undefined generally

[weary tiger]

In the same step?

[static maple]

im fairly sure when you distribute you end up with part of it being your other identity given reg

no another step reg

[sick swallow]

but it does have accepted values in some instances as chmonkey mentioned

[honest barn]

Yeah to show any property of 0^0 you need to define it

[honest barn]

You can define it as different things

[sick swallow]

this is a graph of x^x

[static maple]

great ill define it as 1 and call it a day /s

[honest barn]

If you have it defined as like the limit of 0^x as x -> 0 (actually this is one sided)

Then clearly it’s 0

[sick swallow]

rip did u see that graph

lol

[static maple]

can i just pick some arbitrary definition that works for my goals tho

[honest barn]

Uhhh no?

[sick swallow]

actually it is not clear

[honest barn]

Is this for a class?

[static maple]

yes

it is

[honest barn]

Then you need a provided definition

And work with that

[static maple]

... but i dont have one

[sick swallow]

in fact, anaylsis is one of the discplines which keeps 0^0 as undefined

[honest barn]

If you don’t have one then ask them

Because else

this is like asking you to show if Apple is a natural number

Or like

[static maple]

i mean this argument is because i slightly messed up a problem, but if i can show 0^0 is in natural numbers then my answer is also correct

[honest barn]

“Is x a natural number”

And you say set x = 1

Then you need to redo your method

[glass condor]

if you have $x^y$, $0^0$ depends on whether you first do $x \rightarrow 0$ or $y \rightarrow 0$ (both at the same time is the same as the latter)

[sick swallow]

bruh as mentioned u dont need to worry aobut 0^0

[honest barn]

Or more carefully see how you got 0^0

Because I’m guessing you just naively plugged some shit in to get 0^0 which won’t work

[sick swallow]

because 0 is not in natural numbers

[vital dew]

ConfusedReptile:

[static maple]

yes the reason i got 0^0 is my prof uses "natural numbers include 0" definition while i didnt when doing the homework

[sick swallow]

umm that isnt even true what u said confusedreptile

[honest barn]

What’s ur problem actually?

[static maple]

but i have to show x^y is closed under natural numbers

where natural numbers apparently include 0 as well

[honest barn]

Uhhhh

Ask for a definition of 0^0 then

Or say like... “there’s some issues with this lmfao” and explain that

And say “but some define it as 1 so if we go by that convention...”

[static maple]

to be clear theres no other instances where thats false right, 0^0 is the only place its potentially not closed?

[sick swallow]

you dont need to justify whether natual numbers include 0 or not

[west hedge]

there's no issue with defining 0^0 = 1 for natural numbers

[sick swallow]

it is a definition that they dont

[honest barn]

He isn’t justifying it

[sick swallow]

he kind of is

[honest barn]

The definition of natural they’re given includes 0

[static maple]

they already said natural numbers include 0, I cant change that

[glass condor]

@sick swallow

umm that isnt even true what u said confusedreptile

$$
\lim_{y \rightarrow 0} \lim_{x \rightarrow 0} x^y = \lim_{y \rightarrow 0} 0^y = \lim_{y \rightarrow 0} 0 = 0
$$

[vital dew]

ConfusedReptile:

[honest barn]

They need to show x^y is a natural for x,y naturals

[static maple]

yes

[sick swallow]

why dont u tell them that their definition is wrong

[honest barn]

That limit doesn’t exist reptile, the first one

[static maple]

somehow i feel like telling the prof their definition is wrong isnt the greatest idea

[honest barn]

When y is just some amorphous number you can’t go from the left to 0

[sick swallow]

why

[honest barn]

Since you can’t define x^y for arbitrary y when x is negative (as a real number)

[sick swallow]

if it is wrong, then it is helpful informing him of his misinformation he is spreading

[honest barn]

Lmfao

N includes 0 tho

[sick swallow]

no it doesnt

[glass condor]

When y is just some amorphous number you can’t go from the left to 0
@honest barn yeah, that's true, I meant from the right (for both).

[errant bear]

0 is my favorite natural

[honest barn]

We’ll settle this in discussion math

[stray reef]

@honest barn @sick swallow

[static maple]

ill go to office hours and ask about my problems, then maybe submit a regrade if i can convince the TA

[errant bear]

i also like -0 though

[honest barn]

Ann, you agree with me@tho right?

0 in N 😎

[weary tiger]

wouldn't associative not work because theres an and?

Discrete math is so hard...

I'm gonna fail this unit...

[lean cave]

Yall, I need help. I drew the 5 x 5 grid and I noticed that there are some restrictions where you can't have a 1 x 1 block placed with the 1 x 2 block, but I really can't explain it with words. here is the problem: You want to tile a 5 by 5 grid out of a single 1 × 1 tile and twelve 1 × 2 tiles. Are there conditions on the location of the 1 × 1 tile, i.e. can it occupy any space of the 5 × 5 grid or are there positions it cannot occupy?

[tardy pelican]

https://en.wikipedia.org/wiki/Bertrand's_ballot_theorem#Variant:_ties_allowed

Can someone explain how the reflection principle works here ? Any resources would be helpful.

[sick swallow]

Discrete math is so hard...
it is trivial

[sick swallow]

not being a computer scientist doesnt imply being an engineer in this question

it is being a computer scientist imples not being an engineer, which is different to that

[daring beacon]

can someone tell me where the -1 came from here when you are trying to prove x-3/x+3 is one-to-one?

[sick swallow]

it is a mistake

it is meant to be x_1

[daring beacon]

but what would you cross multiply to get x_1 between (x_2+3)(x_1-3)

like I don't see a value that that would equal x_1 for

I only see the same values as the right side

unless its a typo which the prof said there might typos in this

[naive saffron]

The 6th one is also correct

[weary tiger]

thanks!

[weary tiger]

https://puu.sh/GytFh/1888ad06be.png

[bitter moss]

thats 🧢

@weary tiger is it valid or invalid

[weary tiger]

I'm unsure of what an infinite series is much less convergence

don't need to

Oh.

It's bring q as a premise

think of everything written as just logical statements

and implying p

yeah that sort of thing

converse error

POG

[dapper girder]

hey this is probably the wrong place to ask this, but does anyone know if
ℕ X {0, 1, 2} is countable or not? I've been trying to figure it out for a while

[weary tiger]

try making an injection to N, that would suffice yeah?

[dapper girder]

oh yea lol thanks

[weary tiger]

I think something went wrong on line 5.

[unique herald]

I have no clue how to prove this..

[weary tiger]

@unique herald what is it?

on B

[honest barn]

I think that’s supposed to be complement

Okay so bruh

I’m gonna ask you to do some stuff okay?

@unique herald

I’m gonna ask you to draw some stuff

And then you’ll see why this is true and I think you can prove it

[unique herald]

Wait I think i figured it out

But now I'm stuck on a new question lol

What does it mean by translate in two ways?

[honest barn]

They just mean write it in symbolic logic

[unique herald]

For 8a). I got: x = students in our class, y = students who can't swim. ∃y∀xP(x, y)

[honest barn]

This isn’t right

[unique herald]

why?

[honest barn]

Sorry, what is P here?

[unique herald]

predicate

[honest barn]

Actually okay, I’m not the one to help with this TBH, but it seems wrong to me.

I’m pretty sure you want to say there exists a student in the class such that they can’t swim

But honestly maybe this works

Idfk, this isn’t stuff I’m good at, if no one comes by in 15 min ping helpers

[unique herald]

kk

thx for the help anyways

[honest barn]

Ann is currently online so if no one else does I know she’ll be able to help you, but I wouldn’t ping her specifically

Since that’s kinda rude and defeats the purpose of the 15 min thing

[unique herald]

oh wait

i think im wrong

but this would be right

let x = students in our class

let y = students in our class who cant swim

1). ∃xP(x)

2). ∀yP(y)

[honest barn]

I mean...

If you say y = students in our class who can’t swim

Wouldn’t it suffice to literally just go “there exists y”

[unique herald]

true

idk this quantifier and predicate stuff is confusing me

[honest barn]

I forget what a predicate is

[unique herald]

Like what even is the predicate statement

[honest barn]

But isn’t that like a thingy that takes in a variable and spits out a truth value?

Like you say P(x) is “x can swim”

Then if you let x be students in the class then you just have “there exists x such that not(P(x))”

But the thing is I don’t actually know any of this shit

I just do math and picked up basic symbolic logic from that so I don’t know any of this crap

[unique herald]

here's an example from my lecture slides

[honest barn]

Okay so like here it is

When the universe of discourse is students

It should be P(x) is x cannot swim

Then it should be like
there exists x P(x)

Since then if you translate this this legit says “there exists x, which is a student in your class, such that x cannot swim”

But when the universe of discourse is all people

You have to say P(x) is x cannot swim

Q(x) is x is a member of your class

Then the sentence is
“There exists x (P(x) ^ Q(x))

Cuz when you translate this now it says there exists x, a person, such that x cannot swim AND x is in your class

When you enlarge the universe you draw x from, from ppl in ur class to ppl in the world you have to add in Q(x) so that you know x is actually in your class

[unique herald]

ahhh smart

Idk why but discrete math is much more enjoyable than other math courses imo

thanks for the help btw!

[weary tiger]

Sorry for asking again but can anyone please help me with this question?
We need to determine whether or not this equivalence hold. Does anyone know how to go about this question?
I have searched for these kinda questions but couldnt find them anywhere.

[weary tiger]

How come only B is correct?

if I were to convert 100 to base 10, wouldn't I get 4 as well?

OH WAIT IT'S A "NOT EQUAL" SIGN

smh

nasty trick

[scarlet current]

is ∃x∃y(a(x) —> b(y)) logically equivalent to ∃xa(x) —> ∃yb(y)?

please someone help

[wintry obsidian]

hello

anyone available to help with simple question that i don't get?

@here anyone ^

[weary tiger]

who wrote this question

[errant bear]

the author

[wild flame]

https://i.imgur.com/OQ45vj1.png

For this notation.

Why is the J relevent?

Oh. To denote that it starts with '1', right?

[honest barn]

Because you’re stating what variable you’re using to index them by

[wild flame]

I apologize, as I'm not quite sure what that means.

By 'index them by', do you mean that the the J sets the interval that they're indexed by? For example, if J = 2, then they would be indexed by 2's?

@honest barn

Or does that just choose the starting variable for he index?

[honest barn]

you wrote p_j

If you wrote like
$\wedge_{i = 1}^n p_j$ this has an entirely different meaning

[vital dew]

Chmonkey:

[honest barn]

Also I'm confused why you write a capital J when there's no capital J being mentioned in the picture you had linked

[wild flame]

Hrm? I was referring to the only variable j in the image.

Also I'm not understanding the relevance of your response.

[honest barn]

but J and j are different things

capitalization matters a ton

you might have a J and a j floating around in the same context which are different

[wild flame]

Aye, I get that.

[honest barn]

I'm saying that you write j since you're indexing over p_j

I don't know how to do that like

big or symbol but

let's do the wedge symbol thingy for right now

$\wedge_{j = 1}^n p_j = p_1\wedge p_2\wedge\dots\wedge p_n$

[vital dew]

Chmonkey:

[honest barn]

But $\wedge_{i = 1}^n p_j = p_j\wedge p_j\wedge\cdots\wedge p_j$ where you have $n$ copies of $p_j$

[vital dew]

Chmonkey:

[honest barn]

Note that by saying $\wedge_{i = 1}^n$ you're going "okay take the thing that's in there when $i = 1$, then do $\wedge$ with what is in there when $i = 2$, then do $\wedge$ with what is in there when $i = 3$..."

[vital dew]

Chmonkey:

[honest barn]

but since you have $p_j$ inside of there when $i = 1$ you still have $p_j$, when $i = 2$ you have $p_j$...

[vital dew]

Chmonkey:

[honest barn]

versus when you do this with $j = 1$ to $n$, when $j = 1$ you have $p_j = p_1$, when $j = 2$ you have $p_j = p_2$...

[vital dew]

Chmonkey:

[wild flame]

Ah I get what you're saying.

[honest barn]

Now tbh

It's common to say $\wedge_1^n p_j$

[vital dew]

Chmonkey:

[honest barn]

and then it's understood since $j$ is the only variable in there that you're indexing over the $j$

[vital dew]

Chmonkey:

[honest barn]

but if you have say $\wedge_1^n p_{j,i}$ then you don't know which one to index over

[vital dew]

Chmonkey:

[honest barn]

since $\wedge_{i = 1}^n p_{j,i}$ and $\wedge_{j = 1}^n p_{j,i}$ are different

[vital dew]

Chmonkey:

[wild flame]

Basically. For the 'i' variable (or in the original 'j'), the variable is set to a certian value. Then it loops until reaching some n value.

In the original, j is both the initial value an its tied to P.

[honest barn]

yeah pretty much

[wild flame]

So as j increases, so too does j.

[honest barn]

It's like if you wrote

$\sum_{i = 1}^n a = na$

[vital dew]

Chmonkey:

[honest barn]

cuz what's in there is a constant with respect to $i$

[vital dew]

Chmonkey:

[honest barn]

but now if you do $\sum_{i = 1}^n a_i$ it changes

[vital dew]

Chmonkey:

[honest barn]

but with respect to $i$, $a_j$ is gonna be a constant so $\sum_{i = 1}^n a_j = na_j$

[vital dew]

Chmonkey:

[wild flame]

Gotta go review summation. But this insightful.

TY brother.

[brave lava]

https://i.imgur.com/jEzTt8q.png

can someone check my answers

[gritty crescent]

Looks good.

[brave lava]

what about B

I also put B

B,D,E

@gritty crescent

[gritty crescent]

b) is incorrect; A could be a proper subset of B and the statement would still hold

[brave lava]

why is b incorrect

@gritty crescent

[gritty crescent]

Counterexample: A={1,2,3}, B={1,2,3,4}. Then A intersection B={1,2,3}=A, but A is not equal to B.

[brave lava]

but A isn't a proper subset. Both the sets are equal as given in the question

[gritty crescent]

They've asked when is A=B?, not actually if A=B, then...

The sole criterion is infact A subset B and B subset A

[brave lava]

https://i.imgur.com/Sj0l1C8.png

am i missing any here

[brave lava]

<@&286206848099549185>

[minor dagger]

are you allowed to select more than one answer>

should be relatively prime

because they dont actually have to be prime they just need not share any common divisors

other than 1 of course

[brave lava]

yeah

i can select multiple answers

@minor dagger

is it just d then?

[weary tiger]

anyone knows how to get the range of this function?

[minor dagger]

you might be able to say well-ordered because the non-empty set of divisors for each contain the same smallest values

not sure tho

[brave lava]

i think its just d

thanks

[gritty crescent]

@weary tiger You can figure out range for both the definitions individually and then get their unions?

[brave lava]

https://i.imgur.com/KeYL5wx.png

can someone check my answers

[minor dagger]

looks good to me

[sonic path]

does this properly represent an example of a relation on a set that is neither symmetric nor antisymmetric

[weary tiger]

try to remember what the definitions of those words are, and then figure out what each means in terms of the matrix representing the relation

but if you just want an answer to check your reasoning by, yes it does

[brave lava]

https://i.imgur.com/FuXHkTM.png

[sick swallow]

it is just an easy simultaneous equation

[brave lava]

wdym

?

@sick swallow

[pale epoch]

do you know what that means in english?

[brave lava]

no

[pale epoch]

then look up the definitions of the symbols

[brave lava]

can you help?

[minor dagger]

bruh if you are trying to do discrete math you NEED to know the notation

[pale epoch]

help how? do you not have a book/script?

i can't do the studying for you

[brave lava]

got it on my own

9/2

and -3/2

didnt need u

[sick swallow]

it was trivial

[brave lava]

https://i.imgur.com/JhRlVC6.png

stuck

we have to assume a is not congruent to b mod m

does anyone know what steps are after

[weary tiger]

how do you define a to be congruent to b mod m

[brave lava]

using multiples lol? idk

[weary tiger]

well how do you want to solve an exercise about congruence if you don't know the definition

[brave lava]

thats why im asking

[weary tiger]

before asking someone you should read your book if you have one or if you're learning without book search on internet

i could tell you a definition but i think it's better if you find it yourself

[pure mountain]

a hypercube in dim 3

Define Diameter as the longest shortest path between two nodes

in our case does that imply Diamater is 3 ? because of we pick (0,0,0), to get to (1,1,1) # of edges = 3?

because we cant do better

[weary tiger]

you need to prove that you cant do better

[pure mountain]

we can think of it as a graph

Let me draw something

and label nodes to give a succicent understanding

we get a torus

[pure mountain]

dont know how to fomrally prove it

does it hold for higer dimensions

[glass condor]

for an n-dim cube, each step in the path corrects one coordinate

so to go from (0,...,0) to (1,...,1) you need n steps.

[pure mountain]

so sum of (1,1,1)?

in 3D space

= 3

make sense

[glass condor]

in the general case, the length of the shortest path between $(x_1,x_2,\dots,x_n)$ and $(y_1,y_2,\dots,y_n)$ is $\sum_{i=1}^n |x_i-y_i|$, yeah

[vital dew]

ConfusedReptile:

[glass condor]

so at most n, when all the coordinates are different (opposing vertices of the hypercube).

[pure mountain]

oh

ur the best

and when i think of it

it make sense

thanks

its so nice

when you transform a problem

into a form where u can easily reason

about it easily

thank sir~

[glass condor]

huh, by the way this means that all path lengths between two vertices in a hypercube have the same oddity

uhh, evenness. However you call divisibility by 2
EDIT: a-ha, parity, thanks Madeleine

because in order to deviate from the shortest path, you need to choose to change a coordinate that doesn't need changing and then change it back, so 2 additional edges traversed

[mystic moss]

interesting. is this not true for things that are not hypercubes? (also, parity)

[glass condor]

is this not true for things that are not hypercubes?
here it's due to the fact that all edges have a simple form in the coordinate representation. One can see that for a full graph, paths of all lengths are possible. Besides that, no idea 🙂

[brave lava]

can someone check my work so far

this is an inductive proof

[honest barn]

thanks, this is a really good image, I'm gonna steal it

[weary tiger]

What’s ā I haven’t seen that notation

[wild flame]

Is it more or does the book does a poor job at answering #11?

I was able to solve the issue by using some logical equivalence laws.

And I checked via Chegg and they had a similar answer. So I want to ask a few questions.

https://i.imgur.com/LtJk2TW.png

Couldn't the portion changed with the Commutative law also be just as easily changed with the Associative law?

[wild flame]

Nevermind

Associative needs there to be 3 different variables

[stray reef]

actually TECHNICALLY you need to apply the associative law then the commutative law then the associative law again if you're being extra formal

[wild flame]

Ah. Why is that? is not extra formal

[stray reef]

cause you need to regroup the parentheses to the right, then switch around the p and the !q, then regroup the parentheses back

[scarlet current]

for proofs by contradiction

can i just negate the theorem

and show that it is false

hence the original theorem is true?

[sour arrow]

• Assume the negation of the theorem
• Prove ANYTHING both true and false at the same time, which is not allowed
• Therefore assumption was wrong and the theorem is proven

[stark creek]

ehm, hi i have a question in kinda stuck on

A particle moves in a horizontal line. The distance it covers each second is twice the distance it covered in the previous second. If a_n represents the position of the particle at the second n. Find a recurrence relation for a_n.

i mean, i know the answer just by kinda looking at it

id say its ||2^n - 1||

but my professors solution is very very very different and i dont understand it

[sour arrow]

That's a formula for the position at any n, and not a recurrence relation for it

[stark creek]

oh

well how do i find a recurrence relation, i dont really understand them tbh

i could say that An-An-1 = 2(An-1 - An-2)

but

is that enough?

dont i have to solve that somehow?

[sour arrow]

Lol yeah that's a recurrence

One could solve that, but the question doesn't want you to

[stark creek]

i see

well

how would i solve it?

the first step is seeing if that discrete function is homogeneous or not?

[sour arrow]

Okay good you know a little bit of this

[scarlet current]

Prove that If n is an integer, then n is odd if and only if n^2 is odd. For this question is the conditional statement important? or do I only look at the biconditional?

[stark creek]

that might not be the right word in english sorry

[sour arrow]

This one is homogeneous, so the solution will be terms of the form
a(n) = Cλ^n

Sub that in, you'll be able to solve a quadratic to get λ

[stark creek]

so, i know its homogeneous because there are only terms with An or An-1 and things like that right?

[sour arrow]

Exactly

[stark creek]

because there are no independent terms

okay okay

i think i see it now

thanks a lot kaynex, the wise!

i will probably be back

[sour arrow]

Np! Feel free to ask if you need anything else!

[stark creek]

also, i get the C and the λ by subbing in different terms that i know the values of, right?

[scarlet current]

i took into account the conditional statement and now I negated the theorem "n is an integer and ((n is odd and n^2 is even) or (n is even and n^2 is odd))"

[stark creek]

if n^2 is odd, then n is odd

i would try to prove that if n^2 is odd, then n is even

[scarlet current]

can i simply just go like if n^2 is even then n must be even (definition of even numbers) but it says n is odd when n^2 is even so contradiction?

[sour arrow]

@scarlet current
The question is a common example of the contrapositive

[stark creek]

or something like that

and prove by absurd

[sour arrow]

Do you have to do this one with contradiction?

[scarlet current]

no

[sour arrow]

Oh fuq sorry you need the iff

[scarlet current]

the textbook solved it by just showing

if n is odd then n^2 is odd and if n^2 is odd then n is odd

[sour arrow]

So there's two proofs in one statement here:
n is odd → n² is odd
n² is odd → n is odd

[scarlet current]

but what happened to the if n is an integer part

do we jsut ignore that?

[sour arrow]

"odd" is an integer property so it's already assumed haha

So yes it is kinda ignored

[scarlet current]

ah ok thanks for the help!

[sour arrow]

Did you need any other help with it?

[scarlet current]

no i was just confused because they ignored the conditional statement part

haha

[stark creek]

Find a recurrence relation to obtain the number of ways n poker chips (which can be blue, green, red or white) can be stacked without 2 consecutive blue chips.

im back.

so

[sour arrow]

Lol welcome back

[stark creek]

i think i kinda know where im going

well

no i dont nevermind

i suck at this

[sour arrow]

This one is tricky

[stark creek]

i can write it out for the first few sets

like 0, 1 and 2

[sour arrow]

How many ways can you stack one chip?

[stark creek]

4

[sour arrow]

The trick is to think top-down if that helps

[stark creek]

yeah thats what im doing

but it gets kinda fuzzy when theres multiple blues in different places

[sour arrow]

Think of the number of ways to write the order of the chips above position n, in terms of the number of ways to write the two positions above it

[stark creek]

okay

so two cases for this

one if the top most chip is blue

and one if the 2nd chip is blue

if the top chip is blue, there are 3 possibities for the 2nd chip

[sour arrow]

I had some serious trouble wording that haha

[stark creek]

hahah i think i know what you mean, i kinda remember from class

but my professors are just so vague about it

heres where im at right now
n-2 | RGW | B
n-2 | RGWB | RGW

those are two cases i guess

if the last chip is blue, the 2nd can be red green or white

and whatever comes before that is just the solution of n-2

and then if the last chip is NOT blue, then the 2nd chip can be any color

and all before that is the solution of n-2

so now i guess i have to add these, as they are totally parallel to each other

the first situation gives me 3An-2

and the other one 12An-2

but that doesnt look right

[sour arrow]

Let s(n) be the number of possibilities above position n for any stack, where the top chip is position 1, ect. Let's say s(any non-positive number) = 0

Let's say at position n, there's a blue chip. Then, there's 3 + s(n - 2) ways to stack from here up.

Let's say there's a non-blue chip at position n. Then, there's 3 + s(n - 1) to stack from here up.

Like you said, these are disjoint so we can just sum them.
s(n) = s(n - 1) + s(n - 2) + 6
@stark creek

Oof but that can't be right, that would imply s(1) = 6. Hmm.

[mystic moss]

say s(0)=1 and s(1)=4. then could it be that s(n)=3(s(n-1) + s(n-2))?

where s(n) is the number of ways to pile a stack of height n (sorry for abusing your notation kaynex 😅)

@stark creek

[bronze rain]

I think it is easier to look at recurrence equations for sequences ending with a blue or a non-blue chip. Then combining then. However the manipulations required for getting a recurrence for the total may not be the most straightforward and more importantly may not give much insight into the problem.

[mystic moss]

yeah, if you end with a blue chip you have one way to choose the blue chip, 3 ways to choose the previous chip, and s(n-2) ways to choose the rest. if you don't end with a blue chip, you have 3 ways to choose that chip and s(n-1) ways to choose the rest

which manipulations are you referring to here?

[stark creek]

oh

[bronze rain]

Ah right. I meant having separate b(n) and b'(n), and s(n) being their sum. But yes what you wrote is easy to see.

[stark creek]

ladies and gentlemen

i got it

n-2 | RGW | B
n-2 | RGWB | RGW

doing this

i realized that the one in the second row is just n-1

so the relation is An=3An-1 + 3An-2

i think thats what @mystic moss had said

[scarlet current]

how would you solve this? prove that 3^n < n! if n is an integer greater than 6. Would it be by induction?

[bronze rain]

Induction is the easiest I guess

[scarlet current]

i tried contradiction, contrapositive and direct

couldnt use any of those

[stark creek]

yeah

its induction

over the the set of integers greater than 6

so instead of analyzing p(1) you would use p(7) as your starting point

@scarlet current

[scarlet current]

is there any other way to solve it?

[brave lava]

https://i.imgur.com/Qqr05tt.png

is b possible here

im still confused on this

[weary tiger]

b is true

[brave lava]

thanks

[weary tiger]

you should probably either try to prove it or look at a proof of that tho

not good to mindlessly memorize things imo

[brave lava]

its in my book my friend showed me

thanks though

[gritty crescent]

A school has a certain number of students, and every student must participate in one of its 3 clubs. If each club has exactly 35 members and the only thing that is known is that 10 students are members of all the 3 clubs, find the minimum and the maximum possible number of students in the school.

I came up with minimum=60 and maximum=85 with a lot of contrived reasoning. Can anyone guide me through a legible solution?

[pale epoch]

how that minimum 🤔

[bronze rain]

Could you let us know your line of thought? Might be helpful to emphasize the points where you seem to be having trouble.

[gritty crescent]

Say there are 3 clubs, and 2 of them have a total overlap of 25 students. The 3rd club has 25 members who are not members of either of the remaining 2 clubs and has 10 more members who are members of both the other clubs. That gives me a total of 25+35=60 students.

[pale epoch]

but what if every student is member of every club

[gritty crescent]

The intersection of students in all three clubs is restricted to 10

[pale epoch]

is it?

[gritty crescent]

Yes

Uh let's ground some notation here. Suppose the clubs are denoted by A,B and C. Then $$n(A)=n(B)=n(C)=35$$and $$n(A\cap B\cap C)=10$$These are the only two pieces of information I have, and I need to find $$\max(n(A\cup B\cup C))\text{ and }\min(n(A\cup B\cup C))$$

[vital dew]

TedNowKaczynski:

[gritty crescent]

My contrived reasoning to get these values is to minimise/maximise the overlap somehow

[bronze rain]

Why do you believe that the case you considered actually gives the minimum? Or can you try to do better?

[gritty crescent]

This is precisely why I call my reasoning contrived

[bronze rain]

Your reasoning is intuitively on the right track but try not to limit the possibilities

[gritty crescent]

I'm fairly sure I'm missing out something

Mmmm maybe I should use rigour here

[pale epoch]

you can do less

better intuition is: you have 3*25 slots left to fill

[gritty crescent]

I'm aware that $$n(A\cup B\cup C)=n(A)+n(B)+n(C)-n(A\cap B)-n(B\cap C)-n(C\cap A)+n(A\cap B\cap C)$$

[pale epoch]

a student can fill at most 2 slots

[vital dew]

TedNowKaczynski:

[stray reef]

$|A \cup B \cup C| = |A| + |B| + |C| + |A \cap B \cap C| - |A \cap B| - |B \cap C| - |C \cap A|$

[vital dew]

Ann:

[gritty crescent]

Lel I did an overflow but I'm aware of it.

a student can fill at most 2 slots
@pale epoch

[pale epoch]

at least that's my intuition

so i think 48 is min

[gritty crescent]

That makes sense

[pale epoch]

and my quick sketch confirms that it's possible

[stray reef]

$|A \cup B \cup C| = 115 - |A \cap B| - |B \cap C| - |C \cap A| = 115 - 30 - \sum_{cyc} |A \cap B \setminus C|$

[vital dew]

Ann:

[pale epoch]

and the "a student can fill at most 2 slots" should show its the min

[gritty crescent]

Cyclic index

[stray reef]

im lazy ok

[gritty crescent]

and the "a student can fill at most 2 slots" should show its the min
@pale epoch I see, I'll try to sketch this rigorously.

[stray reef]

the sum is the number of ppl in exactly two clubs

[gritty crescent]

Oh, I see.

How about the maximum bit?

Am I off-track there as well?

[bronze rain]

Yeah the maximum was fine

[gritty crescent]

😌

Might get partial credit afterall

But I still need to figure out the minimum bit on my own.

Are "non-crossing" and "no isolated element" standard terminology in relations/combinatorics?

One of the questions I encountered today was about finding the number of non-crossing and "no-isolated element" relations from the set {1,2,...,k} to {1,2,...,n}

The two terms were defined, so I can clarify what they mean

[pale epoch]

never heard either

[bronze rain]

I'm guessing non-crossing is some kind of order condition on the images of the elements

[gritty crescent]

Okay, they did give formal definitions for both that I've now forgotten, but I can supplement the idea with a picture. If you place the elements of the sets {1,2,..,k} and {1,2,...,n} in parallel rows, when matching elements of first to second(to create a relation), none of the lines should intersect. This was roughly the idea of non-crossing relations.

[pale epoch]

combinatorics is so whack

[gritty crescent]

So say if you've got (1,1) and (2,1) in your relation, then you can't get (1,2)

[bronze rain]

Yeah that's what I guessed. Ah interesting it's relations not functions. That makes it not as easy as I had originally thought.

[gritty crescent]

This was the non-crossing condition. The no-isolated element condition simply met that every element should have at least one image, and every element of the set {1,2,...,n} should have at least one pre-image.

Yeah, relations are whack.

I tried doing the case for n=k, and realised on my way back from the test that I did that one wrong as well

Apparently I said the identity map worked, but there were more possibilities which I couldn't even count

[bronze rain]

So when you say intersect, is this allowed: (j, i) and (j+1, i) in that relation?

[glass condor]

If you place the elements of the sets {1,2,..,k} and {1,2,...,n} in parallel rows, when matching elements of first to second(to create a relation), none of the lines should intersect. This was roughly the idea of non-crossing relations.
oh god, I think I've got combinatorics flashbacks from this one

that's some classical task, but I most certainly don't remember how it's solved

[gritty crescent]

So when you say intersect, is this allowed: (j, i) and (j+1, i) in that relation?
@bronze rain As long as (j,i+p) for some p does not happen, sure.

Uh can you guys suggest some resources to get a hang of combinatorics and proofs based on them?

It's whack and I don't get it right most of the times, tripping over one thing or the other.

[pale epoch]

there is no overarching theory for combinatorics

[gritty crescent]

:(

[bronze rain]

A really really good book but I'm not sure if it's at your level is Jukna's Extremal Combinatorics

[gritty crescent]

Would a book on Discrete Math suffice?

[pale epoch]

every problem is solved by magic

[bronze rain]

But yeah combinatorics is more about problems and a wide variety of techniques

[gritty crescent]

The name sounds intimidating @bronze rain , I'm fairly certain it would be beyond me.

[pale epoch]

or by divine provenance

[gritty crescent]

I have neither

[bronze rain]

The first chapter or so is definitely accessible I think.

Jukna was the name of the author by the way in case that was confusing

[mystic moss]

about the problem--given a number of mappings between the two sets, could you do a stars-and-bars kind of argument on both sides?

[gritty crescent]

I hope you can forgive me for not knowing what stars-and-bars argument is supposed to be.

[bronze rain]

Yes that's what I was thinking could be done Madeleine

[mystic moss]

ah it's an aops thing I guess

[gritty crescent]

Might have to look up AoPS texts on combinatorics, perhaps they could give me some grounding.

[mystic moss]

and then maybe it could be a summation over all possible numbers of mappings?

@gritty crescent yeah I liked their combo books

[gritty crescent]

Thanks, I'll look into it. Maybe I need some more grounding in combinatorics before handling such problems.

While matching I came up with a pseudo-boolean value argument but it failed too

[bronze rain]

For the other no isolated one, do you have any ideas?

[gritty crescent]

With the picture at hand, I could choose to either map an element to its identity, or its successor/predecessor(in two separate cases) or both simultaneously. I could not discard the possibility of neither happening, though.

Nope honestly, I think the first condition that has to be placed is, in fact, the no-isolated elements one.

Not only this, I was actually asked to find a recurrence relation f(k,n) which described it

And then find the value of f(3,n)

[bronze rain]

That actually makes more sense than asking for a closed form expression.

[mystic moss]

there was another no isolated one? 🤔

[gritty crescent]

Hmm?

Oh, I've defined the terms "no-isolated elements" and "no-crossing" above

[mystic moss]

I'm apparently confused about the question ;-;

[gritty crescent]

Although a bit vaguely

[mystic moss]

hm okay

[gritty crescent]

I'll rephrase the question

[mystic moss]

thanks :))

[gritty crescent]

I'll try to be as coherent as I can

I have to find the number of relations from the set S={1,2,...,k} to T={1,2,...,n} such that:
i)Every element of S is related to at least one element of T, and every element of T has at least one pre-image in the relation(this is the condition of no-isolated element)
ii) If you place the elements of S and T parallel to each other in rows, and join the elements related to each other by a line, then the lines should not intersect at any point(this is the condition of no-crossing; there was a formal definition but I forgot it :3)
The solution is sought as a recurrence relation f(k,n).

[scarlet current]

why is set A and set B equal if and only if ∀x(x ∈ A ↔ x ∈ B)? why not ∀x(x ∈ A /\ x ∈ B)

(/\ meant as conjunction sign)

[glass condor]

because that'd mean both A and B are equal to the universal set 😛

[scarlet current]

ah right

[mystic moss]

well okay if you add another element to S, is it the case that you can only hope to add it to the last element in T?

and vice versa

[gritty crescent]

Yes, makes sense.

But it could be the case that it can be joined to its predecessor as well

[mystic moss]

whose predecessor?

[gritty crescent]

Ummm suppose that n>k. Then, k->n as well as possibly k->(n-1).

[stray reef]

what's ->

[gritty crescent]

I guess that works regardless of the relation between n and k though

[mystic moss]

n needed to be connected to k-1 though

[gritty crescent]

Maps to

[mystic moss]

like {1, 2, ..., k-1}

[gritty crescent]

I so wish to be able to draw on the screen atm :3 lemme grab a quick visual from GeoGebra to clarify what I meant

So here, k->n as well as k->(n-1)

[mystic moss]

right, but if we consider recursion, we're adding vertex k to the existing relation between {1, 2, ..., k-1} and {1, 2, ..., n}

[gritty crescent]

Correct.

[mystic moss]

so n must have been connected to something before k

[gritty crescent]

I hadn't even thought about this problem in terms of recursion

I struggled to even get a basic idea of what sort of relations I'm looking for, then got stuck up in a jumble of combinatorial arguments

[mystic moss]

;-; this was for a test?

[bronze rain]

I think an idea is to pick the earliest neighbour of k and then see whether you want to allow that to be connected to others or not.

[gritty crescent]

I had my uni entrance today morning

This was one of the problems

[bronze rain]

Wild for an entrance test

[gritty crescent]

They take in olympiad kids, not very surprising

[mystic moss]

earliest neighbor of k?

[weary tiger]

huh

[bronze rain]

If (k, i) holds then (k, j) for all j > i. Unless I messed up somewhere

[weary tiger]

meanwhile American unis:
my life be like dat

[gritty crescent]

If all else fails I might head to American unis, ngl

[mystic moss]

right, yeah. you'd get that by starting at a scenario where k=k and n=i and then adding vertices to T until n=n, right?

[bronze rain]

Yes

[gritty crescent]

Question: Does this have anything to do with graph theory?

[mystic moss]

oh so when you mean choose the earliest neighbor, it's like a kind of fan almost

i don't believe so

[gritty crescent]

Oh, alright.

[weary tiger]

relations can be interpreted in terms of adjacency matrices so kinda

[scarlet current]

sorry to interrupt but why is A a subset of {a,b} when {a,b} is in set A?

[bronze rain]

But graphs are pretty nice that way. They model a lot of things.

[mystic moss]

yeah, that's true. i don't think any graph theory results are specifically used here though

[bronze rain]

I agree

[stray reef]

@scarlet current where does it say that A ⊆ {a,b}?

[scarlet current]

sorry to interrupt but why is A a subset of {a,b} when {a,b} is in set A?
@scarlet current oh nvm A is not a subset of {a,b}

got confused by the B

[gritty crescent]

Much thanks for the help everyone. I think I'm still lacking a lot of background knowledge here, so I'll try to study some combinatorics from AoPS first and then come back to this problem.

[scarlet current]

also what is the difference between {a} and a?

[gritty crescent]

{a} is the set containing the element a

[scarlet current]

ah i see

[mystic moss]

sure thing. when you do come back to it, do tell

[gritty crescent]

Thanks :) Your help is much appreciated.

[weary tiger]

competition math kids are something else

always blows my mind how early in life people can really delve into that world

[gritty crescent]

This particular test was neat, the problems were very descriptive and gave definitions, even hints and suggestions for almost all problems.

For instance, for this particular problem drawing a diagram was suggested.

[mystic moss]

i hope you do get into that college then, it seems nice

[gritty crescent]

Yeah, might have to try next year again, I plan to build some math background by that time but now I'm a bit split into thoughts.

I initially planned to study elementary analysis/abstract algebra in this gap duration but now I think I might have to focus on combinatorics/geometry which are relevant to the test.

[weary tiger]

check this out

if you move the parallel lines around into perpendicular ones, and curve the edges in the right way

wait nvm

[mystic moss]

it's nice that you can try again after you've studied more. also, gap duration?

[weary tiger]

oh wait yep it's fine:

every corner is a 1 in the adjacency matrix

elsewhere 0

and you always get something that looks like that with no crossings

[gritty crescent]

Hmmm, niceee, ConfusedReptile gave me a solution about antisymmetric relations based on a matrix argument too.

[mystic moss]

oh so like a path from the top left to bottom right?

[gritty crescent]

it's nice that you can try again after you've studied more. also, gap duration?
@mystic moss Ah, I got out of HS this year and covid happened, so the entire admission process got delayed by months. I might be on a gap year till the admission process next year now.

Ngl, I'm a bit glad it happened, I wouldn't have fallen for maths else if!

[mystic moss]

yeah, relatable. the two months after quarantine started was when i learned web dev :)) wouldn't have had the time otherwise

[weary tiger]

POG

[gritty crescent]

I wish I used the initial time in a better way though, if the realisation would've struck me earlier I might've gotten through but well, no point regretting now.

Web dev is cool

And tough Ig?

[mystic moss]

i wouldn't want to still be in quarantine when college starts though, that would be sad

yeah i'd originally wanted to because of web exploit in ctfs

[weary tiger]

but based on my drawing is there like something that's close to permutations but if you choose "none" as an option it cuts off the remaining options forever? Cause it's basically a k-repeating version of that

[mystic moss]

it's hard to attack something if you don't know how it works ;-;

"none" as an option?

[weary tiger]

Yeah so look at the options for the first column vertex's adjacencies to the row vertices

you have n choices, then none or n-1, or none or n-2, etc, and say where you pick none is m

and then for the second column vertex it's the same thing but for n-m I think

this interpretation probably makes things more complicated than other solutions though so maybe not worth pursuing

[mystic moss]

how do you get those choices for the first column vertex?

[weary tiger]

Ahh wait, it's close

It needs at least one adjacency, but the furthest one it can take is the n-k-th row vertex

err

wait no

[mystic moss]

hm?

[weary tiger]

I was thinking of this wrong

the first row vertex has to connect to the first column vertex

[mystic moss]

yeah, and it has to be connected to every consecutive vertex after that until it decides to leave the rest to the remaining vertices

this seems very related to stars and bars

[weary tiger]

havent taken combinatorics but looks interesting

[mystic moss]

yeah. also there are some edges in that diagram that can be potentially deleted, right?

[weary tiger]

yeah

[mystic moss]

oh interesting. we can think about this as the column vertices "claiming" subsets of the row vertices

[weary tiger]

and I think it's recursive from there

[mystic moss]

in this case, 1 gets 1, 2 gets 2, 3 gets 34, and 4 gets 5

i think we don't particularly need recursion in this case, perhaps?

[weary tiger]

so f(n,k) = (first row vertex's choices that leave n-s row vertices including the last one it connected to) + f(n-s,k-1)

[mystic moss]

yeah, that works

[weary tiger]

POG

[mystic moss]

we also have that k-1 can choose to connect to the n-sth vertex if it wants