Recent questions in Advanced Math

Discrete mathAnswered question

sincsenekdq 2022-09-07

Predicates and Quantifiers in discrete math

Let P(x,y) be "x is waiting for y", where the universe of discourse is the set of all people in the world. Use quantifiers to express the following statement. (i)There is no one who is waiting for everybody. (ii) Everybody is waiting for somebody.

May i know how to solve this kind of question?

Let P(x,y) be "x is waiting for y", where the universe of discourse is the set of all people in the world. Use quantifiers to express the following statement. (i)There is no one who is waiting for everybody. (ii) Everybody is waiting for somebody.

May i know how to solve this kind of question?

Discrete mathAnswered question

nar6jetaime86 2022-09-07

Chessboard by dominoes in Discrete Math

In how many ways can you cover a $2\times n$ chessboard by dominoes?

In how many ways can you cover a $2\times n$ chessboard by dominoes?

Discrete mathAnswered question

Jonah Jacobson 2022-09-07

Discrete math Group - Isomorphism and Automorphism

Let G be a Cyclic group

Prove or disprove: A.let $a,b\in G\phantom{\rule{1em}{0ex}}$ so the function $f:G\to G,f({a}^{k})={b}^{k}$ is Automorphism of G(which means G is Isomorphism to herself)

B.let a,b generators of G so the function $f:G\to G,f({a}^{k})={b}^{k}$ is Automorphism of G(which means G is Isomorphism to herself)

Let G be a Cyclic group

Prove or disprove: A.let $a,b\in G\phantom{\rule{1em}{0ex}}$ so the function $f:G\to G,f({a}^{k})={b}^{k}$ is Automorphism of G(which means G is Isomorphism to herself)

B.let a,b generators of G so the function $f:G\to G,f({a}^{k})={b}^{k}$ is Automorphism of G(which means G is Isomorphism to herself)

Discrete mathAnswered question

katdoringlo 2022-09-07

Discrete math and recursion problem.

Let ${b}_{1}=3$

${b}_{n}=n(n+2)$

From that question I wanted to do the $n+1th$ step as well for the recursion process and i got this:

${b}_{n+1}={b}_{n}+3$

however, that is wrong and apparently it is missing a $+2n$ in it:

$${b}_{n+1}={b}_{n}+2n+3$$

Can someone please explain how the book got 2n?

Let ${b}_{1}=3$

${b}_{n}=n(n+2)$

From that question I wanted to do the $n+1th$ step as well for the recursion process and i got this:

${b}_{n+1}={b}_{n}+3$

however, that is wrong and apparently it is missing a $+2n$ in it:

$${b}_{n+1}={b}_{n}+2n+3$$

Can someone please explain how the book got 2n?

Discrete mathAnswered question

Koronicaqn 2022-09-07

Prove or disprove ${2}^{an}=O({2}^{n})$

I was wondering if someone could verify or correct my work.

For all $a\ge 1$ Prove or Disprove ${2}^{an}$ belongs to big-o of ${2}^{n}$

By definition, if there is a positive integer 'N' and a positive integer 'c' then $f(n)\ge g(n)$, for all $n>N$.

Therefore,

$$\begin{array}{rl}{2}^{an}& \le c\times {2}^{n}\\ \mathrm{log}({2}^{an})& \le c\times \mathrm{log}({2}^{n})\\ an\times \mathrm{log}(2)& \le cn\times \mathrm{log}(2)\\ an& \le cn\end{array}$$

let

$$c=1$$

$$n=1$$

Therefore,

$$a<=1$$

therefore our given statement cannot be true since there exists some ${}^{\prime}{a}^{\prime}>{=}^{\prime}{c}^{\prime}$

I was wondering if someone could verify or correct my work.

For all $a\ge 1$ Prove or Disprove ${2}^{an}$ belongs to big-o of ${2}^{n}$

By definition, if there is a positive integer 'N' and a positive integer 'c' then $f(n)\ge g(n)$, for all $n>N$.

Therefore,

$$\begin{array}{rl}{2}^{an}& \le c\times {2}^{n}\\ \mathrm{log}({2}^{an})& \le c\times \mathrm{log}({2}^{n})\\ an\times \mathrm{log}(2)& \le cn\times \mathrm{log}(2)\\ an& \le cn\end{array}$$

let

$$c=1$$

$$n=1$$

Therefore,

$$a<=1$$

therefore our given statement cannot be true since there exists some ${}^{\prime}{a}^{\prime}>{=}^{\prime}{c}^{\prime}$

Discrete mathAnswered question

Jonah Jacobson 2022-09-07

Discrete Math Help with a Proof

I need help to prove the following: Let a, b, and c be any integers. If a∣b, then a∣bc

I need help to prove the following: Let a, b, and c be any integers. If a∣b, then a∣bc

Upper Level MathAnswered question

iescabroussexg 2022-09-07

Is there an algorithm which for a formula P of PA outputs ${\mathrm{\Sigma}}_{m}^{0}/{\mathrm{\Pi}}_{m}^{0}$ such that the output is the level P belongs to in Arithmetical hierarchy? If that's not computable is there an algorithm which outputs an upper bound on the level?

Discrete mathAnswered question

ymochelows 2022-09-07

Is this coding exercise well thought?

I have to create a code C of 5 words with length $n=6$, with the alphabet ${\mathbb{F}}_{2}=\{0,1\}$ that corrects 1 mistake.

I am new to coding theory so I am having some troubles with this particular question...

If it corrects 1 mistakes, that means that $d>2\cdot 1$ (I believe this is a well-known result [I prove it at my courses]), where d is the minimal distance of the code C defined as $d=d(\mathcal{C})=min\{d(x,y)|x,y\in \mathcal{C},x\ne y\}$, and that distance in the definition is the Hamming distance defined as $d(x,y)=\mathrm{\#}\{i|1\le i\le n,{x}_{i}\ne {y}_{i}\}$, being $x=({x}_{1},{x}_{2},...,{x}_{n})$ and $y=({y}_{1},{y}_{2},...,{y}_{n})$ elements in ${\mathbb{F}}_{q}^{n}$ (where ${\mathbb{F}}_{q}$ is the alphabet of the code, and n denotes the length of the words).

So, in my particular case I want that the minimal distance of the code is greater than 2, i.e., I want that there are no two different words in the code that have Hamming distance equal or lesser than 2, i.e., no two words in the code that have more than 4 coordinates equal to each other (as If they have four equal to each other, there would be $6-4=2$ different to each other, so the Hamming distance would be 2, and if there are 5 equal to each other, the Hamming distance would be 1 which is not valid). So, I begin to construct the code, by taking the first word:

$$(1,1,1,1,1,1)\in {\mathbb{F}}_{2}^{6}$$

Then, I could take another one like:

$$(1,1,1,0,0,0)\in {\mathbb{F}}_{2}^{6}$$

which satisfies the previous conditions. So, taking this kind of words, and taking on account the conditions that must hold, I could keep going with this ''constructive algorithm'' until I have 5 words. For example:

$$(1,0,0,1,0,0)\in {\mathbb{F}}_{2}^{6}$$

$$(0,1,0,1,1,0)\in {\mathbb{F}}_{2}^{6}$$

$$(0,0,0,0,0,0)\in {\mathbb{F}}_{2}^{6}$$

And this would conclude the exercise (by taking all this 5 words listed above). I am not sure if this is a great argument and I would really appreciate if someone could give me some feedback on it...

I have to create a code C of 5 words with length $n=6$, with the alphabet ${\mathbb{F}}_{2}=\{0,1\}$ that corrects 1 mistake.

I am new to coding theory so I am having some troubles with this particular question...

If it corrects 1 mistakes, that means that $d>2\cdot 1$ (I believe this is a well-known result [I prove it at my courses]), where d is the minimal distance of the code C defined as $d=d(\mathcal{C})=min\{d(x,y)|x,y\in \mathcal{C},x\ne y\}$, and that distance in the definition is the Hamming distance defined as $d(x,y)=\mathrm{\#}\{i|1\le i\le n,{x}_{i}\ne {y}_{i}\}$, being $x=({x}_{1},{x}_{2},...,{x}_{n})$ and $y=({y}_{1},{y}_{2},...,{y}_{n})$ elements in ${\mathbb{F}}_{q}^{n}$ (where ${\mathbb{F}}_{q}$ is the alphabet of the code, and n denotes the length of the words).

So, in my particular case I want that the minimal distance of the code is greater than 2, i.e., I want that there are no two different words in the code that have Hamming distance equal or lesser than 2, i.e., no two words in the code that have more than 4 coordinates equal to each other (as If they have four equal to each other, there would be $6-4=2$ different to each other, so the Hamming distance would be 2, and if there are 5 equal to each other, the Hamming distance would be 1 which is not valid). So, I begin to construct the code, by taking the first word:

$$(1,1,1,1,1,1)\in {\mathbb{F}}_{2}^{6}$$

Then, I could take another one like:

$$(1,1,1,0,0,0)\in {\mathbb{F}}_{2}^{6}$$

which satisfies the previous conditions. So, taking this kind of words, and taking on account the conditions that must hold, I could keep going with this ''constructive algorithm'' until I have 5 words. For example:

$$(1,0,0,1,0,0)\in {\mathbb{F}}_{2}^{6}$$

$$(0,1,0,1,1,0)\in {\mathbb{F}}_{2}^{6}$$

$$(0,0,0,0,0,0)\in {\mathbb{F}}_{2}^{6}$$

And this would conclude the exercise (by taking all this 5 words listed above). I am not sure if this is a great argument and I would really appreciate if someone could give me some feedback on it...

Discrete mathAnswered question

curukksm 2022-09-07

Discrete math induction proof (divisibilty)

How to show that ${10}^{n}-(-1{)}^{n}$ is always divisible by 11 through proof of induction?

How to show that ${10}^{n}-(-1{)}^{n}$ is always divisible by 11 through proof of induction?

Discrete mathAnswered question

niouzesto 2022-09-07

I've googled already for an explanation and examples that show the difference between logical and tautological equivalences. I understand that a tautological equivalence is first a logical one, but not necessary vice versa. Besides that as far as I've seen they are the same. Are the truth tables the same? What could be a good example that shows the differences between both?

Examples of the questions I was given on this matter: 1)$(pVq)->r$ is the tautological equivalence of $(p->r)\wedge (q->r)2)\text{}p-(qVr)$ is the tautological equivalence of $\text{}q-(pVr)$ I have to demonstrate which one, if any of those two are true statements.

On this basis I have to understand the difference between tautological and logical equivalences, why one and not the other, both or none.

Examples of the questions I was given on this matter: 1)$(pVq)->r$ is the tautological equivalence of $(p->r)\wedge (q->r)2)\text{}p-(qVr)$ is the tautological equivalence of $\text{}q-(pVr)$ I have to demonstrate which one, if any of those two are true statements.

On this basis I have to understand the difference between tautological and logical equivalences, why one and not the other, both or none.

Upper Level MathAnswered question

Gauge Odom 2022-09-07

Prove that the height of a 2-3 tree is between ${\mathrm{log}}_{3}N$ and $\mathrm{lg}N$

Discrete mathAnswered question

Terry Briggs 2022-09-07

A 'non-numerical\analytic' proof that $(}\genfrac{}{}{0ex}{}{n}{k}{\textstyle )$ > $(}\genfrac{}{}{0ex}{}{n}{k-1}{\textstyle )$ for large $n\in \mathbb{N}$

The number of k-subsets of [n] is given by the formula $(}\genfrac{}{}{0ex}{}{n}{k}{\textstyle )$ or ${}^{n}{C}_{k}$. They famously occur in the expansion of $(1+x{)}^{n}$ and they are given by the formula

$$(}\genfrac{}{}{0ex}{}{n}{k}{\textstyle )}=\frac{n!}{(n-k)!k!$$

Using this formula, it is easy to prove the inequality that $(}\genfrac{}{}{0ex}{}{n}{k}{\textstyle )}>{\textstyle (}\genfrac{}{}{0ex}{}{n}{k-1}{\textstyle )$ for large enough $n\in \mathbb{N}$. What this inequality says is that the number of ways of choosing $k-1$-subsets is eventually smaller than the number of ways of choosing k-subsets of [n].

One more way of showing this is by observing that $(}\genfrac{}{}{0ex}{}{n}{k}{\textstyle )$ is a polynomial in n of degree k and then, we can see that it will outgrow $(}\genfrac{}{}{0ex}{}{n}{k-1}{\textstyle )$ which is a lower degree polynomial in n.

Is there a more natural way of seeing this inequality without the use of calculations with the use of something more combinatorial-like? Possibly by exhibiting an injection between the $k-1$-subsets and k-subsets? Or by another interpretation of the numbers where it is easier to get such an injection? Or something else altogether?

Remark: My supervisor mentioned almost immediately that there was a way to see this using Symmetric Chain Decomposition. But I do not have the luxury of spending that much time on this. I apologise. I would be thankful if you could provide a proof based on the same.

Tl;dr: What I am looking for is something more along the lines of bijections or a different interpretation of the binomial coefficients that makes the inequality easier to see. I hope the approach doesn't rely heavily on calculations and at the same time, explains why the the inequality reverses for small n.

The number of k-subsets of [n] is given by the formula $(}\genfrac{}{}{0ex}{}{n}{k}{\textstyle )$ or ${}^{n}{C}_{k}$. They famously occur in the expansion of $(1+x{)}^{n}$ and they are given by the formula

$$(}\genfrac{}{}{0ex}{}{n}{k}{\textstyle )}=\frac{n!}{(n-k)!k!$$

Using this formula, it is easy to prove the inequality that $(}\genfrac{}{}{0ex}{}{n}{k}{\textstyle )}>{\textstyle (}\genfrac{}{}{0ex}{}{n}{k-1}{\textstyle )$ for large enough $n\in \mathbb{N}$. What this inequality says is that the number of ways of choosing $k-1$-subsets is eventually smaller than the number of ways of choosing k-subsets of [n].

One more way of showing this is by observing that $(}\genfrac{}{}{0ex}{}{n}{k}{\textstyle )$ is a polynomial in n of degree k and then, we can see that it will outgrow $(}\genfrac{}{}{0ex}{}{n}{k-1}{\textstyle )$ which is a lower degree polynomial in n.

Is there a more natural way of seeing this inequality without the use of calculations with the use of something more combinatorial-like? Possibly by exhibiting an injection between the $k-1$-subsets and k-subsets? Or by another interpretation of the numbers where it is easier to get such an injection? Or something else altogether?

Remark: My supervisor mentioned almost immediately that there was a way to see this using Symmetric Chain Decomposition. But I do not have the luxury of spending that much time on this. I apologise. I would be thankful if you could provide a proof based on the same.

Tl;dr: What I am looking for is something more along the lines of bijections or a different interpretation of the binomial coefficients that makes the inequality easier to see. I hope the approach doesn't rely heavily on calculations and at the same time, explains why the the inequality reverses for small n.

Discrete mathAnswered question

Alfredeim 2022-09-07

The way to prove that $\sigma (a)={3}^{k}$ has no solution?

$\sigma (n)$ = sum of divisors of n is a divisors function.

How to prove there are no such a and $k\ge 2$ satisfy $\sigma (a)={3}^{k}$.

This proplem can be simplify to the case when a is a power of prime ($a={p}^{\alpha}$) because

if $a={p}_{0}^{{\alpha}_{0}}{p}_{1}^{{\alpha}_{1}}...{p}_{n}^{{\alpha}_{n}}$, then

$$\sigma (a)=\sigma ({p}_{0}^{{\alpha}_{0}})\sigma ({p}_{1}^{{\alpha}_{1}})...\sigma ({p}_{n}^{{\alpha}_{n}})=\prod _{i=0}^{n}\frac{{p}_{i}^{{\alpha}_{i}+1}-1}{{p}_{i}-1}$$

$\sigma (n)$ = sum of divisors of n is a divisors function.

How to prove there are no such a and $k\ge 2$ satisfy $\sigma (a)={3}^{k}$.

This proplem can be simplify to the case when a is a power of prime ($a={p}^{\alpha}$) because

if $a={p}_{0}^{{\alpha}_{0}}{p}_{1}^{{\alpha}_{1}}...{p}_{n}^{{\alpha}_{n}}$, then

$$\sigma (a)=\sigma ({p}_{0}^{{\alpha}_{0}})\sigma ({p}_{1}^{{\alpha}_{1}})...\sigma ({p}_{n}^{{\alpha}_{n}})=\prod _{i=0}^{n}\frac{{p}_{i}^{{\alpha}_{i}+1}-1}{{p}_{i}-1}$$

Upper Level MathAnswered question

cjortiz141t 2022-09-07

Solve a laser's upper level $\frac{dy}{dx}=\frac{1-y}{A}-\frac{y\times f(x)}{B}$ where y = y(x) and A, B are constants.

Discrete mathAnswered question

puntdald8 2022-09-07

Discrete Math Equivalence Relation

Let f be some function with domain S and range T. Define a relation R by xRy to mean $f(x)=f(y)$. Prove that R is an equivalence relation. If 4 is a member of S, what are the members of [4] (the set of all elements equivalent to 4 under under this equivalence relation)?

I'm not sure what exactly this question is asking...what does "relation R by xRy" mean?

Let f be some function with domain S and range T. Define a relation R by xRy to mean $f(x)=f(y)$. Prove that R is an equivalence relation. If 4 is a member of S, what are the members of [4] (the set of all elements equivalent to 4 under under this equivalence relation)?

I'm not sure what exactly this question is asking...what does "relation R by xRy" mean?

Discrete mathAnswered question

IJzerboor07 2022-09-07

"Let m, n, and r be non-negative integers. How many distinct "words" are there consisting of m occurrences of the letter A, n occurrences of the letter B, r occurrences of the letter C, such that no subword of the form CC appears, and no other letters are used?"

Discrete mathAnswered question

ridge041h 2022-09-07

Construct an injective function from N to P(N) in a way that f(n) is not finite for any $n\in \mathbb{N}$ and prove that it is injective.

Problem. Construct an injective function from N to P(N) in a way that f(n) is not finite for any $n\in \mathbb{N}$ and prove that it is injective.

This is what I have attempted so far and I just need someone to check if what I have done is correct, or maybe guide me on what I have done wrong. This is my first time taking a proofs course and I am trying my best to learn and attempt the questions.

So first I decided that $f(n)=\{n,\mathrm{\infty}\}$.

And then to prove injectivity I picked two elements, x and y such that

$$\{x,\mathrm{\infty}\}=\{y,\mathrm{\infty}\}\phantom{\rule{1em}{0ex}}\phantom{\rule{thickmathspace}{0ex}}\u27f9\phantom{\rule{thickmathspace}{0ex}}\phantom{\rule{1em}{0ex}}x=y$$

Hence, injectivity is proved.

Problem. Construct an injective function from N to P(N) in a way that f(n) is not finite for any $n\in \mathbb{N}$ and prove that it is injective.

This is what I have attempted so far and I just need someone to check if what I have done is correct, or maybe guide me on what I have done wrong. This is my first time taking a proofs course and I am trying my best to learn and attempt the questions.

So first I decided that $f(n)=\{n,\mathrm{\infty}\}$.

And then to prove injectivity I picked two elements, x and y such that

$$\{x,\mathrm{\infty}\}=\{y,\mathrm{\infty}\}\phantom{\rule{1em}{0ex}}\phantom{\rule{thickmathspace}{0ex}}\u27f9\phantom{\rule{thickmathspace}{0ex}}\phantom{\rule{1em}{0ex}}x=y$$

Hence, injectivity is proved.

Discrete mathAnswered question

batystowy2b 2022-09-07

Are these two statements equivalent?

Express the statement that no one has more than three grandmothers.

G(x, y) : x is the grandmother of y

$$\mathrm{\exists}y(({\mathrm{\exists}}_{a}{\mathrm{\exists}}_{b}{\mathrm{\exists}}_{c}{\mathrm{\exists}}_{d},(G(a,y)\wedge G(b,y)\wedge G(c,y)\wedge G(d,y)))\to (a=b\text{}\vee a=b\text{}\vee a=c\text{}\vee a=d\text{}\vee b=c\text{}\vee b=d\text{}\vee c=d))$$

This is my solution. What I am trying to say is that if there exists a person y (anyone) who has four grandmothers then at least two of those grandmothers must be the same.

Is this correct?

The books solution is this:

$$\mathrm{\forall}y(\mathrm{\neg}{\mathrm{\exists}}_{a}{\mathrm{\exists}}_{b}{\mathrm{\exists}}_{c}{\mathrm{\exists}}_{d},(a\ne b\text{}\vee a\ne b\text{}\vee a\ne c\text{}\vee a\ne d\text{}\vee b\ne c\text{}\vee b\ne d\text{}\vee c\ne d\wedge (G(a,y)\wedge G(b,y)\wedge G(c,y)\wedge G(d,y))$$

I am thinking this means: For all persons y, there does not exist four different people each of whom is the grandmother of y.

It seems as if mine is simple the negation of his statement, where

$$\mathrm{\neg}p\to q=\mathrm{\neg}q\wedge p$$

Express the statement that no one has more than three grandmothers.

G(x, y) : x is the grandmother of y

$$\mathrm{\exists}y(({\mathrm{\exists}}_{a}{\mathrm{\exists}}_{b}{\mathrm{\exists}}_{c}{\mathrm{\exists}}_{d},(G(a,y)\wedge G(b,y)\wedge G(c,y)\wedge G(d,y)))\to (a=b\text{}\vee a=b\text{}\vee a=c\text{}\vee a=d\text{}\vee b=c\text{}\vee b=d\text{}\vee c=d))$$

This is my solution. What I am trying to say is that if there exists a person y (anyone) who has four grandmothers then at least two of those grandmothers must be the same.

Is this correct?

The books solution is this:

$$\mathrm{\forall}y(\mathrm{\neg}{\mathrm{\exists}}_{a}{\mathrm{\exists}}_{b}{\mathrm{\exists}}_{c}{\mathrm{\exists}}_{d},(a\ne b\text{}\vee a\ne b\text{}\vee a\ne c\text{}\vee a\ne d\text{}\vee b\ne c\text{}\vee b\ne d\text{}\vee c\ne d\wedge (G(a,y)\wedge G(b,y)\wedge G(c,y)\wedge G(d,y))$$

I am thinking this means: For all persons y, there does not exist four different people each of whom is the grandmother of y.

It seems as if mine is simple the negation of his statement, where

$$\mathrm{\neg}p\to q=\mathrm{\neg}q\wedge p$$

Discrete mathAnswered question

tashiiexb0o5c 2022-09-07

Throw 5 times a dice with 6 sides colored in: blue, red, yellow, green, orange (5 colors)

How many possibles answers for getting at least one cube with '3'?

Exactly one cube with '2', and exactly one with with '4'?

How many possibles answers for getting at least one cube with '3'?

Exactly one cube with '2', and exactly one with with '4'?

Discrete mathAnswered question

Mutignaniz2 2022-09-07

How to solve for the inverse of f for a floor function? I really need to learn the method.

I was doing some exercises on discrete maths and came across this question I don't know how to solve, nor can I find any relevant examples in my book.

Suppose $f:\mathbb{R}\to \mathbb{R}$ where $f(x)=\lfloor x/2\rfloor $, if $T=\{3,4,5\}$ , then what's the inverse of f(T)?

I know how to get f(T) but how to get its inverse? Could anyone teach me please?

I was doing some exercises on discrete maths and came across this question I don't know how to solve, nor can I find any relevant examples in my book.

Suppose $f:\mathbb{R}\to \mathbb{R}$ where $f(x)=\lfloor x/2\rfloor $, if $T=\{3,4,5\}$ , then what's the inverse of f(T)?

I know how to get f(T) but how to get its inverse? Could anyone teach me please?

Students pursuing advanced Math are constantly dealing with advanced Math equations that are mostly used in space engineering, programming, and construction of AI-based solutions that we can see daily as we are turning to automation that helps us to find the answers to our challenges. If it sounds overly complex with subjects like exponential growth and decay, don’t let advanced math problems frighten you because these must be approached through the lens of advanced Math questions and answers. Regardless if you are dealing with simple equations or more complex ones, just break things down into several chunks as it will help you to find the answers.