Discussion about math, puzzles, games and fun.   Useful symbols: ÷ × ½ √ ∞ ≠ ≤ ≥ ≈ ⇒ ± ∈ Δ θ ∴ ∑ ∫  π  -¹ ² ³ °

You are not logged in.

## #1 Help Me ! » Boolean Questions » 2013-04-17 04:48:14

rhymin
Replies: 1

I'm confused about a couple things related to Boolean algebra and expressions and was hoping someone could explain it better than textbook.

1) How does Boolean algebra capture the essential properties of logic operations and set operations?

2) How does the reduction of Boolean expressions to simpler forms resemble the traversal of a tree? What sort of Boolean expression would you end up with at the root of the tree?

## #2 Help Me ! » Graph Question » 2013-04-10 04:19:38

rhymin
Replies: 1

I haven't studied graphs in a long time and was wondering how to go about answering these 2 questions:

1) Random graphs are a fascinating subject of applied and theoretical research. These can be generated with a fixed vertex set V and edges added to the edge set E based on some probability model, such as a coin flip. Speculate on how many connected components a random graph might have if the likelihood of an edge (v1,v2) being in the set E is 50%. Do you think the number of components would depend on the size of the vertex set V? Explain why or why not.

2) You are an electrical engineer designing a new integrated circuit involving potentially millions of components. How would you use graph theory to organize how many layers your chip must have to handle all of the interconnections, for example? Which properties of graphs come into play in such a circumstance?

## #3 Help Me ! » Special Functions and Computational Complexity » 2013-04-01 11:24:37

rhymin
Replies: 0

I'm working out of a friend's textbook to try and prepare myself for a class I'll be taking in a month or so. I was wondering if someone could give me the answers to these problems so I have a better understanding of how to solve them?

1) How do you figure the degree of the table?

Let A_i, 1 ≤ i ≤ 5, be the domains for a table D ⊆ A_1 x A_2 x A_3 x A_4 x A_5, where A_1 = {U, V, W, X, Y, Z} (used as code names for different cereals in a test), and A_2 = A_3= A_4 = A_5 = Z^+.

Table D:

Code Name of Cereal / Grams of Sugar per 1-oz Serving / % of RDA^a of Vitamin A per 1-oz Serving / % of RDA Vitamin C per 1-oz Serving / % of RDA of Protein per 1-oz Serving
U    1    25    25    6
V    7    25    2    4
W    12    25    2    4
X    0    60    40    20
Y    3    25    40    10
Z    2    25    40    10

2) How do you determine the best "big-Oh" form?

Use the results of Table 1 to determine the best big-Oh form for the following function f: Z^+→ R.
f(n) = 3n + 7

Table 1 (I'm not sure how to write tables so I used the dash (-----):

Big-Oh Form ------------------------ Name
O(1) --------------------------------- Constant
O(log_2 n) -------------------------- Logarithmic
O(n) --------------------------------- Linear
O(n log_2 n) ------------------------ n log_2 n
O(n^3) ------------------------------ Cubic
O(n^m), m = 0, 1, 2, 3,... ------- Polynomial
O(c^n), c > 1 ----------------------- Exponential

## #4 Re: Help Me ! » Division Algorithm? » 2013-03-28 05:55:42

Bob Bundy, no worries at all.  The confusion actually helped me more because I don't think I will ever forget it now because of this discussion.  Also, thank you so much for showing how you solved for that.

One more question:

So for problem #1, the answer is no.

And you can use any numbers to prove that, such as Nehushtan's example?

9|6 x 15 but 9 is not a factor of 6 or 15   Would that be a good way to explain that it is false?

## #5 Re: Help Me ! » Division Algorithm? » 2013-03-27 15:15:57

rhymin wrote:

So for problem #1, the answer is no.

And you can use any numbers to prove that, such as Nehushtan's example?

9|6 x 15 but 9 is not a factor of 6 or 15   Would that be a good way to explain that it is false?

BTW, I just wanted to confirm that this is correct?

## #6 Re: Help Me ! » Division Algorithm? » 2013-03-27 15:08:54

The textbook is Discrete and Combinational Mathematics.

Ahh, i see that Euclid's algorithm is a way to find the GCD.  Awesome.

Could you please shine some light on the second part of the problem?

## #7 Re: Help Me ! » Division Algorithm? » 2013-03-27 11:21:13

What is the easiest way to figure out the GCD of 2 large numbers besides manually trying to divide by random numbers?  I see now 7 is the GCD.

Sorry, but I just don't get how 8a and -63b were calculated.

I looked up Linear Relationship - A statistical term used to describe the relationship between a variable and a constant. Linear relationships can be expressed in a graphical format where the variable and the constant are connected via a straight line or in a mathematical format where the independent variable is multiplied by the slope coefficient, added by a constant, which determines the dependent variable.

But that is just adding to the confusion a bit.  Sorry, I know this can be frustrating as I'm not very smart in this area.

## #8 Re: Help Me ! » Division Algorithm? » 2013-03-27 07:49:55

bobbym wrote:

Hi;

2)

I am not sure I understand the question.

a = 1820
b = 231

(1820,231) = 7

1820 t +231 s = 7

t = 8
s = -63

8a - 63b = 7

I'm still confused by this.  Are t and s just random letters picked to help solve the problem?  I also don't know where the 7 comes from unless you divide 1820 by 231 and leaving the remainder out.  Is this called the quotient?

I'm not sure where 8a or -63b comes from either.

Any explanation is highly appreciated!

## #9 Re: Help Me ! » Division Algorithm? » 2013-03-27 07:46:58

So for problem #1, the answer is no.

And you can use any numbers to prove that, such as Nehushtan's example?

9|6 x 15 but 9 is not a factor of 6 or 15   Would that be a good way to explain that it is false?

## #10 Re: Help Me ! » Division Algorithm? » 2013-03-27 05:15:37

And thank you everyone for your replies!

## #11 Re: Help Me ! » Division Algorithm? » 2013-03-27 05:14:16

For now, I am teaching myself discrete math because it is a requirement in the information technology field.  My friend is getting a degree in the same thing as me and let me use his old discrete math book, "Discrete and Combinational Mathematics".

I am still a bit confused because 2 people said a couple different things.

## #12 Re: Help Me ! » Division Algorithm? » 2013-03-26 19:08:20

Thanks for the insult I guess.

Like I said, I haven't taken a math class in several years.

## #13 Re: Help Me ! » Division Algorithm? » 2013-03-26 18:19:53

Thanks for replying so quickly   Few questions:

What is GCD?

How did you get 7, 8a, -63s?

## #14 Re: Help Me ! » Division Algorithm? » 2013-03-26 18:12:31

I'm not sure, that is exactly how it is written in the textbook.  What is s and t?  And how did you decide that a = 1820, b = 231...when 231 was listed before 1820?

## #15 Help Me ! » Division Algorithm? » 2013-03-26 16:08:48

rhymin
Replies: 30

I'm practicing some discrete math from a friend's textbook.  My class isn't for a month, but I am struggling so far (I knew I would as I haven't taken a math course in several years).  I'm working on exercises in the book and found these 2 problems to be quite confusing.

1) If a, b, c ∈ Z^+ and a|bc, does it follow that a|b or a|c?

2) For each of the following pairs, a, b ∈ Z^+,  determine gcd(a, b) and express it as a linear combination of a, b.

231, 1820

Any help on how to solve these is greatly appreciated.

Thank you!

## #17 Re: Help Me ! » Permutation » 2013-03-26 15:57:05

Ohh, thank you for that, I get it now.
123: 2 ascents
132: 1 ascent
213: 1 ascent
231: 1 ascent
312: 1 ascent
321: 0 ascents

How would you write the answer? Just like this?

## #18 Re: Help Me ! » Permutation » 2013-03-26 15:42:00

I guess what confused me the most was the last part of the question, "for k = 0, 1, 2".  What exactly does this mean?  Because the example right before it doesn't mention anything about that.

## #19 Help Me ! » Permutation » 2013-03-26 14:49:05

rhymin
Replies: 7

A bit confused on how to begin this.

Consider the permutation of 1, 2, 3, 4. The permutation 1432, for instance, is said to have one ascent  namely, 14 (since 1 < 4). This same permutation also has two descents  namely, 43 (since 4 > 3) and 32 (since 3 > 2). The permutation 1423, on the other hand, has two ascents, at 14 and 23  and the one descent 42.

a) How many permutations of 1, 2, 3 have k ascents, for k = 0, 1, 2?