discrete-math

[last timber]

finally did it haha

[languid flint]

just one more step, from that G(x), I have to get S(k)

like

I need to find the sequence whose generating function is G(x)

and folks, that is how we solve a recurrence relation using generating functions

[cerulean ore]

If n>2 then,
gcd((k)*(k+1)/2, n*(n+1)/2) - k*(k+1)/2)>1 where k<=n.
I am trying to prove it.
(n*(n+1) - k*(k+1))/2)
can be written as (n-k)(n+k+1)/2
How do I prove that they have gcd>1?

[stray reef]

uh

$\gcd\paren{\frac12 k(k+1), \frac12n(n+1) - \frac12 k(k+1)} > 1$

[vital dew]

Ann:

[stray reef]

is this your thing

[cerulean ore]

Yes!

[stray reef]

i am pretty sure gcd(a, b-a) = gcd(a,b)

[cerulean ore]

$\gcd\left({\frac12 k(k+1), \frac12n(n+1)\right) > 1$

[stray reef]

\paren is a custom command i put in my latex preamble. you will need to use \left( \right)

anyway w/e

[cerulean ore]

Oh, actually I have never used latex before, but it feels very neat to use.

[stray reef]

so you have 2 ≤ k < n i guess

[cerulean ore]

lmao, I am sorry.

[vital dew]

Kaori4Kousei:
Compile Error! Click the reaction for details. (You may edit your message)

[stray reef]

we can assume 1 < k < n since k=n makes it trivial and k=1 makes it falsae

uh

yeah no if you are trying to prove this for ALL possible pairs (k,n) then i'll have to disappoint you as there is a simple counterexample

[cerulean ore]

You mean it is not possible for every 1<k<n, like there are specific values of k when it works?

[stray reef]

can i see your problem exactly as it was stated to you?

[cerulean ore]

Like for n = 7: (4, 24) has gcd 4, but it is not possible to make 4 from some first natural numbers, right?

[stray reef]

??

can i see your problem exactly as it was stated to you?

[cerulean ore]

https://codeforces.com/contest/1038/problem/B

[stray reef]

your restatement has precious little to do with this problem

[cerulean ore]

People came up with different solutions, I came up with a solution when gcd(sum of first k natural numbers, sum of first n numbers - sum of first k numbers)>1 then, I have my answer. It worked and got accepted.

So, I am trying to understand why this is true.

[stray reef]

huh?

ok so what you're saying is you want to prove (∀n ≥ 2)(∃k ≤ n)[gcd(k(k+1)/2, n(n+1)/2 - k(k+1)/2) > 1]?

[cerulean ore]

Yep!

[stray reef]

okay

that's clearer at least

[cerulean ore]

For n = 10000007
k = 2
Their GCD is greater than 1.

[stray reef]

well i suppose if k is an odd prime then k divides k(k+1)/2
so if n has an odd prime factor you can just use that as your k

[cerulean ore]

Yes.
One solution was gcd(n, n*(n-1)/2) > 1. I proved it by considering n as odd first then, even.

But couldn't prove my statement.

[stray reef]

i mean yea sure that works too

it's not a hard statement to prove

[cerulean ore]

Yes, but mine is hard to prove.

[pallid lintel]

do you people agree with my proof?

its kinda like 7 bridges of konisberg heh

odd number of bridges over a river

[pallid lintel]

ah i wrote this proof for people in my class so they would all know what the terminology is, if any anything is unclear lemme know

we actually proved it after the assignment using chromatic flow polynomials and the proof was 2 lines long

[jovial grove]

How do I do question b

Please

[near prawn]

what have you tried

[jovial grove]

I get what to do conceptually

Add the cases where priya is in and the cases where Ana is in

Then subtract the cases in which both are in

I just don’t know how to like set it up

Like I feel like I’m not accounting for some things

Or I’m overcompensating

[near prawn]

no thats the right approach

[jovial grove]

I mean like when computing

Like I’m not sure I’m doing it right

I just need clarification on what it looks like

[vapid light]

What I did was that I split the set of girls into two sets, one that has Roberta and Priya and other set has the rest of the girls. Then I just chose 1 from the first set, 2 from the rest of the girls, and 3 from the set of boys

Not sure if I'm entirely correct

So don't take my word for it ig

[jovial grove]

Can someone show the solution in latex

[vapid light]

I got ${2 \choose 1}{15 \choose 2}{14 \choose 3}$

[vital dew]

Gupple:

[jovial grove]

Does that account for the fact that both priya and Roberta not being in the same committee

[vapid light]

Yeah

[jovial grove]

Okay

[vapid light]

It's because you can only pick 1 from roberta and priya, which is 2 choose 1

And then you remove the two girls from the set of girls

So 17 - 2 choose 2

[jovial grove]

Ok cool

Thanks

[vapid light]

Yep

[compact shell]

How many of the arrangements have exactly two consecutive consonants (non-vowels)?
UNUSUAL
Could someone help me on this question?
The answer mentions 5P2 * 3P2 * 4!/3!

[honest barn]

So you’re looking at permitting the letters right?

Oh shit, ughhhh this is gonna be annoying

Let’s figure out how to get this to work lol

So let’s justify each bit of the answer @compact shell

[compact shell]

Okay

[honest barn]

So we need like

A block of two consonants

And then the last one to be separate from it

As in, not adjacent

[compact shell]

Okay

got that

so

We have 3 options and we choose 2

3C2

[honest barn]

Yes

[compact shell]

then we can arrange those two among themselves

3C2 * 2!

[honest barn]

For the choice of consonant you grouop up

Let’s maybe hold off on the 2!

[compact shell]

Ok

[honest barn]

Because I want to use 5C2 to describe where we fit the block in

I think

[compact shell]

ok

[honest barn]

Let me think for a second, I thought I had a proof for that bit, but it fell through

[compact shell]

oh okay

[honest barn]

So I can say for certain

The division by 3!

Has to do with the fact you have 3 U’s

So in your final answer you would overcount

Because we treat the U’s as being separate, but any permutation of the U’s counts as the same word

[compact shell]

correct

[honest barn]

Gaaaa, this is really annoying. I don’t think I can salvage my ice

Idea

I have an idea that’s very close to working, but fitting in 5C2 is so hard

[compact shell]

Oh, alright.

Thanks tho!

[honest barn]

I’m still thinking about it tho

So basically I feel like you want to slot in the 2-letter consonant cluster

The issue is there’s 6 places it can go

And 2 of them leave the remaining consonant with 4 places to go

And the other 4 give it 3 places

So I almost have it, I just overcounted by a factor of 2

So I need to figure out where the symmetry is lol

[compact shell]

🙂

[honest barn]

Weird, my final answer ends up being 4 larger than their answer

;w;

Okay, I’ll outline my methodology, maybe it will help you figure out how to actually get this to work

Begin by placing the 2 consonant block in one of the 6 positions, it’s 6 since there’s 6 places the first letter can be

The two ones on the edge give 4 remaining places for the final consonant

While the other 4 give only 3

So in total there are 20 ways to put in our 2-consonant block, and the other one

From there there are 3C2 ways to pick which two to put in the block

And then there are two ways to actually put them in, because you can flip the two

E.g. SN vs NS

From there there are 4! ways to arrange the remaining vowels

But you overcount by 3! Because of the U’s

So in total I get 203C22*4!/3!

So 480

Their answer is 120

That’s all I got ¯_(ツ)_/¯

[compact shell]

Makes sense, the correct answer is 480 btw.

🙂

@honest barn

Thank you.

[honest barn]

Oh really?

Damn awesome

[compact shell]

Yea

[rancid ibex]

Not sure if this is right place to ask, but

Can somebody explain to me, a noob, what is the difference between Stirling number of the second degree and Bell's number with some basic example? It seems like Bell number is just a sum of Stirling numbers but i can't understand it very well.

[compact shell]

Are there any specific conditions when we could add a "premise" in rules of inference?

I have done some questions which randomly seem to add their own premise

[lyric pumice]

@rancid ibex Basically, Stirling numbers of the second kind count the number of ways to put some number of distinct objects into some number of groups and the Bell numbers count the number of ways to put some number of distinct objects into any number of groups.

[rancid ibex]

Thanks.

[compact shell]

Find the number of all arrangements of 3 ones and 5 zeros such that no two ones are adjacent to each other.
Isnt it gonna be 6C3 * 5?

[smoky harbor]

Hi all, good morning. I am doing a Discrete Math subject next year, I have not done any type of Maths recently but I am looking to study hard to prepare myself for Discrete Math, do you guys have any recommendations of what I should study to prepare myself? Thanks

[rain stone]

@smoky harbor check if there are any pre-requisites for the class you're taking. If there's a pre-requisite class, do a review of the material and some problems. If there are no pre-requisites, I would suggest reviewing basic logic and proofs. There are recommendations for good books in #books-old and #book-recommendations

in terms of raw knowledge, you don't need much for discrete math; logical skills and proofs are much more important, at least from what I've normally seen

some linear algebra might be needed depending on the class, but not very much, and the syllabus/pre-requisites should tell you that

[smoky harbor]

Thanks @rain stone There are no pre-reqs, I'll look into proofs, algebra and logic, cheers

[errant bear]

honestly i wouldnt be worried at all

like, your class should walk you through all of the steps/tools/techniques you need

[hardy remnant]

so i have the answer to this question but i cant seem to solve it on my own

these are my steps so far:

i turned (p->r) into -p OR r

and q -> r into -q OR r

[stray reef]

and them together

[hardy remnant]

(-p OR q) AND (r OR r)

[stray reef]

er

hold on

i think some letters got mixed up somewhere

[hardy remnant]

so (r OR r) is true so that just become a single r

with the idempotent rule

now i have (-p OR q) AND r

[stray reef]

can you check your work again

[hardy remnant]

ok

(p -> r) AND (q -> r)

(-p OR r) AND (-q OR r)

(-p OR -q) AND (r OR r)

(-p OR -q) AND r

thats my work so far

[stray reef]

uh. what's that step from line 2 to line 3

[hardy remnant]

i switched the r and -q

[stray reef]

looks hella fishy to me

can you even do that

[hardy remnant]

im just making educated guesses by looking at the formula sheet

i thought i saw people switch variables around

ok since theres a single r, maybe i should use a distributive rule

wait then that would become step 2 again

idk what im doing, im reading the chapter and its not helping

[sleek swallow]

Nice question:

$$[(p \implies r) \land (q \implies r)] \iff [(\lnot{p} \lor r) \land (\lnot{q} \lor r)]$$

$$\iff [(\lnot{p} \land \lnot{q}) \lor r]$$

$$\iff [\lnot{(p \lor q)} \lor r]$$

$$\iff [(p \lor q) \implies r]$$

[vital dew]

Abhijeet Vats:

[sleek swallow]

It's just an application of distributivity followed by the fact that the following two propositions are logically equivalent:

$$(p \implies q) \iff (\lnot{p} \lor q)$$

[vital dew]

Abhijeet Vats:

[sleek swallow]

@hardy remnant Understand?

[hardy remnant]

oh

i see

[sleek swallow]

There's no reason to use idempotence or anything like that here. Try doing these things in a basic way before moving forward to anything more obscure.

Also, another way to prove the equivalence would be to assume that there existed an assignment of truth values for each atomic proposition such that the equivalence was false. Then, show that there must be a contradiction.

But that, of course, is a more wordy way to do it and is entirely unnecessary given that there are perfectly good laws you can use, as I have shown above.

[hardy remnant]

alright, thank you

[sleek swallow]

you're welcome

[hardy remnant]

@stray reef so i can switch the r around

abhijeet, that makes sense now

i forgot to take the - out of (-p OR -q)

[sleek swallow]

You cannot technically switch the r around. What I did wasn't to switch the r around. You may pull it out because distributivity does hold.

[hardy remnant]

ahh

[twilit matrix]

Anyone have a good online resource for Discrete Maths?

Something like Khan Academy but with Uni maths lol

[honest barn]

libgen?

[robust mango]

https://www.eecs70.org/

@twilit matrix

[twilit matrix]

Thanks but I was thinking more like a series of videos or lectures explaining single concepts. Like a 10 minute video on just Sets.

[robust mango]

ik, this was all i had so i thought id share

[vapid light]

cs 70 is pretty dope

psets are ass cancer though

wow theyre teaching markov chains in the summer

wack

[weary tiger]

https://www.youtube.com/playlist?list=PL3o9D4Dl2FJ9q0_gtFXPh_H4POI5dK0yG I haven’t watched these but I’ve enjoyed all the mit lecture series I’ve watched so I might be willing to recommend them

[errant bear]

https://www.youtube.com/playlist?list=PLDDGPdw7e6Ag1EIznZ-m-qXu4XX3A0cIz this seems ok

[pallid lintel]

are there any ppl here that know a lot of ramsey theory that i can add to friends?

[serene basalt]

is that a joke?

😂

[weary tiger]

could someone explain alias vs alibi?

are these terms familiar to anyone?

[stray reef]

how's this a discrete math question

[weary tiger]

lemme send you the pdf

[last timber]

https://mathworld.wolfram.com/AlibiTransformation.html

@stray reef

https://mathworld.wolfram.com/AliasTransformation.html

[weary tiger]

yeah it's on pg 7 (all can see)

[thorny willow]

How does one prove that a graph is not n-colorable?

proving a graph is n-colorable is straight forward -- just colour it

but idk how to show when it isn't possible

[tulip ravine]

It can be quite messy. One common technique is to identify subgraphs of known chromatic number, but not all graphs are amenable to taht

[stray reef]

^

can you show the graph in question

[heavy crescent]

Guys, I don't understand Example 22. Why can't you remove one of the white squares so it becomes - 21 blue, 21 black, 21 white - instead of removing one of the blue squares (resulting in 20 blue, 21 black, 22 white)?

[fluid verge]

screenshot pls

[heavy crescent]

@fluid verge

[weary tiger]

There are actually 21 blue squares

[heavy crescent]

"...we may assume that we have rotated the coloring so that the missing square is colored blue"

one of the blue squares gets removed

my question is: why can't you rotate the board so one of the white ones get removed?

[fluid verge]

the goal is to reach a contradiction, removing a white square won't do that @heavy crescent

[forest zenith]

does anyone know a good way to upper bound the sum
$\sum_{k=1}^n \sqrt{k(k+1)}$

[vital dew]

jn:

[forest zenith]

so far I just have
$\frac{n^2 + 3n}{2}$

[vital dew]

jn:

[forest zenith]

but there has to be something tighter than that

[honest barn]

I feel like that’s a pretty tight one

The sum is slightly above the sum of k from 1 to n

And that is just (n(n+1))/2 = (n^2 + n)/2

@forest zenith

[forest zenith]

yeah maybe i should just be happy with that then

[honest barn]

Maybe you can squeeze out a tiiiiiiny bit better of a bound

But it’ll definitely still be on the order of n^2

So I don’t see a time it would make a difference

[forest zenith]

yeah i'm just gonna take a big O eventually anyway so it's probably fine lol

[honest barn]

👍

[forest zenith]

thanks!

[heavy crescent]

@fluid verge Oh, I see what you mean - you can interpret the board as 20:blue, 21: black, 22:white so it contradicts the premise.

[fluid verge]

yes

[heavy crescent]

👍

[weary tiger]

so for number 4, would it be (481)(26)?

[naive saffron]

There's also 5, 7 and 9

[weary tiger]

because i'm starting at 1 -> 4
then i look at 4 in the x row which corresponds to 8
then i go to 8 in the x row and that corresponds to 1 so i don't write 1 again and i close the parenthes

is that the right approach?

[naive saffron]

Yes

[weary tiger]

and then i went to the next biggest number at 2 and that corresponds to 6 but then 6 corresponds to 2 but then i can't have repeats

yeah there are other problems bc i have questions on them too

[naive saffron]

Yes that's basically how you do it

But also you're missing 5 7 and 9

Look at 5 7 and 9

[weary tiger]

what about them?

[naive saffron]

They are not fixed by the permutation

So there is also a (5 7 9) in the cycle notation of a

[weary tiger]

?

wait but like

[naive saffron]

Ok so if a number doesn't appear in the cycle notation at all, that means the permutation does nothing to it

[weary tiger]

i stopped bc then there were repeats...

[naive saffron]

?

[weary tiger]

sighs ok hold up

so

(481)(26) is correct so far right?

[naive saffron]

So far, but it's not complete yet

[weary tiger]

ok so now i move on to 3

[naive saffron]

yes

[weary tiger]

and 3 -> 3 but i don't write that down

[naive saffron]

yes

[weary tiger]

so i go to 4 correct?

[naive saffron]

yes

[weary tiger]

4->8->1

[naive saffron]

but 4 already appeared in a cycle

[weary tiger]

and then 1 goes to 4

[naive saffron]

so you don't need to worry about it

[weary tiger]

oh shat

[naive saffron]

now go to 5

[weary tiger]

5->7->9

wait i have a question

since it's 5->7->7->9 would that just become 5->9?

[naive saffron]

Does 7 get mapped to 7?

[weary tiger]

no

right/?

[naive saffron]

It doesn't

So it's 5 -> 7 -> 9

Not 5 -> 7 -> 7 -> 9

[weary tiger]

ok so then 9->5

[naive saffron]

Yes

[weary tiger]

so would it be (579)

[naive saffron]

Yes

[weary tiger]

so is a = (481)(26)(579)?

[naive saffron]

And then you move on to 6, 7, 8,9 but all those numbers have appeared already

So you're done

Yes

[weary tiger]

ahhh

so permutations can't have repeating numbers?

[naive saffron]

Permutation is a bijective function

In particular, it's injective: no two input will have the same output

And when expressing it in cycle notation, this is just the way to do it

Do you know what these cycles mean?

[weary tiger]

so these cycles are just a way to represent permutations right?

idk if i answered the question

[naive saffron]

Each cycle is in itself a permutation

[weary tiger]

i see

[naive saffron]

We can then write the permutation as a product of cycles

And the product here is the product of two permutations: function composition

[weary tiger]

so when it's a product of two permutations, it's function composition?

or not always

[naive saffron]

Writing a permutation like this allow us to easily know what the permutation does

It is always

[weary tiger]

i see

yes there has something to do with rotating the vertices in a shape

[naive saffron]

Well unless otherwise specified in your text

[weary tiger]

i see i see

ok can i ask about the pure cycle method and the function method in 5

lemme resend

[naive saffron]

"as described in the notes"

Sadly as much as I hope I do, I do not have access to your notes

[weary tiger]

ok so the reason why im scared is because i haven't seen example when there is another permutation multiplied together by another in a

oh

wait where do you see "described in notes"

AH

hold on

ok you should have it now

[naive saffron]

Ok if you really understand what permutations are and what cycles are then the "pure cycle" approach should make sense

Ok we can go through it i guess

[weary tiger]

lol im kinda clueless

actually remove the kinda

i basically wanna make sure i have it right becauase it's two permutations multiplied for a so that's kind of confusing

lemme try to work it out real quick and then send my work

because going from right to left will get weird

[naive saffron]

You can think of a permutation as a way to reorder things

For example the permutation a in problem 4

That permutation takes the 1st object and place it at position 4, take the 2nd object and place it at position 6, take the 3rd object and place it at position 3, etc

[weary tiger]

uhh

well that's for the function method

[last timber]

@weary tiger циклический и "функциональный" методы - два способа визуализации одной и той же пермутации

[weary tiger]

@last timber абсолютно спасибо большое)))

[weary tiger]

I'm so lost with B)

What does that even mean?

[honest barn]

What numbers are equivalent to 3 mod 7

Is an alternative way to state it

[weary tiger]

This whole section is killing me

hmm

[honest barn]

The equivalence classes of Z_7 were formed by modding out by the equivalence relation a ~ b iff a = b mod 7

the equivalence class as a set simply holds all things that are equivalent to any thing inside of it

so the equivalence class of 3 is all things equivalent to 3

[weary tiger]

I must be a whole unit behind, thats why Im struggling so much. For something to be equivalent

what does that mean exactly?

I was given this definition, and I can use it

but, no completely sure what this would mean in the deeper sense

[honest barn]

I mean, that's the definiton

if you know what a reflexive, symmetric, and transitive relation is separately

[weary tiger]

yeah

[honest barn]

then an equivalence relation is just one that is all 3 of those at the same time

This lets you form equivalence classes

[last timber]

example of equivalence

3/2 equivalent to 6/4

[weary tiger]

Ohhh

ok, so uhh

This is so much, idk how you guys can do this

Ugh, this is dumb question then, but why wouldn't there be infinite equiv classes of Z_7?

[honest barn]

because each thing is either equivalent to 0,1,2,3,4,5, or 6

but each equivalence class has infinitely many elements

the equivalence class of 0 has 0, 7, -7, 14, -14, 21,...

[weary tiger]

ok, that makes sense

would it be fair to say, that in a = b mod n, our a = the value for our equivalence class, and b belongs to a value in that said set?

[honest barn]

they're both "representatives" of the same equivalence class since they belong to the same equivalence class

[obtuse minnow]

Equivalence classes are just sets of elements of an overarching set that contain all elements of the overarching set and don't have elements in common. (in math speak we take a set and put ALL of its elements into disjoint subsets and each of these subsets are an equivalence class). An everyday example is the letter grade system: All possible grades must conform to exactly one equivalence class of A, B, C, D, F. No grade belongs to more than one and all grades must belong to at least one. In a lot of cases, each subset will have the same number of elements, but it's not required. Hope that helps.

[elder summit]

I don't fully understand the first part of the question - a transposition is a cycle of length two, so how can it consist of n - 1 cycles?

Could someone give an example please

[gleaming zephyr]

a cycle is something that looks like (a_1a_2... a_n)

thats an n cycle

a transposition is a two cycle

t_1 here would prob mean there are n-1 transpositons

(12)(23)(34)..... n-1

@elder summit

[elder summit]

Oh, I thought they meant t_1 would be an individual transposition ie (12) which is why I was wondering how (12) could consist of n - 1 cycles

[hardy remnant]

for a question a, the ! means its a unique quantifier

so doesnt E!x already mean Ex

idk how to do the reverse E

there exists an x that is unique, but that also applies to the second ExP(x)

[sleek swallow]

$\exists! x \in S: P(x)$

means that there exists precisely one $x$ in the set $S$ such that $P(x)$ holds.

[vital dew]

Abhijeet Vats:

[sleek swallow]

So, if you assert the existence of precisely one, you've also asserted existence in general

On the other hand, saying that:

$$\exists x \in S: P(x)$$

does not mean, necessarily, that there is precisely one such x.

[vital dew]

Abhijeet Vats:

[hardy remnant]

ahhh

i see

[elfin lagoon]

this may or may not be the right channel but, what does the resulting set look like?

the star us for kleene closure

is the stuff in paren saying a OR b ?

[obtuse lance]

yeah, probably

I think the notation is not 100% standardized, for instance I think even using () instead of [] can have a different meaning, I'd have to really look in the book you're using to know how it's defined

[hardy remnant]

for f, how does a person figure out what the third variable stands for when it is not given, such as z

i just put that z is a server but that is a guess

[sleek swallow]

W(x,z) just means that student x has visited website z

[hardy remnant]

oh

ok so there can be multiple of the same website or people

ahh, because the second argument in W(x, y) is for websites

[sleek swallow]

So, for f), it is:

There exists a student x and there exists a student y such that for all possible websites z, both students are not the same and student x has visited website z iff student y has visited website z.

[hardy remnant]

i gotcha

thanks bud

[sleek swallow]

you're welcome

[hardy remnant]

does it make a difference if i use if or iff

[sleek swallow]

yes it does

the double arrow refers to a biconditional

if you just use an if, then you're only looking at an implication in one direction

[pallid lintel]

im practicing counting problems atm...i got 14C5* 14C5 *13C4 *11C2 *12C3 *10C1 for this, anyone get the same? i treated it as taking non replaced balls out of a bag. (and taking taking A out of bag for first choice, ect, putting it back in for 2nd choice, ect

[near prawn]

works?

[pallid lintel]

examiner mispelt words heh

[near prawn]

this seems like a permutation problem rather than combinations

[pallid lintel]

ahhh, so it is. order matters

if i replace all the C's with P's

[weary tiger]

any discrete people available?

[errant bear]

dont worry i wont tell anyone 🤫🤐

[soft bobcat]

This upcoming semester, I'll be taking discrete math (This is the description: An introduction to the discrete structures that serve as a foundation for mathematics and computer science: set theory and mathematical logic; binary relations; counting and algorithm analysis; induction and strings.). Will I use Calculus in this class?

[stray reef]

up until algorithm analysis, almost none if any

[sleek swallow]

induction problems might involve calculus

[stray reef]

in algorithm analysis, you will need a little bit

[weary tiger]

Calculus falls under continuous math aka non discrete math

[faint narwhal]

Eh

calculus is used in solving general recurrence relations

[pallid lintel]

you will have to use partial fractions in recurrence relations as well but the lecturer will explain what that is. (its usually learnt first in a calc class though)

there are a couple derivatives used for generating functions, nothing difficult

this was taught in my 2nd discrete math class though, not my first one

[pallid lintel]

can anyone explain what this definition means? the context is a proof of ramsey theorem on p-uniform hypergraphs. I don't understand what 'same beginning' means

[analog sonnet]

I'm guessing that two p-sets (of natural numbers?) have the same color iff their minimal element is the same

[sinful meteor]

I'm gonna ask here because i've struggled to find a proper youtube video explaining this. How can you tell if a relation is a function using the domain and target? I keep finding stuff on using domain and range, but not target, and i'm trying to finish up a programming assignment on this

The definition I understand, every element of A is mapped to exactly one element of B. But my specific problem doesn't have a formula to follow, only a couple of sets so i'm a bit tripped up on where I need to get started

More specifically,

B = [4, 5] #target
f = [ [1, 4], [2, 5], [3, 4] ] #relation```

[faint narwhal]

[1,4] exactly means that 1 is mapped to 4

[sinful meteor]

But [3,4] means that 3 is also mapped to 4

Therefore it cant be a function

Correct?

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

[obtuse lance]

f(x)=x^2 is a function that maps 2 and -2 both to 4

[sinful meteor]

Ahh. So the above is a function. As long as every element of A is mapped to one and only one element of B ?

Even if some A share the same B

[obtuse lance]

have you learned what injective and surjective mean

[sinful meteor]

onto/one-to-one ?

I understand this concept when an actual formula is involved, but not just when i'm handed a few sets

I keep getting tripped up without having an actual formula to follow

[obtuse lance]

whenever you have a relation that you suspect is a function, try to determine if it's injective or surjective

[floral silo]

Hi, I understand the Bellman-Karp algorithm and how it works but I'm reaaaally struggling to represent it in pseudocode using a cost matrix. Could someone help me out?

[weary tiger]

@sinful meteor if an x in the domain is mapping to more than one element y in the range then its not a function everything else is a function

[drifting atlas]

So I think I got this down, I just want to be sure.
b. The range is (-inf, inf). It is one to one as both the input and output are all real numbers, the inverse is $(x-4)/5$ and the range is once again all real numbers so (-inf, inf).

[vital dew]

Soulgiver831:

[drifting atlas]

I didn't do the division thing right but yeah

[drifting atlas]

<@&286206848099549185>

[weary tiger]

inverse looks right

im not sure about your explanation for why it's 1-1 though

@drifting atlas can you elaborate on why the function in part b is 1-1?

(i hope there's no problem with me using the @)

[drifting atlas]

Okay. So should I just do f(x)=f(y) with x and y in R?

[weary tiger]

yep. assume that f(x) = f(y) and show that x = y

that's what it means for f to be 1-1

[drifting atlas]

Okay cool.

[weary tiger]

that should be your argument for why f is 1-1

[drifting atlas]

I think I got it for d as well but I'm not sur ehow to prove x/(1-x)=y/(1-y) implies x=y/

[weary tiger]

what have you tried?

this one's just a matter of simplifying the equation until x = y pops out

[drifting atlas]

Well I tried to multiply both sides by (1-x) but that would mean that mean x=y*(1-x)/(1-y)

[weary tiger]

you can make that a bit simpler

for problems like these it's usually a good idea to try and get rid of all fractions

[drifting atlas]

Oh wait dang I forgot about cross multiplying.

[weary tiger]

can you finish it from there?

[drifting atlas]

I got it

[weary tiger]

nice

[drifting atlas]

Thanks ^^

[weary tiger]

no problem

[drifting atlas]

@weary tiger Sorry to @, I just think I made a mistake and I wanna be sure. For d is the domain of the inverse (y=x-xy) also between 0 and 1?

[weary tiger]

i dont mind being @'d

lemme see

[drifting atlas]

And thank you ><

Wait never mind. The inverse is x/(x+1)

[weary tiger]

yeah

the domain of the inverse is the image of the original function

[drifting atlas]

Sorry I'm confused ><

[weary tiger]

which part?

[drifting atlas]

Like, what is the image of the original function?

[weary tiger]

have you found it already?

you should probably do that before you find the inverse

just so you know where the inverse is defined

[drifting atlas]

I don't think so. I got the range, I proved it's one to one, and I got the inverse function

[weary tiger]

range and image are the same thing

[drifting atlas]

Oh.

In that case it's just (0,1) right?

[weary tiger]

im not sure about that

[drifting atlas]

Oh so it's seperate from the domain?

Like the one given

[weary tiger]

in this case, yes

the image of f is not going to be the same as the domain

staring at a desmos plot tells me that the image should be {x in R : x > 0}

and thats the set which will be the domain of the inverse

now, of course, you have to actually prove that the image of f is the set i just described

[drifting atlas]

But how would we get, say, 100? The highest x can be is .9999_ right?

[weary tiger]

the image is the set of values that the function takes

try solving f(x) = 100, say

oh oops i might have misinterpreted

can you elaborate?

[drifting atlas]

The domain is what you can plug into the function. Like if you have a function f(x)=x+5 and your domain is (1,2,3) your range would be (6,7,8).

[weary tiger]

correct

[drifting atlas]

At least that's how our professor described it.

So the range here is 0<x<1

or sorry domain

[weary tiger]

mmhm

[drifting atlas]

So I figured you just plug in 0 and 1 for x which gives you 1 for x=0 and N/A for x=1

[weary tiger]

the problem here is that the domain contains a LOT of numbers, so you won't be able to find the range by just checking certain numbers in the domain

you have to verify, set-theoretically, that im(f) = {x in R : x > 0}

[drifting atlas]

How?

[weary tiger]

the same way you show any two sets are equal

for one direction, show that if y is in the image of f, then y > 0; specifically, if 0 < x < 1, then f(x) > 0

and for the other, show that if y > 0, then y = f(x) for some x in the domain of f

there's probably a cleaner way to do this but i think it would help if you worked right from the definitions here

[drifting atlas]

And that gives me that the range is x in R: x>0 right?

[weary tiger]

yup

[drifting atlas]

Okay and the domain of the inverse is the same as the range of the original function right?

So it's the same thing

[weary tiger]

it is correct that the domain of the inverse will be the range of the original function, so long as the inverse actually exists (which is the case if the function is 1-1; you've already shown that)

[drifting atlas]

Sweet!

[weary tiger]

i made a correction to the thing above btw

[drifting atlas]

Okay. Thank you again ^^

[weary tiger]

yeah no problem

feel free to @ me if you need any more help with this problem

[faint jackal]

@cerulean idol am having issues with my algebra problems maybe help ?

[cerulean idol]

[faint jackal]

english not really good can french lessons maybe ?

[cerulean idol]

[cerulean ore]

$\lfloor\frac{n}{a}\rfloor+\lfloor\frac{n}{b}\rfloor-\lfloor\frac{n}{lcm(a,b)}\rfloor$

[vital dew]

Kaori4Kousei:

[cerulean ore]

How to generalize this for m numbers?

[faint narwhal]

generalize what? You just have an expression

[cerulean ore]

I mean if we want to find the count of the numbers between 1 to n that are not divisible by a and b then we do n - n/a - n/b + n/lcm(a,b)

[faint narwhal]

this is just inclusion-exclusion

[cerulean ore]

Yes, for past 3 hours I am trying to implement PIE.

But cannot come up with a solution for m numbers. (Getting confused all the time)

Eg. Suppose n = 100 and numbers are m = {2,3,5,7}. How to find the count of numbers that are not divisible by any of the numbers from the set m?

[faint narwhal]

you subtact 100 - 100/2 - 100/3 - 100/5 - 100/7

But this overcounts the numbers that are divisible by 23, 2 * 5, 2 * 7, 35, 3*7 and 5*7

[cerulean ore]

But when we add the overcounted numbers back to this : 100 - 100/2 - 100/3 - 100/5 - 100/7 are not we overcounting some numbers again?

[faint narwhal]

exactly

So which numbers do we have to count again

[cerulean ore]

Which are the multiple of pairwise LCM of these: 2*3, 2 * 5, 2 * 7, 3*5, 3*7 and 5*7?

[faint narwhal]

yes

[cerulean ore]

Will we count some numbers again?

[faint narwhal]

yes

[cerulean ore]

So, basically this is what I should try to write?

[faint narwhal]

yes

[cerulean ore]

Thank you! 😄

[weary tiger]

Suppose 5 different integers are randomly chosen from between 20 and 69, inclusive. What is the probability that they each have a different tens digit?

is the answer $\frac{10^5}{50 \cdot 49 \cdot 48 \cdot 47 \cdot 46}$

[vital dew]

polynomial:

[weary tiger]

@stray reef ?

[stray reef]

looks a bit suspicious to me, hold on

yeah the denom should be 50C5

[weary tiger]

why tho

[stray reef]

vimes please don't interrupt

vimes please don't interrupt this isn't even the issue here

anyway, you do not care about the order in which you draw your numbers

[weary tiger]

yes but look at them one at a time

say we wanted 1 number to fit this

10 ways to pick a tens number

50 ways to pick a number at all

do you agree

[stray reef]

50 * 49 * 48 * 47 * 46 would count the possible draws if you DID care about which integer came first, which came second etc

[glass karma]

what grade you in

[stray reef]

i.e. under that count, you would count [51, 23, 21, 20, 66] as a different outcome than [21, 66, 20, 23, 51]

and if you choose to do it that way, which you certainly can, then the number of favorable outcomes will no longer be 10^5

it'll be 5! * 10^5

[weary tiger]

i don't see how i am not accounting for the same thing with the 10^5 tho

[stray reef]

since to count the favorable outcomes you still want one number from each ten-range

but now it matters what ten-range comes in what position in your now ORDERED draw sequence

e.g. you could have the number in the twenties come first in your draw

or second

or third, or fourth, or fifth

[weary tiger]

ok but look at it one step at a time

choosing any first of the 10 numbers

we have

10 choices for any tens digit

right

do you agree

[stray reef]

yes, and we also have 5 choices for what the tens digit will be

[weary tiger]

oh ok

[stray reef]

ie whether the first number will be in the twenties, thirties, forties, fifties or sixties

[weary tiger]

i get it now

thanks

[stray reef]

there's another way to look at it

[weary tiger]

yes?

[stray reef]

you could say that the first number can be whatever you want

ie 50 options

but then after you pick it the number of options goes down not by 1 but by 10, since you're crossing off the entire ten-range the number was in

so the next number has 40 options

the next has 30, then 20 and then finally 10

[weary tiger]

ohhh

yeah

i like that way more

thanks

that makes a lot of sense 🙂

that also explains my overcounting

[weary tiger]

Ten people are sitting around a round table. Three of them are chosen at random to give a presentation. What is the probability that the three chosen people were sitting in consecutive seats?

@stray reef can you help me again please

i am thinking of (10 * 2 * 2)/(10 * 9 * 8)

[weary tiger]

Wouldn't it be 10!/((10-3)! * 3!)

= 10!/(7!*3!)

10 * 9 * 8/(3!)

this can't be it because that makes the probability way higher than 1.

Oh my bad i misread the question

I was thinking about ways to choose sorry

Wait wouldn't it be the # of ways to pick 3 consecutive people / # of ways to choose 3 people

yes

Total num of ways to pick 3 ppl is 10 choose 3 = 120

But now to find how to pick 3 consecutively

Since for the first person, there r 10 selections that can be made

We have 10 * ..

this is wrong for sure since your order is messed up

But i mean i have the general idea

well i had the general idea as well above..

Its been a while since ive done discrete sorry

Guess i dont remember it as much as i thought i did

Sorry about that

[strong urchin]

anyone good with fourrier series and fourier- + z-transformations? pls pm me :)

[stray reef]

the number of ways to pick 3 consecutive people from a round table is obviously just 10

@weary tiger @weary tiger

[weary tiger]

@stray reef why tho

[halcyon ledge]

🤔

draw a little picture

then pick people

[stray reef]

every picking of three consecutive people is uniquely determined by who's in the clockwise-most position

[sinful meteor]

If I were to try and say "There are no dinosaurs living at the zoo" in terms of a logical expression,

S(x) : x is a dinosaur
M(x) x lives at the zoo

Wouldn't it just be

∃x(¬S(x) \/ M(x))

? Or is it ∀x ? I'm confused on the difference. I know the wording difference but have no clue when to use each

I guess i'm confused because "There are no" kinda implies EVERY, but the wording is "There are" so I get tripped up.

[weary tiger]

you can think of a "there are no..." statement is as the negation of a "there exists" statement, which seems to be what you had in mind

you should therefore end up with something with a "for all" in front

your final answer should be the logical equivalent of "every animal living at the zoo is not a dinosaur" (which you don't need logic to figure out)

[sinful meteor]

∀x(¬S(x) \/ M(x)) seems to be what im after then

[weary tiger]

iirc "(not P) or Q" is "P implies Q", so what you've written is "for all x, if x is a dinosaur, then x lives at the zoo"

or "every dinosaur lives at the zoo", which would be pretty cool but is unfortunately not the case

[sinful meteor]

so then technically it would be the opposite of that? ¬S(x) /\ ¬M(x) for all x, x is not a dinosaur and x is not living at the zoo

meaning that any animal that is not a dinosaur could be living at the zoo

[weary tiger]

in my mind the final answer should be (up to logical equivalence) the statement
"for all x, M(x) implies (not S(x))"

which is, written out, "for all x, (not M(x)) or (not S(x))"

(typing on my phone so i can't use fancy logical symbols)

where did the "and" come from?

i suggest you start from the statement "there is a dinosaur living at the zoo" and try negating it. you should get the answer you want

[solemn dome]

this question has me so confused

does it not just give me the answer?

[rain stone]

it's asking you if that is correct or not

[weary tiger]

lmao

[sleek swallow]

@solemn dome

[solemn dome]

i saw the response. I said true, but I'm not sure why because i havent looked into how contrapositives work yet

[sleek swallow]

They're telling you that the implication is equivalent to its contrapositive

If a statement is equivalent to another statement, the equivalence is obviously true

[solemn dome]

okay

do i need to do a truth table to find out if something is a contradiction or a tautology?

im trying to figure out if this is a tautology or a contradiction

[sleek swallow]

Is the prime supposed to represent negation?

[solemn dome]

yeah

[sleek swallow]

Well, look at the truth value of $A \lor \lnot{A}$.

[vital dew]

Abhijeet Vats:

[sleek swallow]

Is it true or false?

[solemn dome]

A V A` would just mean "T or F" right?

im really new to discrete math

[sleek swallow]

Well, $A$ is a proposition so it is either true or it is false. But, $\lnot{A}$ would be false whenever $A$ is true and true whenever $A$ is false. So, what is the truth value of $A \lor \lnot{A}$?

[vital dew]

Abhijeet Vats:

[solemn dome]

T

[sleek swallow]

Good. So, now, your implication $(A \lor \lnot{A}) \implies \lnot{(A \lor \lnot{A})}$ is something of the form $T \implies F$. Is that true or false?

[vital dew]

Abhijeet Vats:

[sleek swallow]

@solemn dome

[solemn dome]

false

[sleek swallow]

Indeed and this happens regardless of what the truth value of A is, yes?

[solemn dome]

yes

[sleek swallow]

So, is this is an absurdity, tautology or a contingency?

[solemn dome]

so its a contradiction

[sleek swallow]

Yeap

[solemn dome]

okay thank you

[sleek swallow]

You're welcome

[solemn dome]

i did all of those problems wrong originally

[sleek swallow]

Well, that's very natural if you're not working with truth tables

[solemn dome]

i turned the A and B into sentences and tried to think of them in that way

because my previous homework did something like that

[sleek swallow]

Ah well

whenever you're not sure, just use truth tables

[solemn dome]

okay

[sleek swallow]

They're annoying to make but you gotta do that bread and butter stuff before you get to the cool stuff

[hasty glade]

How can I found that A = {0,1,2,3} and (A. *) is a group?

The only property that I do not know how to prove is associativity

[sour arrow]

Do you mean (A, +)? Haha

[hasty glade]

Oh yes hahahah

A, +

[sour arrow]

Unfortunately associativity isn't easy to prove with the Cayley table

[hasty glade]

D:

[sour arrow]

You've got to check all combinations. (Or, make an argument for why associativity should hold)

[hasty glade]

The full exercise is to prove that (A, +, *) with operations defined by a Cayley table is a ring

So I wanted to prove first associativity

But it is probably a tedius exercise

[sour arrow]

Oh, so you do mean (A, *)

You can probably assume the group axioms, as the point of the exercise is to get you learning the ring axioms

[hasty glade]

What I can see is that (A, +) = (Z4, +)

[sour arrow]

That's a really neat multiplication haha

[hasty glade]

So I m sure that it is a conmutative group

The thing is...

[sour arrow]

Good argument imo

[hasty glade]

How Can I prove distributive

[sour arrow]

Gotta check all combinations. Happily, most of them are 0

[hasty glade]

I hate that... hahaha

[granite hamlet]

not sure if this holds up rigorously but one thing u can notice about (A, •) is that odd * odd = 2

and like hopefully use that to make your owrk shorter

[sour arrow]

Oh yeah, maybe there's a way to reason it out

[granite hamlet]

this way you only need to check like 6 combinations of parities for a(b + c)

[brittle berry]

Why do we assume x is even here when working through this? That's my only question

[last sigil]

@brittle berry Look at (iii)

also, I don't understand (i), since 3x + 2 =5, and x is odd?

[brittle berry]

So that automatically forces you to assume x is even sinve x squared is even?

[last sigil]

yeah

You should try proving

that if x^2 is even, x is even

[brittle berry]

Ah yeah thats a good reminder xd

[last sigil]

Actually, I think I get (i) & (ii), but the way they phrased this question is very weird

[brittle berry]

So i just need to prove all 3 assuming x is 2k?

[last sigil]

What you need to do

is show

(i) implies (ii)

(ii) implies (iii)

and (iii) implies (i)

[brittle berry]

Mmmm ok thank you. Sounds fun

[last sigil]

If 3x + 2 is even, then x + 5 is odd (prove this to show (i) implies (ii))

[honest barn]

I think it's easier to just show all of these are equivalent to x is even tbh

Like that's a far more underlying thing going on here, if you know any of these then you know x is even

and all the statements follow from that

[hasty glade]

All order 4 groups are conmutative ?

Men.. All order 4 groups are conmutative..

And there are only 2 possible isomorfisms

Groups are pretty crazy

[hasty glade]

Guys

I m having a loot of trouble in finding elements of a ring

Or that giving a prove to show that in a ring (A, +, *) * is distributive with +

Any suggestions ?

[granite hamlet]

what’s the ring?

[weary tiger]

Idk an onion ring?

[delicate ridge]

the famous ring A

kinda a shame that R gets all the attention tho 😔

[weary tiger]

I agree. R sucks

[velvet junco]

I love being able to work through these on my own

Feels like solving a puzzle once you get it all done

[fluid verge]

me: mom, can i have an elegant proof
mom: no, we already have elegant proofs at home
elegant proofs at home: induction

[loud copper]

its always induction

[safe tinsel]

[hasty glade]

Guys how can I prove that two groups are distributive with each other ?

Do I have to test all cases ??

[sleek swallow]

What do you mean two groups being distributive with each other?

If $(G,\circ)$ is a group and $\square$ is another binary operation defined on $G$, then is $\square$ distributive over $\circ$? Is that what you're asking?

[vital dew]

Abhijeet Vats:

[sleek swallow]

If that's what you're asking, then you need to test whether that holds with any three elements $a,b,c \in G$. In other words, you need to show that:

$$a \square (b \circ c) = (a \square b) \circ (a \square c)$$

for any $a,b,c \in G$.

[vital dew]

Abhijeet Vats:

[sleek swallow]

@hasty glade

[hasty glade]

@sleek swallow do you know what a ring is ? I ask because I dont know If what I m talking about is known as that.

because I have the problem with rings

[stray reef]

can you show the exact question you're trying to answer

exactly as it is stated

[sleek swallow]

Yea, just send a clear picture

I mean, you can just search up what a ring is and check if what you're talking about matches up with the definition of a ring

[hasty glade]

Okay. Lets say yoy have a ring made of (A, +, *)

[loud copper]

ring is just spicy group

[hasty glade]

You know that (A, +) Is already a conmutative group

How do you prove that * is distributive with + ?

[stray reef]

wdym

don't you already have that (A, +, *) is a ring

[loud copper]

its one of the defining properties of a ring actually

[hasty glade]

You have to say if It is or not

I mean you have two tables

[stray reef]

now

[loud copper]

tricked

[stray reef]

what did i just say

about asking your question

[sleek swallow]

show us the exact question

[stray reef]

EXACTLY

[sleek swallow]

send a picture

[stray reef]

AS

IT

WAS

STATED

[hasty glade]

The thing is that it is full spanish lol

[stray reef]

just send it...

[hasty glade]

That is why I do not send pics

[sleek swallow]

My dude, just send it

[loud copper]

You have to say if It is or not

[stray reef]

we'll ask to translate what needs to be translated.

[loud copper]

and u just got pranked into answering the q

[stray reef]

so far you're just leaving us in the dark.

[hasty glade]

Find the values remaining for (A,+,*) being a ring

[stray reef]

A = {s, t, x, y} as i understand it?

[hasty glade]

Yes

[stray reef]

ok

well you can see from the addition table that s is your 0

[hasty glade]

And also you already know that (A, +) is a conmutative group

So you just have to work on the second table

well you can see from the addition table that s is your 0
@stray reef Yes

[stray reef]

you have that tt = t, xt = t, xy = y and yx = s

notice that from the distributive law and the addition table you get that xx = x(t+y) = xt + xy = t + y = x

and from the associative law you get that yy = y(xy) = (yx)y = sy = s

continue in a similar fashion to find the values of yt, tx and ty

[hasty glade]

It will take a lot of time lol

[stray reef]

it will not

it just took me under 10 minutes.

[hasty glade]

You completed the whole table ??

[stray reef]

it's only like five unknown entries

and yes i did complete the whole table

by means of, for lack of a better word, doing some arithmetic in this ring

[weary tiger]

..

Why not say in this bitch

[errant bear]

i feel like this is like the 5th day jack has asked this question

[hasty glade]

hahahaha

I already finished my exam

So now it is over

Thank you guys

[weary tiger]

Np stay blessed

[halcyon ledge]

yay

[hasty glade]

I got a 9/10

[halcyon ledge]

[jovial grove]

Question

If I’m choosing a group of 5 from 6 boys and 9 girls

How many combinations if the group must have 3 boys and 2 girls

[errant bear]

what have you tried

[jovial grove]

6c3*9c2?

[naive saffron]

Seems about right

[errant bear]

btw

i hate the notation for n choose k etc

like

it makes sense

[jovial grove]

Alright

[errant bear]

but nCk, i feel like it should be written the other way around

like the smaller number first

[jovial grove]

$$6 \choose 3$$

[vital dew]

Bivariate:

[jovial grove]

Like this?

[errant bear]

no its fine

[naive saffron]

I think nCk is fine

[errant bear]

im talking about how in general

its written lik nCk

[naive saffron]

Are you saying it should be kCn

[jovial grove]

Oh I c

[errant bear]

like i feel intuitively you should start out with your like, rule, or requirement

[jovial grove]

k chosen out of n

[errant bear]

and so like we are picking k out of n

[jovial grove]

I mean that sorta makes sense

[weary tiger]

if you read C as "choose" then what's unintuitive about it?

[errant bear]

not, given n, pick k

[weary tiger]

"choose k"

[jovial grove]

I guess everyone’s just used to the normal notation

[errant bear]

im not arguing about that botn, im saying the whole idea of n choose k im not a fan of

it makes more sense to me to pick k out of any n

by fixing n, it like doesnt flow like in every day setting

[weary tiger]

Fn,Ck

[errant bear]

idk how to describe it

hm yeah, i get that, but like, picking k out of n seems to flow better in language

idk how to describe it

like the structure of the statement is better imo the other way

but anyways, yeah you needing 3 boys is independent of needing 2 girls, so you just multiply their possibile outcomes

which is why its correct

[cerulean ore]

I am trying to find out why my algorithm works for this problem:
https://codeforces.com/contest/437/problem/B
The problem states that we have numbers from 1 to limit and we have to find the set of distinct numbers such that the sum of their lowbit(x) is equal to the given sum.

Low bit of x is : Lowbit(x) = 2^(position of least significant set bit (0 indexing))

set i-> 1
for i to limit:
  create pair {lowbit(i), i}
  append to the set T
Sort the set T in the order of non-increasing of first element of each pair. 
for pair in T:
  if(sum-pair->first >= 0)
    sum-=pair->first
if sum is 0
  answer exists
else
  answer doesn't exists

Basically if we have 2^0, 2^0, 2^0, 2^0, 2^1, 2^1, 2^2, 2^3,
and from these numbers if we want to make a number x then, it is always best to choose the biggest number such that x-(number)>=0.

[last timber]

yep i think u should always pick the highest possible power

In the first line print an integer n (1 ≤ n ≤ 105), denoting the size of S. Then print the elements of set S in any order. If there are multiple answers, print any of them.

oh wait it is size

like {1, 2, 6} will have size 3

[cerulean ore]

Yes

[last timber]

ah lol

nvm,

it is output

[cerulean ore]

lol

So, why picking the highest possible power works?

[last timber]

well, idea is that given sum is some sum of powers of two

let us say for example that the sum is
10101010100

taking highest possible power which will be 10000000000 i get new number

i.e 101010100

and 10000000 wil be put into set of answers

101010100 repeating this procedure

i will consecutively get
10000000

and etc

is it clear?

[cerulean ore]

How does it works for when the limit is 8 and the sum is 15?

[last timber]

so 15 in binary notation is
1111

[cerulean ore]

1 1 1 1
2^3 + 2^2 + 2^1 + 2^0
(8,4, 2, 1)

[last timber]

by taking highest power

i will get

1000

which is 8

then 100 which is 4

then 10

and 1

but also u should remember

that if limit was 7

then u will be forced to take 111 as first number

i mean taking not only the highest possible power

but highest number

[cerulean ore]

Yeah, that is what I was going to ask. Suppose if sum is 20 and the limit is 8.

16 8 4 2 1
1  0 1 0 0```
We cannot have 16, as the limit is 8.

[last timber]

20 = 8+7+5

yes, take highest number possible

in general it is greedy + recursion as i see

[cerulean ore]

Wait lowbit(8) + lowbit(7) + lowbit(5) = 10

Summation of lowbit of every number in the set should be equal to the given sum.

[obtuse minnow]

discrete mass is that like dark matter?

[weary tiger]

Would f(x)=-abs(x) be not one to one nor onto for domain:R->R+

It would not be one to one given counter x= 1, x=-1

And would not be onto because not all range in R+ is reached,

[stray reef]

f(x) = -|x| does not even define a function from R to R+ at all

[weary tiger]

Uh oh

[stray reef]

do you have the exact statement of the problem handy

[errant bear]

it does for positive enough negative values smh

[weary tiger]

The problem is to give an example of a function that would not be one to one or onto given the domain

R->R+

[stray reef]

ok, your thing does not work

there is a relatively simple to write down function which does

f(x) = x^2 + 1

[weary tiger]

I get how to make a function not one to one but not sure about onto

Im confused on onto

[stray reef]

you need to make it so that at least one value in the codomain is never returned by the function

[weary tiger]

OH I see with the fx you gave 0 is never reached

Tysm

[urban olive]

Hey guys I need help with this problem

''In how many ways can a commission be selected to design the syllabus for a discrete mathematics course at a computer school if the commission need be composed of three members from the computer department and four members from the mathematics department, knowing that the department of computer science has nine members and the one of mathematics eleven.''

Need help trying to figure out the total ways possible, the topic is permutations and combinations

Nvm I think I got it

Combination of (11, 4) + (9, 3)

[spare terrace]

I feel like those combinations should be multiplied

[near prawn]

yes you multiply them and not add

[pallid lintel]

yes its multiplied by the multiplication principle https://en.wikipedia.org/wiki/Rule_of_product

for any set of 4 of the mathematicians you can select 3 distinct comp sci people

[winged sun]

Hey guys, just started studying discrete maths and having some issues with propositional logic

Let's say we have P: The window is open and Q: The lights are on. Let's say both of these are true. Then P -> Q is also True. But how can we say that P implies Q when really these are two rather unrelated things

Like P could be true and Q could be false

In other words. How can we say "If the window is open, then the lights are on." - doesn't make any sense to me

[foggy hatch]

To non-Wey readers, I just responded to that in #proofs-and-logic

[sudden wedge]

Hey guys I was wondering if someone could point me in the right direction on this question, I'm not certain I understand what is being asked

\item List all functions $f$ from ${1,2,3}$ to ${1,2,3}$ that satisfy $(f\circ f)(x)=x$ for all $x\in{1,2,3}$. You may do this by either explicitly writing down all the pairs of each function OR by using arrow diagrams. Hint: There are 4 such functions!\

[vital dew]

Trapezoider:

[sudden wedge]

I'm guessing I am supposed to find the functions that map from the first set to the second? But they are the same set so.... Apologies for my confusion and lack of understanding

[naive saffron]

What's wrong with them being the same set?

[sudden wedge]

Nothing I suppose

I am just thick headed and am not sure how to approach this question

Maybe the first function could be one that adds zero to each element?

Another multiplies by 1?

Am I even thinking along the correct lines here?

[naive saffron]

If you think about it, they are the same function

But yes, the function you described satisfy the equation (f o f)(x)=x

[sudden wedge]

So basically its just asking me to find 4 functions that take in an element of a set and output the same element?

If thats the case I vastly overconfused myself for no reason 😆

[naive saffron]

No no no

[sudden wedge]

oh

Shoot

[naive saffron]

It's asking you to find a function f such that f(f(x))=x for all x

[sudden wedge]

Ahh and there are 4 such functions...

[naive saffron]

Yes

[sudden wedge]

Okay, I understand now. Ill have to do some googling to figure out what those 4 functions are. My pea sized brain is struggling to generate an answer. Thank you for your help @naive saffron 🙂

[naive saffron]

Um

I suggest you don't

You probably won't be able to find the answer online to a specific question like this

[sudden wedge]

Yeah I meant generic googling

"Set function composistion" etc

find some vids

[naive saffron]

What I suggest you to do is writing out all the functions from {1,2,3} to {1,2,3} and see which ones satisfy f(f(x))=x for all x

There are only 9 functions to test

You should think of a function as a machine that takes in something and outputs something

[maiden fractal]

Hey guys, I have a question, was wondering if anyone could help?

The problem is as follows: We have buckets numbered from 1 to N each with a tag.

A tag can consist of characters from an arbitrary alphabet, or * and %.

We can send tags to select buckets, a tag works similar (but differently) to a regex, where % matches any 1 character in the alphabet and * will match 0 or more of any character.

However, the caveat (making it different from a regex) is that * disregards any characters after it. Meaning that if we have buckets will tags "1234" and "1235", the tag "12*" will match both of them, but so will "*" followed by any combination of characters e.g. "*%skdkljlkadfj" will match both as well, since as soon as the there is a "*" in the tag, it will match ALL tags assuming the start of the tag has already been matched.

Essentially, as soon as there is a "*" the all tags will be matched from that point on.

The goal is to maximize B, the amount of buckets from 1..B that we can match. For an L, length of the tagging string. E.g. if L = 3 and B = 3 then the scheme allows match buckets 1, buckets 1 and 2, buckets 1, 2 and 3 with unique selection tags, given that our tags for the buckets are 3 characters in length.

Assuming we have an alphabet of just 0 and 1, I've created the following scheme which allows us to match L buckets. This means that B = L for the following scheme.