Question

Discrete study---B.

Answer 1

Hey, what's up man

Answer 2

Hey. So I am having trouble understanding what type of "..." notation he is talking about?

Answer 3

I think it means something like

\[x _{1}+x_{2}+...+x_{n}\]

Answer 4

so I'm just going with
1+3+5+(2n-1)

Answer 5

Okay. I think I may leave it as just X1 + X2 + ... + Xn and leave it generic.

Answer 6

sorry:
1+3+5+...+(2n-1)

Answer 7

How about P(n) on next one is P(n) = "Sum of first n odd numbers is n^2.)

Answer 8

so:
P(n) = 1+3+5+...+2n-1 = n^2?

Answer 9

Looks good to me.

Answer 10

Proof by induction?

Answer 11

Like this?
1+3+5+...+2k-1 + 2(k+1)-1 = n^2 + 2(k+1)-1

Answer 12

Just a sec...

Answer 13

I am going to write it out and I will post a pic.

Answer 14

What do you think?

Answer 15

very nice!

Answer 16

Have you done number 3?

Answer 17

No. Not sure how to approach it. You?

Answer 18

I tried looking up some info last night. Basically I think each element of set x has as many choices to be mapped to in y as there are elements in y.

Answer 19

X=3 elements, y = 5 elements.

so each x will have 5 choices, and there are 3 elements in x.

Answer 20

So in this scenario 5 X 5 X 5 choices. or 5^3

Answer 21

so each x will get m number of choices, and there are n number of x's. So m^n

Answer 22

Are you just making up the 3 and 5?

Answer 23

yes.

Answer 24

Ok. I see

Answer 25

Did you read the book to help with this?
It's completely unfamiliar compared to what we've done in class

Answer 26

google search. Not at all like class.

Answer 27

Search for how many functions from x to y.

Answer 28

Did you do 4 already?

Answer 29

Not yet. Trying out 5 first....have you done that one?

Answer 30

All but part D

Answer 31

IS the strategy to never leave an even amount left after first move?

Answer 32

Multiples of 4. But evens would work, too

Answer 33

My c might be wrong. Seems too simple:
P(n) = 4n

Answer 34

Nevermind, evens wouldn't work. You would lose if you left 6

Answer 35

Let me check my notes I thought we got part c in class. Yours looks good, but I am not too sure myself how to describe it...

Answer 36

Cant find them...

Answer 37

Assuming it's right, how would we apply induction to it?

Answer 38

Maybe by just showing tat 4(k+1) is also divisible by 4?

Answer 39

that cant be it...

Answer 40

All that takes is writing it down. The 4 is already factored out :p

Answer 41

I think we also need to include a variable that can only be 1,2,or 3 somehow.

Answer 42

I am going to try to look this problem up/.....

Answer 43

I am reading this right now... http://www.cs.cmu.edu/~anupamg/251-notes/games.pdf

Answer 44

Good find

Answer 45

Still havent made sense of it though lol

Answer 46

Do you have your notes? And did we get this part in class/?

Answer 47

I have them, but we only got as far as c; which was also seemingly incomplete.

Answer 48

Well how about one of us repost the question and get some help on it? I am prteyy unsure anout c and d.

Answer 49

Or do you want to mess with the other problem?

Answer 50

I think I'm on track with it. I'll share in a bit and see what you think

Answer 51

Thanks.

Answer 52

Game starts with 4k + (4-m) pennies where m = {1,2,3}
Basis: k = 1.
P(1) = 4 + (4-m)
You take m. -> 4 remain.
Opponent takes m -> 4-m remain.
You take 4-m and win.
Induction: Assume P(k) = 4k + (4-m) is a winning strategy.
P(k+1) = 4(k+1) + (4-m)
You take m. -> 4(k+1) remain = 4k +4
Opponent takes m. -> 4k + (4-m) = P(k)

Answer 53

Good?

Answer 54

Not really sure. Better than what I got which is nothing.....want to mess with the last one?

Answer 55

4?

Answer 56

yes.

Answer 57

a is
P(n) = 2^n -1

Answer 58

from class notes

Answer 59

thanks.

Answer 60

So is b just an if then statement saying in n=5 takes 2^5 -1 moves then n=6 takes 2^6 - 1 moves?

Answer 61

Wow, yeah. I was over-thinking it.

Answer 62

I am not too sure though if he just means for us to translate it...I think that is all I did.

Answer 63

from notes for c:
suppose a tower of 5 rings takes 31 moves to solve. Now suppose that our tower has 6 rings. Then the top 5 rings may be moved to the "non-destination" tower in 31 moves. Then the 6th ring can be moved to the "destination" tower in 1 move, and the top 5 may be moved to the "destination" tower in 31 moves. 31+1+31 = 63

Answer 64

ok....

Answer 65

Should that suffice for an answer, or was he just trying to help us think about it?

Answer 66

I think this works and is enough.

Answer 67

Then how that 31+31+1 which is what you described is equal to P(6) which is (2^6) - 1

Answer 68

So part d will be induction and the basis step is proving n=1 -> n=2 ?

Answer 69

That I a not so sure about how to finish.

Answer 70

I think we use Mk= 2^k - 1

Answer 71

number of moves.

Answer 72

\[Basis: n=1: 2^1 -> 2^2 -1\]
1st ring moved to non in 1 move, 2nd ring moved to dest in 1, 1st moved to dest in 1.
\[1+1+1 = 3 = 2^2 -2\]
\[Induction: n=k: 2^k -> 2^{k+1} -1\]

Answer 73

k rings moved to non in 2^k, 1 ring moved to dest in 1, k rings moved to dest in 2^k

Answer 74

how do we relate 2^k +1+2^k to 2^(k+1) -1?

Answer 75

not sure...

Answer 76

my whole induction part was missing the -1 part of 2^k -1

Answer 77

So \[ Induction: n=k: 2^k -1 -> 2^{k+1} -1\]
\[2^{k+1}-1 = 2*2^k -1 = 2^k +2^k -1\]
k rings move to non in 2^k -1
1 ring moved to dest in 1
k rings moved to dest in 2^k -1
\[2^k -1 +1 +2^k -1 = 2^k +2^k -1\]

Answer 78

I looked it up online and it seems most are starting from Mn=2^n -1 and proving base case then somehow doing this induction..I a still trying to work it out though....

Answer 79

Gotcha...looks good. I am going to re write some stuff and see what you think of what I am thinking.

Answer 80

I am going to eat some dinner. We can keep messing with number 5 in a bit or we can call it good for now and finish that problem in class?

Answer 81

I'm gonna eat too. I think I'm good with number 5. Part e is "second" btw.
Would you be done with the worksheet then?

Answer 82

I gotta get down part c and d....Ill mess with what you wrote earlier (; See you in the morning. Glad we got most of everything worked out fairy quickly.

Answer 83

How far are you with the book work?

Answer 84

I didnt know there was any ??

Answer 85

Crap lol. I swear I checked it yesterday and there was not book work....

Answer 86

Ok, I'm back

Answer 87

k

Answer 88

Have you done bookwork yet?

Answer 89

none

Answer 90

So for 6a would the domain be called N since we only have positive integers we can say natural numbers, and the range would be natural numbers as well?

Answer 91

Oh, yeah. I missed the concept of it. I was getting tripped up on the pairs part, and it's not even really relevant.

Answer 92

b is a little wierder but there is somewhat similiar example in book.

Answer 93

D: natural R: rational?

Answer 94

For b? I think the domain in b is all bit strings, and integers>0

Answer 95

integers great or equal to 0