discrete-math

[stray reef]

$A^3 = A \times A \times A$

[vital dew]

Ann

[near kiln]

I see

@stray reef Is this a correct example for chatgpt?

[stray reef]

!nogpt

[lofty cloud]

Please do not trust ChatGPT or similar AI tools for mathematical tasks, as they often generate output which "sounds correct" but has numerous factual or logical errors. Use of these AI tools to answer other people's help questions is strictly against server rules (see #rules).

[stray reef]

but in this case, yes, it managed not to fuck up.

[near kiln]

my bad, yeah I am aware of chatgpt being terrible at math

is

A = {(0,1), (0,3), (1,3)}?

@stray reef since it is squared therefore A X A, also the amount of element on the tuple depends on the amount of squared right?

in the earlier example it is A X A X A so it needs 3 element per tuple and all its combination?

[stray reef]

A = {(0,1), (0,3), (1,3)}?
no

i don't have the energy to get through your bad english right now, sorry

[near kiln]

np

[weary tiger]

could I get some help with double checking my answers for this hw? my grade can’t take a hit this late in the semester lol. Thanks!

[void sage]

hello people can anyone help in this problem? :does there exists an uncountable collection of countable sets with distinct cardinality?
if no can anyone show why its not possible?

what i tried in hopes of getting that its not possible that assume there is a collection possible then what i saw that cardinality being different implies atleast one has to be have greater cardinality than aleph null

[stray reef]

1 is probably ok if your class considers adjacency matrices as storing the weight of each edge -- if not, i would change all the nonzero entries in yours to 1
2a: why do you claim that there's no eulerian path in the graph? do you have a proof?
2b: "the graph doesn't pass thru each vertex exactly once" makes no sense.
(skipping 3, so as not to accidentally screw up the execution myself and feed you lies...)
4: replace the => with =
5a: correct
5b: incorrect, why do you start with a?
5c: same as 5b

[void sage]

but from there no idea came to my mind

[stray reef]

:does there exists an uncountable collection of countable sets with distinct cardinality?
let me clarify one thing

you want a collection of sets $(A_\alpha){\alpha \in J}$, where $J$ is an \textbf{uncountable} index set, satisfying the following:
\begin{itemize}
\item each $A\alpha$ is countable
\item for any $\alpha, \beta \in J$ with $\alpha \ne \beta$, we have $|A_\alpha| \ne |A_\beta|$.
\end{itemize}

did i understand you correctly?

[vital dew]

Ann

[odd heart]

And presumably they include finite sets in the "countable" category, since otherwise the answer is immediately no

[stray reef]

and by "countable" i suppose you mean "countable or countably-infinite"

^

@void sage confirm or deny that i understood you correctly.

[void sage]

yes exactly

[void sage]

you are right

[stray reef]

well

ok then let me ask you

how big is the set of possible cardinalities for the A's?

[void sage]

yes countable means both countably infinite as well as countably finite

[stray reef]

do you mean just "finite"?

what's "countably finite"?

[void sage]

yeah same thing

as 1,2,3,4 is a example of countable finite

[odd heart]

I recommend referring to those just as "finite"

[stray reef]

but why say "countably finite"?

[odd heart]

"countable finite" isn't standard terminology and is liable to be confusing

[stray reef]

like the word "countably" isn't doing anything there

anyway my question still stands.

[odd heart]

Although I love the idea of uncountable finite sets; sadly those don't exist within our framework.

[stray reef]

how big is the set of possible cardinalities for the A's?

[brave rock]

There exist uncountable finite sets, bc I can only count to 6. What comes after six??????

[odd heart]

Lots

[brave rock]

Okay so it's one two three four five six lots

Thank u

[stray reef]

https://www.youtube.com/watch?v=u8ccGjar4Es

obligatory mention

[fossil mural]

incorrect

it's n

[odd heart]

If you need to go even further, it's "hordes" and then "zounds"

[stray reef]

@void sage are you still here y/n

[brave rock]

Writing this down......

[void sage]

yes wait a min

[void sage]

yes take it as finite only for convenience of yours

[void sage]

yeah sure okay

[stray reef]

asking my question for a third time

how big is the set of possible cardinalities for the A's?

(this question is intended for you to come to an idea on your own)

[void sage]

i am thinking as the sets themselves must be countably infinite that means cardinality of those sets must be <= aleph null isnt ? otherwise it would be uncountable sets ?

now we want that indexing on those sets to be uncountable so that means the cardinality of those index is greater than aleph null ?

as in list of sets cardinality

[stray reef]

you have something that looks like the right idea, but you are dodging my question.

[void sage]

i am very sry

[weary tiger]

Just a set of decimal fractions. alpha is a real number, and A_alpha is the corresponding digits in alpha's decimal fraction.

[void sage]

limited to aleph null only ?

this was what you are expecting Ann ?

oh sry now got it

[stray reef]

i was expecting $\bN \cup {\aleph_0}$

[vital dew]

Ann

[stray reef]

or, if you consider $\bN$ to start at 1, $\bN \cup {0, \aleph_0}$

[vital dew]

Ann

[stray reef]

in either case, the set of all possible cardinalities for your A_α is itself countably infinite -- and there are by definition not enough of those to assign a different one to each of an uncountably-sized collection!

[void sage]

here you are assuming that suppose say cardinality is 5 also possible ?

as in finite ones also taken considered?

set

[stray reef]

i am not assuming anything

[void sage]

oh

[void sage]

okay i think i understand this just few points : why 0 and aleph null only possible ?

why specifically N U {0,aleph null}?

[stray reef]

???

why 0 and aleph null only possible ?
"Why are 0 and aleph_0 the only possible cardinalities?"
i did not say they were the only ones.

0 is the cardinality of the empty set, and aleph_0 is the cardinality of a countably-infinite set.
the cardinality of any finite set is a natural number.

[void sage]

okay you mean the upper and lower bound as {,}?

[stray reef]

??????

no

ok so i think this is a language barrier problem

what is your native language?

[void sage]

i mean to say that {a,b} generally means a set containing a and b as elements right ?

[void sage]

english

[stray reef]

{a,b} means the set whose elements are a and b and nothing else.

[void sage]

oh now i got it

i think

you mean possible cardinalties being any number betwwen 0 to aleph null

now its okay ?

[stray reef]

50%

[void sage]

oh

[stray reef]

you are right by coincidence, but my notation did not speak of any "betweenness".

the possible cardinalities of a countable set are precisely:

• 0
• the natural numbers
• aleph_0

{0, 1, 2, 3, 4, ..., aleph_0}

or {0, aleph_0} ∪ {1, 2, 3, 4, ...}

or {0, aleph_0} ∪ N

do you understand now?

[void sage]

yes this i understand now

just was looking at the last claim

which claims that this not possible

[void sage]

the set of possisble different cardinalities is countable infinte because we can label them even though last term is aleph null we can still label them and know what the next element can be ?

from a particular i th index

[stray reef]

no, countability has nothing to do with any notion of "next"

[void sage]

okay leaving the next just labelling is fine ? we ca do that here ? hence countably infinite ?

[stray reef]

"labelling" is bad

i think you don't know or don't remember the definition of a countable set

you should reread your notes or textbook to refresh it in your memory

[void sage]

one -one correspondence between natural number and that set ?

[stray reef]

yes

badly worded, but yes

[void sage]

so that means if i start from 1 then in all i am just doing a labelling with the natural numebers isnt ?

to that set given to us

sry if i am saying something very poorly

[stray reef]

you are saying many things very poorly, and i am struggling because of it.

i struggle both to understand you and to explain my points.

[void sage]

may you once tell your def of countable set ?

[void sage]

as in we required a mapping thats why i was thinking like this

[stray reef]

we call a set countable if and only if there exists a bijection between that set and N.

[void sage]

okay yes thats what i also knew

i will stop using labelling then

just a mapping is needed will say then

[stray reef]

i have to go, sorry

[void sage]

yeah i have understood your claim thanks

[void sage]

thanks for the extreme help

even if didnt manage to understand some parts but will try to understand better

[weary tiger]

Made changes based on the feedback you gave.

#1. We did it with 0’s (I included an example we had for reference).
#2. EDIT: 2a is now “no there is no Eulerian path” and 2b is “yes it is Hamiltonian.” The graph itself is a Hamiltonian path, but not sure if the whole thing is. Also, idk if (c) is right - probably not.
#3. Changed it to “=“
#4. Fixed (b) and (c).

#5. Were you able to check this one too? The Huffman tree on the last page

@stray reef

[void sage]

completely understood thanks Ann

Does there exists an infinitely countable collection of uncountable sets with distinct
cardinality?

[storm pumice]

does anyone here speak german?

[muted gate]

hey guys, quick question

say I have a set A

and consider A \ {a}, where a is an arbitrary element of A

how do I write the complement of A \ {a}

A \ (A \ {a})?

what is this equal to

the empty set?

or just the singleton {a}

[brave rock]

{a}.

[muted gate]

alright thank you!

[void sage]

anyone pls help?

[lyric quartz]

You can ask questions in non-English languages in the help channels.

Or you can try to ask in English and use some German terms if you don't know the English words

[compact yacht]

Are you familiar with the axiom of choice?

[white zealot]

Since I'm here, I may as well ask about where I might be able to find extra practice for sequences. Easily my weakest unit so far. I've done the chapter exercises and I'm still not 100% comfortable with them

[void sage]

yes

[void sage]

i can take a element out of it using axion of choice from a uncountable set and still it be a a uncountable set but then still distinct cardinality is not there in this .plus its an uncountable list

[ruby shale]

Im not sure, but maybe check Khan academy? they have practices on a lot of math concepts so I would recommend checking there?

[void sage]

you were writing something ?

[compact yacht]

I think you can show there is a function $f: \mathbb{N}_{\le n} \to \mathbb{O}$, where $\mathbb{O}$ is the class of ordinal numbers such that $card(f(i)) < card(f(j))$ if $i < j$, from this you can use axiom of choice to construct an infinite set of sets with different cardinalities

[fossil mural]

that... technically works but is overcomplicated

[vital dew]

Leu

[void sage]

does this list work ? power set of natural numbers and then power of power set and the series goes on? all are distinct and also that we have a countable indexing of the list ?

[void sage]

any simple way ?

[fossil mural]

well there's the way you just found

[compact yacht]

I agree :V, I don't know how to make it simpler though

[fossil mural]

this works

[void sage]

thanks

[fossil mural]

i honestly don't know how you get... sequences of cardinals of every finite length... without just constructing an infinite sequence of cardinals

also since the ordinals are well-ordered you don't need choice even if you're doing that

also like just use the $\aleph$s or something

[vital dew]

bee [it/its]

[compact yacht]

I don't think you can conclude that without choice

[fossil mural]

for each n just take the lexicographically first function with that property from N_{<= n} to the ordinals, that avoids choice

but i meant in terms of like

what actual construction did you actually use that doesn't automatically get you infinitely many cardinals

[compact yacht]

From this you'd have a countable infinite collection of sets A_i, such that a_i < a_j if i < j and a_i \in A_i and a_j \in A_j

But then don't you need choice to contruct the actual set?

[fossil mural]

...i have no idea where you got that from, that is not what you'd end up with at all

but if you somehow did construct that, you can then just take minimums again

[compact yacht]

You mean the functions I said earlier?

[compact yacht]

If that is the case you could then show that from every n you can take A_n = {f_n(n}},

You could probably just to It directly using induction I'm not really sure

[fossil mural]

nope that doesn't work

i mean you can do that but it's entirely possible that they just all give you the same cardinal which wouldn't be helpful

[stray reef]

wait so what's being discussed rrn

rn*

[fossil mural]

good question

[stray reef]

im a little out of the loop even having read the backlogs

[fossil mural]

the original question is whether there's a countable set of distinct uncountable cardinals

[compact yacht]

I'm trying to understand the flaw

[fossil mural]

obviously there is, but now we're on a tangent about a proposed solution that uses the axiom of choice unnecessarily and that i think is overcomplicated

[compact yacht]

I mean, it isn't for me, I'm trying to understand why there is, and I asserted since the beginning I wasn't completely sure about it

[fossil mural]

just start at any cardinal and repeatedly take power sets and you get infinitely many distinct cardinals

[compact yacht]

Yeah, got it now, each step you have a well defined set for esch n 😛

[stoic jackal]

i've a question about the exercises 15,1 and 15,2 of Numerical Methods for Engineers by chapra and canale anyone know ?

I have the solution but the results are somewhat inconsistent since the 15.2 is a continuation of the 15.1

[lean rover]

Let φ be the sentence "For all x, for all y, there exists a z such that if R(x, y) then R(y, z)", where R is a predicate symbol of two arguments.
Let A = {a, b, c, d}.
Define RM as the set {(b, c), (b, b), (b, a)}.

Question:
Do we have M ⊨ φ, where M is the structure with universe A and interpretation RM?

My Answer: I received a tip that whenever encountering an implication, I should always check if the condition p in p→q is false because then I can assert that it is true. So, in case (a), it states that for all x and for all y , R should hold. However, given x=a , it doesn't hold since there's no y for a . Therefore, I concluded that the model holds here. But I was wrong, and I don't understand what the answer sheet is telling me at all. Can someone please explain?

[fossil mural]

ok well it's not just the "if", there's also the quantifiers

"for all x, for all y, ..." is true if the rest of it is true for every choice of x and y

like for instance x=b, y=c

also i have no idea what you mean by "case (a)"

[lean rover]

better version of the question

[fossil mural]

running with this example: if phi is true, then there is some z such that if R(b, c) then R(c, z)

so what is this z?

and if there isn't one, then that means phi is false

[lean rover]

yes but given that the set is {a,b,c,d} don't we expect R = {(a,b), (b,c), (c,d), (d,a)}

because now for all x's there is a "y". a has b and vice verrsa, b has c and vice versa

etc...

[fossil mural]

well yes that's an example of an R that makes that statement true

but i thought the question was asking about R = {(b, c), (b, b), (b, a)}

[lean rover]

yes and thus I conluded that the p in (p->q) is false

and thus False -> Anything = True?

[fossil mural]

ok well that's not the right place to start from

the question we're considering isn't "exists z, if R(a,a) then R(a,z)"

it's "for all x and y, exists z, if R(x,y) then R(y,z)"

that statement is true iff it's true for every choice of x and y

that's what "for all" means

so if that statement is true then "exists z, if R(b,c) then R(c,z)" is true

and "exists z, if R(c,b) then R(b,z)" is true

and "exists z, if R(a,d) then R(d,z)" is true

there are 16 instances like this, and the statement "for all x and y, exists z, if R(x,y) then R(y,z)" is true if all 16 instances are true

[lean rover]

but R is a relationship tho so if we say for all x and y R(x,y) then it requires (a,b) (b,a) given a set of {a,b}

[fossil mural]

...we didn't say that

[lean rover]

sorry I'm slow

[fossil mural]

look at where the brackets are in the statement as they originally wrote it

for all x, for all y, exists z, (if R(x,y) then R(y,z))

[lean rover]

can you prove to me that this false using the set of alphabets?

I think I am getting there but Ima need an example

[fossil mural]

suppose it's true
let x = b, y = c, so we get exists z (if R(b,c) then R(c,z))
and for any z, this is false, because R(b,c) is true but R(c,z) is false for all z
which is a contradiction so it's false

alternative way to think about it: the negation of this statement is "exists x and y, for all z, R(x, y) and not R(y, z)"
so we take x = b, y = c, and then it is true that R(b, c) is true and R(c, z) is false

[lean rover]

Another thing if we say for all x and y we don't mean actually all possible x's from the universal set?

[fossil mural]

we do mean all of them

[lean rover]

Or is it that we found one case where the first holds but the second (q) in p->q doesn't hold?

[fossil mural]

exactly

a forall is false if there is any counterexample

[lean rover]

And since we are asked for all then False

[lean rover]

Thanks for the Help I really appreciate it!!

[near kiln]

What should I do here?

[restive flare]

think about it

[near kiln]

It's
true
false
false
true

my problem now is probably either I have to make it with example or not

[restive flare]

id check back over how you go to your answers. remember domain of all integers includes 0. This should help you with some of the questions when you plug things in.

[lean rover]

additional question about the same thing. If R had been R(x,y) = {(a,a), (b,b), (c,c)} then I would be right ?

No?

[robust hazel]

can anyone help me with this? like what am i supposed to do

[dull tartan]

So first you need to note what a tautology is

[robust hazel]

in language its when you repeat something often right?

[brave rock]

No

You're presumably working out of a set of course notes, or a textbook. Undoubtedly they explicitly define what a tautology is. You should go back and find the definition.

[robust hazel]

👍

[dull tartan]

I beleive ||a tautology is a truth statement that always evaluates to true irregardless of inputs||

(definitely try to find it in the book first before reading)

[robust hazel]

tommorow i have midterm and idk what to do i need to learn so many things

which one would you recommend me?

[brave rock]

I would recommend your course notes

[lyric quartz]

Just read two books before tomorrow...

[lethal prairie]

Definitely Susanna

[opal latch]

does anyone know if distributive properties apply to Zp if p is not prime?

p being a number in the natural numbers

[brave rock]

Yes.

[weary tiger]

can somebody help me with number 2

a) all i cant think of is n choose 4 which is obviously wrong

[weary tiger]

hello i need help with 4 discrete math problems anyone willing to help

[weary tiger]

Here are some visual hints in the order the images are posted

[urban ravine]

should just ask them (probably not all at once)

[hard citrus]

can someone explain why my thought process here is incorrect?
"In how many ways can four chessboard squares can be selected, if no two can be from the same column?"
i thought that for choosing the first squre we have 64 options, then for the second we cant choose that column so we have 64-8 ways, for the third 64-2*8 and forth 64-8*3

[left ridge]

You forget that the order of choosing 4 squares doesn't matter.

[hard citrus]

oh i see, thanks

[left ridge]

np

[hard citrus]

can someone help me with this i got stuck
i'm trying to find the number of ways to get the sum of 12 using 3 different 6-sided dice (each colored differently), so i set up the equation $x_1+x_2+x_3=12$ where $1 \leq x_{1,2,3} \leq 6$
which can be transformed into $x_1'+x_2'+x_3'=9$ where $0 \leq x'_{1,2,3} \leq 5$ and its at the next step i got stuck:
usually i would describe another variables $y_i$ such that they complement the former meaning $ 6 \leq y_i$ but in this problem it just doesn't work

[vital dew]

horizon2.0

[lyric quartz]

Can someone give a hint on how to prove that for an Abelian group any finite order |h| , if it exists, divides the maximal order |g|?
I thought about looking at |gh| since that has to divide lcm(|g|, |h|). But I'm not experienced with these number theory proofs...

[weary tiger]

Complementary method does work here

By stars and bars method, the whole number solutions to x_1' + x_2' + x_3' = 9 is (9 + 3 - 1)choose(3-1) = 11C2 or 55

Now subtract the whole number solutions when at least one of the x_i' ≥ 6

Or equivalently, finding the whole number solutions to:
y_1 + x_2' + x_3' = 3 (since only one of the x_i' can be ≥6 such that x_1' + x_2' + x_3' = 9)

And you can do the same with x_2 and x_3 as well, i.e., count them as well

[terse wyvern]

break problem up into 2 steps where two dice add to k and the third adds to 12-k

[terse wyvern]

prove for cyclic groups and then use fundamental thm

[lyric quartz]

Book hasn't said anything about cyclic groups or fundamental theorem

[terse wyvern]

that book is kinda shite then ay

[brave rock]

No

[hard citrus]

but you cant use the stars and bars method when the variables are upper bounded, no?

[lyric quartz]

This is the first paragraph on orders

[brave rock]

Using the fundemental theorem is overkill anyway

It's a good idea at least once to do this manually

[weary tiger]

You can if you're using complementary method

[terse wyvern]

oh yeah I suppose

yeah I see the proof now but it's weird that they don't discuss cyclic groups in the book

[brave rock]

You're right to look at |gh|. The idea is that you will be able to find an element of higher order by combining g and h.

[hard citrus]

in the third line is it strictly greater? not greater or equal?

[lyric quartz]

Higher order compared to h?

[terse wyvern]

well g and h

[brave rock]

Compared to g, hence giving us a contradiction.

[lyric quartz]

But g has the highest order

[brave rock]

Yes.

[terse wyvern]

yes

[lyric quartz]

Ok, i will try some more, thanks

[terse wyvern]

how are you boytjie

hows research coming along

[brave rock]

I'm on a short break at the moment, so not much research is happening

But overall OK

[terse wyvern]

nice

[brave rock]

You, trees?

[terse wyvern]

ok, final undergraduate* year

where the * is a natural extension

[weary tiger]

Yeah complement of x_i≤6 is x_i>6

[brave rock]

Best of luck

[hard citrus]

but x'_i is less than or equal 5, on the forth line i wrote

[weary tiger]

Ah mb

[hard citrus]

but still x'_2 and x'_3 are bounded by 5 so we cant use the stars and bars, otherwise why wouldn't we use it when we had x'_1+x'_2+x'_3=9?

[weary tiger]

@hard citrus edited

No basically here's the gist:

We first find the total whole number solutions of:
x_1' + x_2' + x_3' = 9

Then we subtract those solutions if at least one of the x_i' ≥ 6

All of this is equivalent to finding the number of whole number solutions when 0 ≤ x_i ≤ 5

I gtg now

[hard citrus]

i see what you're saying but, the way I've learned it is that if any of those variables are upper bounded (assuming if it was lower bounded you took care of it such that it lower bound is 0) then we cant use the stars and bars method to find the number of solution to that equesion, we must first use diffrent variables that are lower bounded by the upper bound and then subtract that from the universe

[hard citrus]

oh i see, thanks anyway, i'll try and look around some more

[hard citrus]

can someone do it as well to compare answers? i got 55-30=25

[weary tiger]

The last part is exactly what I did. The "universe" here is total whole no. soln of x_1' + x_2' + x_3' = 9

Make the upper bound as the lower bound:
5<x_i => x_i≥6
And subtract these cases from the "universe"

The only thing you need to take care of here is only one of the x_i can be ≥6 here, and not more than one at a time

[weary tiger]

Yeah the same answer

[hard citrus]

thanks i think i got the gist of it

[odd pendant]

i need help with a question can anyone plz help

Which of the following results need not hold in a ring (R,+,.)?

a+b=b+a ∀ a,b ∈ R
a.0 = 0.a = 0,∀ a ∈ R
a.b = b.a,∀ a,b ∈ R
a.(b-c)= a.b-a.c,∀ a,b,c ∈ R

i think option 4 is correct can anyone plz help

[stray reef]

do you have a counterexample for option 4?

[little prism]

and whats your definition of a ring

[tawny orchid]

help with combinatorics problem , in a car park there are 30 cars in a row , 8 of them have broken down , how man ypossibilities are there fo parking 30 vehicles ( always in a row ) , if every pair of broken down vehicles is seperated by atleast two good vehicles

[stray reef]

@tawny orchid progress?

[tawny orchid]

my progress is $\binom{20}{4}$ if the order of broken doesnt matter and multiply 8! otherwise

[vital dew]

Kapa

[stray reef]

how did you get $\binom{20}{4}$ and what does this count represent?

[vital dew]

Ann

[stray reef]

when i said progress i did not really imagine "wild guess out of nowhere without reasoning to support it"

[tawny orchid]

ill tell you my reasoning

$X_1 + X_2 + X_3 + X_4 + X_5 = 22$

[vital dew]

Kapa

[tawny orchid]

just imagine with me

for a second

[stray reef]

what are these X_i?

[tawny orchid]

ill get there

just imagine that those + signs are broken down vehicles

[stray reef]

also, just to confirm, there are 8 broken cars, yes?

[tawny orchid]

yes

[stray reef]

then why are there only 4 plus signs?

wouldn't you want $X_1 + X_2 + \dots + X_9 = 22$?

[vital dew]

Ann

[tawny orchid]

4 plus signs , because we can think of those broken down vehicles as pairs and their order doesnt matter

[stray reef]

but broken vehicles can't go together

every two broken cars have at least 2 good cars between them

[tawny orchid]

they are in pair

[stray reef]

no?

unless this is a language issue

[tawny orchid]

everytwo broken down vehicles have 2 cars that seperate

[stray reef]

yes

every two broken cars have ≥2 good cars between them

[tawny orchid]

its like u have NEW,NEW,NEW BROKENBROKEN ,NEW,NEW BROKEnbroken

[stray reef]

no

[tawny orchid]

$\overbrace{NNBBNNNBBNNNNBBNNBB}^{\text{one case approx}}$

[vital dew]

Kapa

[stray reef]

no

[tawny orchid]

yes what does that mean

[stray reef]

"every two broken cars have ≥2 good cars between them" means your row contains, in this order:

• some number of good cars (maybe 0)
• broken car #1
• at least 2 good cars
• broken car #2
• at least 2 good cars
• broken car #3
• (and so on...)
• at least 2 good cars
• broken car #7
• at least 2 good cars
• broken car #8
• some number of good cars (maybe 0)

[vital dew]

WanderingLethe

[stray reef]

^

like that

[tawny orchid]

oh

then its language problem for me

[stray reef]

did you translate?

[tawny orchid]

no its in my WS

[stray reef]

if you translated, then from what language?

[tawny orchid]

its in english

[stray reef]

right...

[lyric quartz]

Then what is the exact formulation?

[stray reef]

i was going to suggest a purely combinatorial solution, by the way.

[tawny orchid]

if i solved it the way i understood it

ist still correct?

[stray reef]

not quitee

you need to multiply by 22! as well to account for the order of the good cars

[tawny orchid]

english

[lyric quartz]

Yes, what is the exact formulation in your homework?

[tawny orchid]

yea 22! and 8! for the order of broken down

[tawny orchid]

ill write it

$Exercise 10 $ : In a car park , there are 30 cars in a row , 8 of them have broken down ,How many possibilities are there for parking 30 vehicles ( always in a row ) , if every pair of broken down vehicles is seperated by atleast two good vehicles? then generalize it

[stray reef]

the bot was pointless here

[tawny orchid]

yes

[stray reef]

also you could have taken a screenshot or picture

anyway

do you want to hear my purely combinatorial solution Y/N

[tawny orchid]

yes

[stray reef]

clearly the sticking point is finding the number of possible selections of 8 spots among 30 for the broken cars (since the answer to the problem will be that times 8! * 22!), so let's consider how we could do that.

imagine that there are 2 phantom cars at the end the parking row, and that they are always good.
then the condition "every two broken cars are separated by at least two bad cars" can be rewritten as "every bad car is followed by at least 2 good cars." (if a bad car is in any of the spots from 1 to 28, it'll have to be real good cars, and if a bad car is in spots 29 or 30, it'll have to be one or both phantoms)
this means that we are essentially arranging good cars and B-G-G groups in a row. there are 8 B-G-G groups (one for each broken car) and 8 single good cars (to bring the total length up to 32 -- remember that there are 2 phantom cars at the end.)
which comes out to ||C(16, 8) choices for where the broken cars can go.||

[tawny orchid]

oh yes thats actually the correct answer , thank you for your help

[tawny orchid]

by the way , i got the exact same soltuion if i solve it with X_i

wanna see it?

[stray reef]

i know the general idea of it

you can share if you want

[tawny orchid]

$X_1+X_2+...+X_9= 22 \implies$ we can think of $X_i$ as a box where u can put good cars and $+$ signs as broken down vehicles

[vital dew]

Kapa

[stray reef]

you could say that yeah

[tawny orchid]

how ever we know starting from X2 -> X8 they are all gonna be >= 2

so we can do change for variable

[stray reef]

or you could be more direct and say that X_i is the number of good cars in the interval between bad cars i-1 and i,
with X_1 and X_9 being the counts of good cars from the leftmost and rightmost ends resp.

but the logic afterward is all the same

[tawny orchid]

$Y_1 + Y_2 ... + Y_9 = 22 - (8-2+1)(2)$

[vital dew]

Kapa

[tawny orchid]

$Y_1 + Y_2 + ... + Y_9 = 8$ now number of solutions to this equation is $\binom{16}{8}$

[vital dew]

Kapa

[tawny orchid]

yes

thank your for your help ann

[lyric quartz]

I got the feeling I am only getting further away from the answer...

[stray reef]

what answer

[lyric quartz]

That if a finite order exists it divides the maximal order of an Abelian group

[stray reef]

... ? this wording sounds strangee

do you mean like

"let G be a finite abelian group and let x ∈ G, then ord(x) divides |G|"

this?

or you could also just (re)post your original problem in full cause im not at all certain we are on the same page here.

[lyric quartz]

No, Let G be an Abelian group and let g be an element of maximal finite order. Prove that for any element h with finite order, |h| divides |g|.

[stray reef]

so let G be an abelian group with the additional property that the set of all finite orders of its elements is bounded,

[lyric quartz]

And this is an exercise after the first paragraph about orders, so not many theorems in the toolbag

[lyric quartz]

yes

[stray reef]

i have a feeling that you could just consider the subgroup of G formed by all finite-order elements

oh but wait, we don't know that that would itself be finite.

[lyric quartz]

I do have a theorem that if g and h commute that |gh| divides lcm(|g|, |h|)

[stray reef]

right, and since we're in an abelian group, then we get commutation for free.

[lyric quartz]

Also that if gcd(|g|, |h|) = 1 then |gh| = |g| . |h|

[stray reef]

well, suppose gcd(|g|, |h|) = d < |h|

g is a max-finite-order element and h is an arbitrary finite-order element and our goal's to show |h| divides |g|, so we assume towards a contradiction that their orders' gcd is not |h|

what can you say about the element h^d?

[lyric quartz]

That its order is lcm(d, |h|)/d

[stray reef]

i mean you're technically right but

[lyric quartz]

oh 😛

[stray reef]

you understand that lcm(d, |h|) is equal to |h|

right

cause d is a divisor of |h| by construction

[lyric quartz]

oh right

[stray reef]

anyway yeah

so then what will gcd(|g|, |h^d|) be?

[lyric quartz]

let me check some gcd laws

[lyric quartz]

oh just 1?

[stray reef]

indeed

[lyric quartz]

So |gh^d| = |g||h|/d

[stray reef]

yeah, do you see the contradiction here

[lyric quartz]

d >= |h| while we said d < |h|

Thank you Ann, now for me to come up with this myself...

[lyric quartz]

So, how did you think about this? Just because we have a d, try if we can do something with it?

[stray reef]

my idea was to come up with an element with order coprime to |g|

[lyric quartz]

a and b are coprime if gcd(a,b) = 1, right?

And because |g| is maximal, the other element has to have order 1

I have never done any number theory, so this is pretty new. But the book assumes the reader knows some...

[stray reef]

yes

[weary tiger]

i dont understand this

i have k3,3 drawn on my paper but idk what homeomorphoism fully is

[lyric quartz]

Isn't a homeo a continuous bijection?

[weary tiger]

i have no clue what that means

[lyric quartz]

It's a bijection that preserves the topological properties, so i guess in graphs that means that you cannot break or create edges

But I don't know any topology or graph theory

[odd heart]

Two graphs are homeomorphic if you can make each one from the other by (repeateadly) adding/removing vertices of degree 2 along some edges.

I.e. replacing an edge with a vertex connected to both of the original endpoints

Or replacing a vergex of degree 2 with an edge between its two neighbors

So a triangle and a square are homeomorphic graphs

But neither of them is homeomorphic to a Y - shaped graph

https://en.wikipedia.org/wiki/Homeomorphism_(graph_theory)

Hm, I've only just looked at the screenshot and that description sounds like it's describing contractibility rather than homeomorphism, so no wonder you're struggling

I don't think the Petersen graph has a subgraph that's contractible to K(3,3), although it is contractible to K5

It does have a subgraph that's homeomorphic to K(3,3)

[weary tiger]

im tryign to map k3,3 onto the peterson graph then collpasing all the remaining points

but yeah its not working

[odd heart]

You need to remove a few edges from the Petersen graph

Note that you just need to find a subgraph that's homeomorphic to K(3,3)

[stray reef]

or a minor, no?

you can remove edges but you can also "smooth out" degree-2 vertices

[odd heart]

Yeah, that's the homeomorphism thing

[weary tiger]

ok so right now im trying to "smooth out" a subgraph of the peterson graph so its has 6 vertices that each have a degree of 3

[lyric quartz]

So compared to topology, in which a homeo is a continuous bijection and thus the preimage of every open set in the codomain has to be an open set in the domain. Is this equivalent in graph theory in the way that a bijections needs to preserve every path(?) in the graph?

[weary tiger]

i cant do it

spent an hour on it

[stray reef]

i mean you can tie it directly to the topological sense of homeomorphism

if you imagine a graph as a geometric entity where the nodes are points and the edges are curves (aka the edges are homeomorphic to a segment)

then homeomorphism in the graph theoretic sense coincides with the topological sense

[lyric quartz]

ok

[brave rock]

Well not precisely right, for example the graph •-• is homeomorphic to the graph •-•-•, if you'll excuse my lazy ascii rendering

I think this works under certain subtle conditions on the graph

[stray reef]

i mean those two are homeo in both senses are they not

topologically they are both just a line

[brave rock]

No, they are not isomorphic graphs

But they are homeomorphic topogical spaces

Oh wait I see, I misunderstood what was going on. My mistake.

[stray reef]

i didn't say they were iso as graphs

only homeo as graphs

[lyric quartz]

So how would you translate that to a topological space? Is that possible with a finite set of vertices? Because you can't have a bijection if you don't have the same amount of vertices right?

[stray reef]

if you imagine a graph as a geometric entity where the nodes are points and the edges are curves (aka the edges are homeomorphic to a segment)
that's the translation

are you familiar with the concept of gluing stuff together topologically

[lyric quartz]

I know about pushouts in HoTT... In which you glue points together

[stray reef]

i am decidedly not a HoTT person

you take a single point for each vertex, you take a copy of a segment for each edge, and you glue them all together in accordance with their incidence in the graph

the resulting topo space is the... i guess topological version of your graph

and my claim was that for two graphs, those things are homeo iff the original graphs were graph-theoretically homeo

[lyric quartz]

ok

I only know about the assembly language of topology a set M with a topology O \subseteq P(M), such that...

[stray reef]

how do you know hott but not the more picturesque bits of topology

[lyric quartz]

because HoTT is easier to do in a programming language

But I am now reading a book about abstract algebra to get some more basic fundamental knowledge. Topology is on the list as well

[terse wyvern]

imagine ignoring vertices and edges and thinking about a graph as lines on a surface of some genus

there's the space of the surface minus the graph and that's of interest to knot theorists I believe

[umbral glen]

I need some help solving this problem, I know the equation for repeated permutations is

$\frac{n!}{n{1}!n{2}!...n_{k}!}$

[vital dew]

BadChef

[umbral glen]

And so I derived a general case without the condition that each perm starts from an obj of an odd-numbered type

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

[vital dew]

BadChef

[umbral glen]

But I am unsure how to derive the case which satisfies the condition

[regal kernel]

Hello guys, help me!

[terse wyvern]

what do you need help with?

[terse wyvern]

?

[elfin furnace]

to find out which of the propositions are truw

true*

[terse wyvern]

do you understand the exists and for all symbol meanings?

[elfin furnace]

not really

ngl just speeding through homework so i can sit down and study the content later

[terse wyvern]

well its probably a good idea to do it the other way

look at the definitions for both and it should be easy

[hard citrus]

Can someone help me understand how do I prove this?
$$2n+1= \sum_{k=0}^n (-1)^k \binom{2n-k}{k} 2^{2n-2k}$$

[vital dew]

horizon2.0

[stray reef]

are you sure the left hand side is 2n+1

aight nvm theres no typo there by the looks of it

i'd try to look at the function $f(x) = \sum_{k=0}^n \binom{2n-k}{k} x^k$, or something similar

[vital dew]

Ann

[stray reef]

the RHS of your identity can be expressed in terms of that function.

[lyric quartz]

I just checked this again. Is that even true? I get that it has to be less than d, but it can be some other divisor less than d not equal to 1, right?

so then |h^d| is not coprime to |g|, and my proof fails...

[stray reef]

bézout's lemma

it states that the gcd of any two integers x and y is expressible as some integer linear combination of x and y

more precisely given x, y ∈ Z and d = gcd(x,y), there exist a, b ∈ Z s.t. d = ax + by

a corollary of this lemma is that if it's possible to express the number 1 this way from x and y, it means x and y are coprime.

ah wait, hold on.

that didn't quite work the way i imagined it, hang on.

[lyric quartz]

Ok, didn't know the Bézout Identity

ah so I want to find some x |g| + y |\phi(h)| = 1?

[vital dew]

Results provided by WolframAlpha

Click here to refine your query online
Upgrade to WolframAlpha Pro!

Requested by freerezervex

[fading steppe]

,ask How many 9-card hands contain four cards of the same value?

[vital dew]

Wolfram Alpha doesn't understand your query!
Perhaps try rephrasing your question?
Click here to refine your query online

Requested by freerezervex

[fading steppe]

,ask How many 9 card hands contain four cards of the same value?

[vital dew]

Wolfram Alpha doesn't understand your query!
Perhaps try rephrasing your question?
Click here to refine your query online

Requested by freerezervex

[signal plank]

brother someone plz help 🙏

In a standard deck of playing cards, there are 52 different cards. Each card is one of 13 different values, and one of 4 different suits (of which there are 2 red suits and 2 black suits). How many 9-card hands contain four cards of the same value?

[stray reef]

the bot won't do your questions for you

@fading steppe @signal plank are you two classmates or something?

[signal plank]

ye

we classmates

locked in 4 lyfe

[stray reef]

ok

have either of you made any progress on this problem?

[fading steppe]

lmao, kinda

[signal plank]

yea an attempt

[fading steppe]

but its like random conjecture

understand the base pincipal

[stray reef]

ok, can i see it?

[fading steppe]

so for 5 hands we had 13 x 48c1

[stray reef]

you mean for 5-card hands?

[fading steppe]

5 card hands yeah

[signal plank]

yea

[stray reef]

right

[signal plank]

ill post working in a sec

[stray reef]

yeah, that tracks so far.

[signal plank]

for 9-card hand

[stray reef]

ok, awaiting that.

[signal plank]

lmk if u want me to elaborate on anything

or if something is unclear

[stray reef]

13 * 48 * 47C4 is what i'm seeing from you

[signal plank]

yep

[stray reef]

i mean

"pick a card, then pick 4 not of the same value" is a bit troublesome

first, because you would probably wish to pick from 44 cards and not 48 -- and second, because those four last cards could form a 2nd four-of-a-kind among themselves.

which is that bad kind of overcounting that's hard to account for

[signal plank]

mhm

[fading steppe]

48c5?

[stray reef]

so here's my suggestion:

• first, count the hands with at least one four-of-a-kind in a similar fashion as you did for hand size 5 -- as 13 * 48C5, in this case
• then, observe that this will double-count precisely those hands which contain two four-of-a-kinds (i.e. stuff like AAAAKKKKQ)

so from that, subtract the number of hands with 2 four-of-a-kinds

[signal plank]

oh i see

so we do 13 * 48C5 minus the number of 2 four-of-a-kinds which we have to find

got it

[stray reef]

yes

and the hands with 2 four-of-a-kinds can be counted in a similar manner as well

and of course you don't need to worry about a 3rd four-of-a-kind bc there are not enough cards to make that :P

[fading steppe]

would two 4 of a kind just be 42c1 ?

[signal plank]

oh wowww it worked appreciate it

the way to find 9-card hands with 2 four-of-a-kinds is 13C2 * 4C4 * 44C1

and it all worked out from there

[stray reef]

what's the 4C4 for?

especially given that 4C4 = 1

[signal plank]

ah just since we have 4 cards of the same value

so i selected 4 cards from 4

it just made sense in my head

it might be a bit redundant but the general idea is there

[stray reef]

i mean there's only one way to do that

so it's unnecessary

[signal plank]

Fair

O yea I C that now

[tame bronze]

This is a discrete math problem, and I have no idea where to even begin
What area of discrete math would this be so I could research more into it

7. Suppose that $n$ cats and $n$ dogs are seated around a table$^1$ . Prove that, no matter how they are arranged, it is possible to find a starting point so that if one travels around the table clockwise, the number of cats one has passed is never less than the number of dogs one has passed.

[vital dew]

nogo

[tame bronze]

ping me if someone replies to this please

[agile magnet]

Have you tried this with small values of n?

Say n = 3 or 4?

Try some example seatings

[tame bronze]

seeing that both are n, it means whatever amount of cats there are must be the same amount of dogs
however i'm not sure if that assumption is correct, nor do I see how that assumption could show how cats passed never less than dogs

because if n = 3 for example, and if its random arrangement, you can get
(must start with cat)
cat dog cat dog dog cat
bold indicates a moment where # of cats passed is less than # of dogs passed

unless the question is asking the grand total at the end? im interpreting it as what is passed over in realtime

[tame bronze]

_ _
can anyone help with a fibonnaci sequence question instead?
got stuck at the end, not sure what to do from there

[agile magnet]

In your sequence of you start at the last cat

(remember they're sitting in a circle you can start anywhere)

It works

[lyric quartz]

The first line in the base case, should be gcd(f_1, f_0) on the rhs

[agile magnet]

I think for this k has to be at least 1, not 0

0 doesn't work as you can see

[tame bronze]

oups yeah, just wanted to show that k=0 doesn't work

[agile magnet]

Sure but it's not relevant for the proof

[tame bronze]

true i'll just remove it

[agile magnet]

And I'd argue including it makes the proof more confusing

If you want to say that, put that after the proof as a side note

[tame bronze]

but then you got cat > dog > dog and by then you would have seen 2 dogs before another cat no?

[agile magnet]

I said last cat

so cat cat dog cat dog dog

[tame bronze]

oo ok i see

not sure how to write that as a proof though but that helps thanks

[agile magnet]

Right so try some more examples

See if you can see that if the claim doesn't hold, you get some contradiction

[tame bronze]

alright i see now what you mean, and the statement is true
but still not sure how i can use something like a contracdiction to prove the statement is true for all n

since i assume i can't just show an example like n = 3, prove that is true

unless i can

[agile magnet]

no you can't

[tame bronze]

actually wait does it count as a proof to show that if n = 3, suppose you can't get more cats than dogs if you choose the order
and then proving you can acutally nvm that doesn't make sense yeah im pretty lost

maybe a proof by induction?

but then again no cause there's barely numbers to work with just words

https://math.stackexchange.com/questions/4794841/induction-proof-that-for-all-n-girls-and-n-boys-there-is-never-less-girls-th i found a stackexhange with basically the same question so i'll use this to guide me, thanks for the help on it though

they seemed to do induction not contradiction

[lyric quartz]

you meant this, right?
d = x |g| + y |h|
1 = x |g|/d + y |h|/d

If i then calculate |h^d g^d| = |h^d| |g^d| = |h| |g| / d^2 and thus |h| <= d^2
But that doesn't (directly) lead to a contradiction

[lyric quartz]

@stray reef and @brave rock I took a look at the hint by the exercise. It indeed say to assume that |h| does not divide |g| and then that follows that |h| has a prime factor with higher multiplicity than |g|. And it wants you to use that factor to construct an order

Then it is pretty easy. I should have looked at the hint, didn't wrote it down on paper and totally forgot about it... 😛

<@&268886789983436800> ^ spam

[sand pelican]

Hey guys, apart from using induction. Would it be reasonable to prove this equation by expanding the LHS and simplify?

[cedar spindle]

yeah

[sand pelican]

Thanks man, I just kinda need some source or someone that shows me how that is performed.

[lyric quartz]

Just expand it with the definition?

[meager prawn]

https://en.m.wikipedia.org/wiki/Hockey-stick_identity#Proofs

[zenith marsh]

I have just started to study Discrete Mathematics, and I have no idea how to solve this : A fighter fights in 10 consecutive days, at least one battle a day and the total battles are not over 15. Prove that there are consecutive days the fighter has fight exactly 4 battles.

I think it's Pigeonhole

[remote anvil]

I don't get the problem... suppose he fought 10 battles in total, one per day. I don't see any "exactly 4 battles" day

[zenith marsh]

i am confused too

[fossil mural]

it's a string of consecutive days

so if it's 1 per day, then any string of four days contained exactly 4 battles

[zenith marsh]

wot

wdym

[fossil mural]

well say that you had: 2, 2, 1, 2, 1, 1, 2, 1, 1, 1

then the first two days are two consecutive days, and have exactly 4 battles in total (2 + 2)

if it's 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, then [1, 1, 1, 1] is four in total

something like 1, 5, 1, 5, 1, 5, 1, 5, 1, 5 does not work, because "[1, 1, 1, 1]" is not four consecutive days (you'd be skipping over the days with 5 battles in between), but in that case the total number of battles is way more than 15

[zenith marsh]

hmnnnnnnnn

can it contain 3 ?

m only = 1,2 ,4 ???

hmnn i am figuring how to solve it mathematically

[fossil mural]

having 3 isn't a problem
like if you had 1, 3, 1, 2, 1, 2, 1, 1, 2, 1, then [3, 1] works because that's 4 in total

or [2, 1, 1], that's also 4 in total

[zenith marsh]

cool

[remote anvil]

probably start with n = 10 which bee already showed has a string of days with exactly 4 battles

then from there prove that it holds for n =11

and so on, building up to 15

[zenith marsh]

induction somehow?!?!

okayy thankyouu

[remote anvil]

not induction, exactly

somewhat less abstract

[zenith marsh]

okay

can I do something like this

suppose ai is the number of battles on ith day

sum of ai <= 15

i go from 1 to 10

suppose bi is the total battles up until the ith

bi is greater than 1 and less or equal to 15

suppose we have B = {b_1,b_2,b_3,b_4,...,b_10,b_1 +4,b_2 +4} this set has 20 elements from {1,..,19}

suppose bi = bj +4 then bi-bj = 4 means that total battles from i+1th day to jthday is 4

[zenith marsh]

can it be 1 consecutive day

like 4 battles in that day, is it satisfied?

[remote anvil]

I believe so yes

[remote anvil]

so I was thinking about the multiset formula. If you have a set of n elements, there are n + k -1 choose k sets with k elements, where each element may be repeated. it's explained pretty well here:
https://en.wikipedia.org/wiki/Multiset#Counting_multisets

but I would like to know if there's another way to go about it.

specifically, I would like to set up a bijection between k-multisets of a set with n elements (call that family A )and the k-element subsets of a set with n + k - 1 elements (family B), such that the sets of A with no repetitions are exactly mapped to the sets of B that only contain the first n elements. and the remaining sets of A, that is those that have repetitions, are somehow exactly mapped to the sets of B that contain at least one of the remaining k -1 elements. Can you think of a way to make this mapping happen?

[true condor]

its just when you sub it in right?

[left ridge]

yes

[true condor]

I have no idea how to get started for this one

[lyric quartz]

induction multiple choice...

[gilded silo]

what's an axiom of choice ?

[brave rock]

The axiom of choice is a particular assumption mathematicians make about the way sets work. It is used without worry in everyday mathematics and has subtle and interesting connections in the study of logic and formal set theory.

The wikipedia page is an excellent introduction if you want to know more.

[lyric quartz]

What are those interesting connections with formal logic and set theory?

Also doesn't it break higher inductive structures?

[brave rock]

What are those interesting connections? C is independent of ZF, amongst other things.

I have no idea what you mean by 'higher inductive structures'

[true condor]

so how do I start it?

[lyric quartz]

For example higher inductive types in HoTT, aren't those all contractible with the AoC?

[fossil mural]

all contractible? no, it's consistent with AC that a type with two distinct elements exists, and there are various higher inductive definitions that produce that type

it's certainly true that if you formulate AC in a way that's kind of just... wrong... then that ends up being inconsistent with univalence

[lyric quartz]

Well the higher structures contractible

[fossil mural]

i don't know if AC actually implies UIP and not just "not univalence"

[lyric quartz]

Ok

[fossil mural]

but yeah that formulation of choice is kind of just stupid?

if you assert the axiom of choice for sets then you don't get any problems

[lyric quartz]

Oh right, since identities on sets are already contractible (I think)

[lyric quartz]

Well what is the induction principle?

Univalence, AoC all little too far above my head...

[true condor]

u gotta assume smth and then use it ltr but I dont get where I am supposed to begin

[lyric quartz]

Not just something, what does your book say about the induction principle?

[true condor]

uhh.. you have to prove something for k'th element and make it work for k+1 element

[left ridge]

no. you assume it's true for k-th element, then use that assumption to prove that it's also true for (k + 1)-th element

[true condor]

oh yea that seems more familiar now

[lyric quartz]

Do you have a book? I would really advice to read about this and understand it fundamentally

[true condor]

I was js doin it from memory. I dont have my notes with me rn

[compact topaz]

bro

i dont like discrete math

but its part of my major

and its in flipped learning format

[remote anvil]

I didn't get any responses yesterday, and would like to ask this q again today. can somebody please help me find such a bijection? (or convince me it's pointless to look for one)

[remote anvil]

..I actually think I figured it out, if anyone's interested I'll explain what the hell I was thinkin about 😄

[true condor]

anyone know why this was wrong?

was it supposed to split the list into 2/4?

[sand pelican]

Could anyone confirm if this inequality is correct? It seems wrong to me

[brave rock]

Why does it seem wrong to you? It's a strong inequality – much stronger than it needs to be – since a sharp upper bound is n+1.

This follows from $\lfloor x \rfloor \leq x$ -- this is just part of the definition of the floor, if you like.

[vital dew]

Boytjie

[brave rock]

Here is the graph of 2+2floor((n-1)/2) in red, and n+1 in blue.

[sand pelican]

Hey man, so we could change the last lower bound from < to <=?

[brave rock]

Your image is correct

The text of your message is not, but I think you just meant to say "from <= to <" instead.

[sand pelican]

No, thats actually what I meant 'cause the last bound of the previous image is different

[sand pelican]

.

[calm sapphire]

In Boolean product of zero one matrices are actually multiplying ? In this Kimberly brahm playlist for discrete math, she does it using meet and join symbols.

In the other hand I did just by actually multiplying and got the same result

[opal crescent]

@calm sapphire at no point you do end up computing 1+1 anywhere in this example

that's why there's no difference to be seen

[calm sapphire]

can i assume, that my way of doing it will work for all matrices that satisfy mxk kxm (the dimensions of the matrices) so long that the matrices comprise of zeros and ones ?

[opal crescent]

what do you mean by will work ?

what I'm getting at is that the example in the video is not very well chosen

it doesn't highlight the difference between their "boolean product" and matrix multiplication with elements in F_2

the difference arises when you end up computing 1+1

@calm sapphire

[calm sapphire]

Gotcha thanks man !

Any chance you can give me a decent example?

[opal crescent]

make the zero in 2nd row 1st column of A a one

if you're doing the product in F_2, you'll get a 0 at position (2, 2) of the result

for the "boolean product", you'll get a 1 instead (cause it's using a regular OR for "addition", not an XOR)

@calm sapphire

[calm sapphire]

Goated thanks for helping satisfy an itch

Is there a fast way of doing this in ti84?

[opal crescent]

prolly not

[calm sapphire]

Fuh

Python it is

[opal crescent]

I'm pretty sure you can't specify to do shit in F2 by default on an ti84

let alone with their boolean product

[calm sapphire]

bro im such a noob with this calc that i have never used the F2 button lol

[calm sapphire]

no worries i wrote it code

save it for reference

someone had it on stackoverflow

[opal crescent]

I'm not talking about the F2 button, talking about this https://en.wikipedia.org/wiki/GF(2)

maybe you were just joking about the ti84 and the joke got over my head, just making sure we're talking about the same thing

[calm sapphire]

ohh ok, well I also didnt even know about Galios Field let alone F2

this was an interesting convo lol

[opal crescent]

better reread the whole convo now

[calm sapphire]

why do u think i missed something ?

[opal crescent]

I mentioned F_2 quite a bit

but the quick summary is 1+1=0 in F_2

[calm sapphire]

gotcha, does F2 show up in more advanced math classes, cuz in my discrete class they havent mentioned it at all

[calm sapphire]

F2 seems like an interesting abstract world

[opal crescent]

well if you're talking about binary data, F_2 shows up

[calm sapphire]

havent gotten to that in school yet

[opal crescent]

it's the mathy way of talking about binary

[opal crescent]

if you're taking linear algebra you might see it

also in cryptography and coding theory on the more CS side of things

anyway i gtg

[weary tiger]

how do i write $\dfrac{n(n+1)(2n+1)}{6}$ in terms of choosing formula $\binom{n}{k}$?

[vital dew]

Derivative

[mental mirage]

u really cant to match the degrees the only choice is C(n,2) which doesnt satisfy

[stray reef]

$\binom{n(n+1)(2n+1)/6}{1}$

[vital dew]

Ann

[stray reef]

@weary tiger

[mental hull]

Is this not just 271? One 10*10 square, one 9*10 square since it shares a side with the first, and one 9*9 square since it shares 2 sides with the first 2

[stray reef]

was 271 rejected?

[mental hull]

No

I’m just checking

[stray reef]

well you are right

[mental hull]

Thank you

[agile token]

does anyone have some good resource for how to solve recurrence relations with generating functions?

[wintry anchor]

There are many. Example:

• https://ocw.mit.edu/courses/6-042j-mathematics-for-computer-science-fall-2010/resources/mit6_042jf10_chap12/
• https://math.libretexts.org/Bookshelves/Combinatorics_and_Discrete_Mathematics/Applied_Discrete_Structures_(Doerr_and_Levasseur)/08%3A_Recursion_and_Recurrence_Relations/8.05%3A_Generating_Functions
• https://www2.math.upenn.edu/~wilf/gfology2.pdf

[viral crown]

gfology

[unique girder]

I just finished a problem proving that if G is a planar graph with at least 4 edges and no triangles, then m <= 2n-4, where m is the size and n is the order of G.
The next problem is to prove that if G is a toroidal graph with at least three edges, then m <= 3n, but I can't use n-m+r=0 for toroidal graphs, and I'm struggling to find an approach

r is the number of faces in the embedding

[narrow ocean]

With the pigeonhole principle, can I have a variable number of slots, for example can I say three slots to add up to at least 21 if I have 37 slots with 6 items and 2 slots with 7 items, and I try to put 261 items in, since 37 * 6 + 2 * 7 < 261

[agile magnet]

Depends on the problem you're trying to solve

[pure vale]

With given results can u generate functions

[agile magnet]

And how you want to model it

As in what does a variable number of spots represent in your given problem?

[golden orchid]

What is here about?

[mental hull]

Discrete math

[narrow ocean]

Each spot represents a department and I'm trying to say that if 37 of the departments can have 6 professors in them while 2 can have 7 professors then any more of then the max number of professor slots would result in at least one combination of departments with 21 or greater professors.

It makes sense intuitively I'm just not sure if its a proper use

[umbral glen]

For the following problem:

How many permutations can be formed from 2n types of objects with n1 objects of each
odd-numbered type and n2 objects of each even-numbered type and each permutation
starts from an object of an odd-numbered type?

Would I say there are n1 possibilities for the 1st element of every permutation or n * n1?

[warm flower]

Having mild brain fart, anyone got any suggestions for how to transform (\bigcap_{n \in \mathbb{N}, n \geq k}E_n) into something only using finite union,intersection,difference or the full (\bigcap_{n \in \mathbb{N}}E_n)?

[vital dew]

StarvinPig

[agile magnet]

I mean $$\bigcap_{n \in \mathbb{N}, n \geq k} E_n$$ seems clean enough to me. Can you be more specific about what else you want?

[vital dew]

Spamakin🎷

[warm flower]

I needed to go show this was measurable so I wanted to see if I could represent it in a form of stuff we've shown is measurable in class. But I just did a workaround by making (F_{k,n} = \begin{cases}
X & n < k\
E_n & n \geq k \
\end{cases})

[vital dew]

StarvinPig

[fossil mural]

let $E_1 = \varnothing$ and then the $\bigcap_n E_n$ becomes useless, so it's impossible

[vital dew]

bee [it/its]

[fossil mural]

couldn't you just do the indexing differently...?

$F_n = E_{n+k}$

[vital dew]

bee [it/its]

[warm flower]

Same difference basically

[wraith pelican]

What do I_x and I_y mean in this context?

[stray reef]

identity functions on X and Y respectively

[wraith pelican]

What exactly does that mean?

[stray reef]

$I_X: X \to X$ is the function which sends each point of $X$ to itself

[vital dew]

Ann

[stray reef]

$I_X(x) = x$

[vital dew]

Ann

[wraith pelican]

okay that makes sense. Thank you

[umbral glen]

Would really appreciate if someone helped me with this. Would the first element in a permutation with these conditions have n * n1 or n1 possibilities ?

[weary tiger]

can someone help wiht this?

using handshake lemma I get

2E = 29 + x

29 is the degrees from the question

x is the vertices of degree one (the leaves)

[wraith pelican]

Can anybody help me get started on this problem? I'm totally stuck

[errant bear]

you can start with g(f(x)) = x

@wraith pelican

[hard hazel]

Whats the rule for multiplying a scalar to a congruence class? like what is 2 x [a] or 2[a] ?

[near kiln]

I was wondering why it has to divide the factorial of 11 by the duplicate letter in the word.

So I am guessing that 11! is the combination of every possible arrangement, but it can contain duplicates, so by adding the factorial of duplicates in the denominator, we can do something like an equation thingy that can easily remove all duplicates.

So in the second photo, it is basically subtracting all of the denominators until 1 is the only one left.

I hope you guys catch my drift.

[calm sapphire]

guys im watching this video (current timestamp) https://youtu.be/uGxPGT6boYQ?list=PLl-gb0E4MII28GykmtuBXNUNoej-vY5Rz&t=529 , I don't understand why relation R_3 works

[brave rock]

If by "works" you mean "is antisymmetric," this is vacuous truth. Falsehood implies anything.

There are no pairs (a,b) where a R_3 b and b R_3 a, so vacuously, any such pair must satisfy a = b.

You know this from the early days of truth tables where you learned False → True and False → False both hold.

[calm sapphire]

homie i think I got it, but its so counterintuitive for me

[calm sapphire]

did she make a mistake on R_4

[brave rock]

No.

[weary tiger]

anti-symmetric means a to b is true but you cant reverse it

so if a=3 and b=2 then a>b

but if you flip it to b>a then its false

yall gotta stop explaining stuff as if we already know discrete maths lmao

[calm sapphire]

Say it louder for the ones in the back

[calm sapphire]

Got it, is this a vacuous truth ?

[weary tiger]

i forgot what that means ngl but a>b and b>a is false no matter what

cause if a>b then b>a is impossible

[wind harbor]

Hello everyone, I am currently self studying basic propositions and am wondering if these word question type of problems will ever come up? I am pursuing a minor in math and major in CS (question 7)

[agile magnet]

This would not be our of place in an intro to discrete math type course

Which CS and math majors both have to take some version of

[spark gazelle]

can someone help, I'm having trouble with the non-homogenius part. when I substitute it into the relation, it equals zero and I'm sort of lost on what I should change

[cursive nymph]

guys, why is that?

some visuals for the context

[stray reef]

a priori you don't know which way you need to permute your input elements in order to sort them correctly.

therefore your algorithm needs to be able to permute them every which way.

[cursive nymph]

Ooooooh man. I misread it and thought that the tree must have at least n! comparisons
Whereas they just mean the leafs

thanks

[stone peak]

anyone know why this isnt 36?

the solution says 40

because apparently u dont use inclusion exclusion princple

but I dont see how doing:

5 * 4 + 5 * 4 isnt double counting

dont u have to subtrack the intersection?

[cursive nymph]

I was trying to show that
$$
\max{(f(x), g(x))} \in \Omega(f(x)+g(x))
$$

Does the following argument work?

$$
\underbrace{\frac{1}{2}}_{C} \cdot (f(x)+g(x)) \le \max{(f(x), g(x))} \quad \forall x
$$

since if we rearrange it just becomes
$$
f(x)+g(x) \le \max{(f(x), g(x))} + \max{(f(x), g(x))} \quad \forall x
$$

[vital dew]

Sweet Tea 🧋

Sweet Tea 🧋

[cursive nymph]

nvm, got a reply in another channel – looks good

[cerulean wind]

you could also use max{a,b} = [(a + b) + |a - b|]/2

[ionic lodge]

something is wrong with my solution
pls helps

[cursive nymph]

Guys, I'm struggling a bit to show that if
$$ n! \ge 2^{h(n)}$$ then $$h(n) \in \Omega(n \ln n)$$

I'm certain I have to use Stirling's formula for that, and here's what I have got so far

[vital dew]

Sweet Tea 🧋

[cursive nymph]

but idk how to rigorously conclude that h(n) in Omega(n log n)

[ionic lodge]

soz its not really readable
but i explain properly
see
i solve homogenous part and got the root
then i have basically two exponentials, one is (1)^n and the other is 2^n
so since 1 is also a root, the solution is of a different form...
and let's just skip the trivia because the particular solution I found is correct according to the solution given.
I completed step 1 properly but i messed up somewhere in the start of step 2
i need help

this is the qustion

[cursive nymph]

And I can't even use this result, since the -n term is not non-negative

[cursive nymph]

I meant this -n ofc

omg, I'm dumb. We can group the n ln(n) - n as n(ln (n) - 1) and consider the case when n >= e

Ok, this approach looks much easier

But how do I get rid of the -ln(2)/2 constant?

[ionic lodge]

finally solved it

[prisma verge]

can someone help

[merry storm]

u can visualise A product B drawing x and y axis

draw ur first set A on x axis as a segment, draw C there intersecting it. set A should be a strip in R2 plane. C should be strip as well. Also visualise B and D - on y axis. Then draw it for the right set

u will see that left one lies in the right one

[prisma verge]

but

without graph

[merry storm]

fix any x from the left set - a union of two pairs and show that it lies in the right one

[merry storm]

not correct, the left set are just pairs

all pairs (a;b) such that a from A, b from B united with all pairs (c;d)

of course every such pair would be in the right set as well

because in the right we have all of them and a lot of other pairs - (a;d) for example

[prisma verge]

tyty

HELP

@merry storm

sorry for ping

[merry storm]

idk what they want

[prisma verge]

likeee a formulaa for the sequence

[merry storm]

an = ceil(n/2)

[prisma verge]

idk what ceil iss

[merry storm]

google

its a function

[prisma verge]

can u help with this pleaseeeeeee

@merry storm sorry for the pingg but i really need helpppp

[tardy finch]

do you know how to use induction

[prisma verge]

no

[tardy finch]

whats this for?

[tardy finch]

do yk how it works? the answer wont make sense

but dw its not tough to understand

[prisma verge]

i dont, we learned it in school but i didnt study that

[tardy finch]

alr quick example

say we had dominos lined up

and then we make them fall

why does the 4th one fall? or the 9999th one? (suppose we have a large number of them or something)

we can say that a domino falls if the one before it falls on it right

then if the first one falls, the second one will fall because the one before it fell
the third one will fall, because the one before it fell
the fourth one will fall, because the one before it fell, and so on

we induct over the natural numbers with the same logic
suppouse we have a proposition P and we want to know if P is true for all x in N
if we know that P is true for k+1 whenever its true for k
and that its true for 0, our dominos will start to fall
so If P(0) and P(k+1) if P(k), then its true for all N

[tardy finch]

to prove that this is true for all n in N
we show that 1. its true for 0 and 2. its true for a number when its true for the number before it

$0 \cdot 2^0 = 0$

[vital dew]

aÿb

[tardy finch]

$(0-1)2^{0+1}+2 = 0$

[vital dew]

aÿb

[tardy finch]

so its true for 0

$2 + ... + k2^{k} + (k+1)2^{k+1}$

[vital dew]

aÿb

[tardy finch]

now we suppose the proposition is true for k

and we show that if its true for k its true for k+1

$\underline{2 + ... + k2^{k}}+ (k+1)2^{k+1}$

[vital dew]

aÿb

[tardy finch]

first step is to substitute since we assume its true

$(k-1)2^{k+1}+2+(k+1)2^{k+1}$

[vital dew]

aÿb

[tardy finch]

then distribute

$k2^{k+1}-2^{k+1}+2+k2^{k+1}+2^{k}$

[vital dew]

aÿb

[tardy finch]

combine the alike terms

$2 \cdot k2^{k+1} + 2$

[vital dew]

aÿb

[tardy finch]

this is the same as this

$(k)2^{k+2}+2$

[vital dew]

aÿb

[tardy finch]

so the formula is true for k+1 if we suppose its true for k

[prisma verge]

thank you so much!

[ionic lodge]

second case is frying my brain up

oh bard is good at this

[silver panther]

To prove it without induction you can use calculus

Let $f(x)=\sum_{j=1}^n j x^j=x\sum_{j=1}^n jx^{j-1}=x\sum_{j=1}^n \frac{d}{dx}(x^j)$

Then you can swap the sum and the derivative. The resulting sum will be a geometric series.

$=x\frac{d}{dx}\left(\sum_{j=1}^n x^j\right)=x\frac{d}{dx}\left(\frac{x(x^n-1)}{x-1}\right)$

Then differentiate and replace $x=2$

[vital dew]

Max

[spark gazelle]

Can someone please double check my induction step here, I have my midterm today and need to be sure I did this right. Thanks

[stray reef]

,rccw

[stray reef]

your answer is correct so you made an even number of mistakes

and that number is 2

the second bracket should have been expanded as -30*3^(k-1) + 18*2^(k-1)

then later the -15 and +9 coefficients on the 2^k would have combined into -6 as they are supposed to

[spark gazelle]

Ty!

[spark gazelle]

I also have a question about these if anyone is willing to answer, what do I need to do to make the non homogenous part not equal zero?

[vivid steeple]

Can someone please help me with this...
When someone says
a ≅ b mod c

They mean that when 'a' is divided by 'c', it leaves the remainder 'b'.
So 'c' is the remainder here.

But also people say that
a mod b means the remainder of the division of 'a' by 'b'

For example, when proving the associative law,
(a + b) mod n = ((a mod n) + (b mod n)) mod n,
People prove it by considering the remainder of division of a by n, b by n, and a+b by n, so I'm really confused what is what now

[stray reef]

a ≅ b mod c
They mean that when 'a' is divided by 'c', it leaves the remainder 'b'.
not quite

also usually the symbol is ≡

a ≡ b (mod c) means that a and b have THE SAME remainder upon division by c.

For example, when proving the associative law,
(a + b) mod n = ((a mod n) + (b mod n)) mod n,
wouldnt call this the associative law, and also this is usually not how mathematicians use the word mod

that usage is more like the % operator in languages like C/C++ or others influenced by it

[cyan loom]

one other way to think about it is

modular arithmetic divides all numbers into buckets (numbers with the same remainder)

a = b mod c just means a and b are in the same bucket (and that the bucket is called a)

ex. 24 mod 13 = 50 mod 13 = 11 mod 13 = 11

in general the buckets are labeled by the smallest positive number

[stray reef]

@cyan loom you're using the symbols % and mod in almost the opposite way to me, and this is bound to cause confusion...

[cyan loom]

ph sorry i probably shouldnt use % like that

mod exclusively refers to the equivalence classes

[analog tinsel]

Hey guys, has anyone ever heard of clarkes proof of the cayley formula and knows where I can find a copy of that? Only one I have is in our script but its quite confusing and not very elaborate and apparently its nowhere on the internet

[regal kernel]

Hello guys, I need help about relationships in discrete mathematics, I need your help, I am going to do the exercises but I need you to advise me, help me:

[brave rock]

You should ask a specific question about what you need help with. If you just ask for help it's too vague to do so.

[dire stag]

I take the conditional statement "if every integer n is even, then 3n-11 is odd", and I get its contrapositive:

If 3n-11 is even, then some integer n is odd

But for whatever reason, I cannot use any method that I had which shows that n is odd

I can't factor it, and with what I have right now, it shows the complete opposite of what I'm trying to prove (n is odd)

[fossil mural]

...i'm not sure what you mean by "can't factor it", but also the definition of "3n+11 is even" is definitely not "n = 2b for some integer n"

[dire stag]

here's an example that I'm trying to work off of

I'm trying to simplify 6b-11 to become 2a+1 (the definition of odd numbers) to prove that n is odd

[fossil mural]

ok well that's a reasonable example (apart from the part where you numbered the steps 1, 2, 3, 4, 5, 7, 6), but you do have to keep track of what it is you're actually trying to prove

[fossil mural]

this would not prove that n is odd

this would prove that 6b-11 is odd

and 6b-11 is not n

[dire stag]

hmm

I also have this one, but I'm not sure how to apply it to what I'm working with

[fossil mural]

i'd say don't try too hard to follow an example you already have? just look at what the definition actually says

if 3n-11 is even, then that means 3n-11 = 2b for some b

it doesn't make a difference that "3n-11" is a more complicated expression instead of a variable, it's still just some number

[dire stag]

hold on. Give me a second.

HMMMMMMMMM