Proof by Induction Help Challenge

[chilly sluice]

am struggling for 1).

I am using strong induction.

My base case is n = 0. So player 1 automatically wins.

Inductive hypothesis is for an arbitrary kE4N, there exists j such that 0<=j<=k where p(j) holds true.

Now i said that in order for player 1 to win, they must eat 3 chocolates to start.

Thus for my n = k+4 case,

I am getting n = k+1 left. I broke this up into 3 cases. 1) player 2 eats 1 chocolate, 2) player 2 eats 2 chocolate or 3) player 2 eats 3 chocolates.

(1) If player 2 eats 1 chocolate, there are n = k chocolate left. Thus n = k is in our inductive hypothesis thus player 1 is guaranteed to win.

(2) If player 2 eats 2 chocolates, there are n = k-1 left. But now this case has 3 sub cases where player 1 can eat 1, 2 or chocolates so I do not know how to deal with these subcases within subcases.

(3) same problem as (2).

[native thunder]

1. Wait patiently for a helper to come along.
2. Once someone helps you, say thank you and close the thread with:

+close

3. Feel free to nominate the person for helper of the week in #helper-nominations
4. Do not ping the mods, unless someone is breaking the rules.
5. If you're happy with the help you got here, and the server overall, you can contribute financially as well:

[wanton tartan]

so, you want an optimal strategy huh?

ok, let's start with a significantly large n (n > 10 ig)

maybe player 1 should try to eat as many chocolates as possible

now for n <= 10

hmmm

actually

let's divide this into 4 cases as you did

4k
4k+1
4k+2
4k+3

now, inductive hypothesis is that P(4k) is always true

so, an optimal strategy would be to somehow eat chocolates in such a manner that player one will have 4k chocolates left for him on any one of his given turns

so, let's first see for 4k+1

player 1 can't eat only one chocolate here, otherwise it's a guaranteed win for player 2

so

player 1 eats either 2 or 3 chocolates

now we have 4k+3 and 4k+2

now, if player 2 eats 3 chocolates for the 4k+3 case, player one wins.
so he has to eat either 1 or 2 chocolates

for 4k+2, he eats either 1 or 3 chocolates

now, in 4k+3, if player 2 eats 2 chocolates, the entire case gets reset

so we assume player 2 eats one choco

for 4k+2, he eats 3 choco for the same reasons

so, now we have 4k+2 and 4k+3

what

bruh

the cases repeat themselves

theres no optimal strat

idk...

[edgy cosmos]

guess what @molten badger had the exact same problem

the way you do it is divide cases

4k,4k+1,4k+2,4k+3

then induct after showing base cases.

4k and 4k+2 is won by p1

4k+1 and 4k+3 by p2

[molten badger]

nah only 4k + 1 is won by p2 iirc

[edgy cosmos]

ah right right

u 2 in the same class?

[molten badger]

no clue

prolly

[chilly sluice]

so i create base cases in the form of 4k, 4k + 1, 4k + 2, 4k + 3?

[edgy cosmos]

yes

[chilly sluice]

what would my inductive hypothesis be in this case?

would i have multiple ones ?

[edgy cosmos]

@molten badger will help @chilly sluice

u 2 in the same class

communicate amongst yourselves

[chilly sluice]

r we ?

[edgy cosmos]

yes

exact same question

[molten badger]

236? 😭

[chilly sluice]

:/

[molten badger]

shi i dont blame u the profs p ass

[chilly sluice]

have u finished?

[molten badger]

all the questions or just this?

for this I did the base case

and had the hypothesis

and then for the inductive step

4(k + 1)

4k + 4

I said p1 could mimic the eating pattern for 4k

so that p1 is left wit 4 on his pile

and then just eat 3, forcin p2 to eat the last one

[chilly sluice]

right

did you prove that 4k+1 always loses?

also how many questions have u compeleted on the problem set

[molten badger]

p much everyrhing beside q2 and that weird ass tile one

wbu

for q2 idk how to write it down formally n all that

like I got all my ideas onna rough draft

[chilly sluice]

ive done my formal proof for q1, q3. I know how to do q2 i think i have my draft and then i know how to do q6 p1

[molten badger]

q5 and q6 b is genuinely fucked

bro istg i havent learnt anythin new in this course

[edgy cosmos]

lemme see it too

the tile one just tetris tho

[edgy cosmos]

so like if you do this

you top the class

right?

[chilly sluice]

uh idk

these questions were given to everyone

[edgy cosmos]

ex6 is easier

[chilly sluice]

6. p1 i know how to do

6. 2 i havent tried but i dont think i know how to do it

[edgy cosmos]

mkay

p2?

aight

[chilly sluice]

maybe if i spend some time on it ill think of something

[edgy cosmos]

yeah so just notice

how a knight moves

when its on a new square

it has 7 possible NEW squares to go to

@chilly sluice can you solve it now?

[edgy cosmos]

now theres 7 such moves after those 7 moves themselves!!

[chilly sluice]

i think so but like

f(1) = 8

so if each of those 8 moves, theres 7 moves

wouldnt it be 8 * 7?

but it says f(2) is 33

[edgy cosmos]

nah some cases are false

as it shouldnt go to the same square

[chilly sluice]

hm

i know it creates an octogon

[edgy cosmos]

yes but the knights cant go to their original square

and

2 positions of knight might SHARE some square in range

[chilly sluice]

right

once i try it and draw it out i think it will be easier to visualize

[edgy cosmos]

yeahh

[molten badger]

right i found the recursion formula

(i think)

but idk how to prove it

[edgy cosmos]

describe it

heh

[molten badger]

induction wont work

[edgy cosmos]

wat

[molten badger]

ai so

this is the recursive formula i got

the recursion formula is

for n in 3n

t(0) = 1
t(3) = 3
t(n) = 3(t(n - 3)) + 2(t(n - 6)) ... + 2(t(3)) + 2(t(0))

[edgy cosmos]

have u tried using "Peper"

paper*

[molten badger]

wym

like regular paper?

[edgy cosmos]

yes draw it out

[molten badger]

I got the formula I was tripping

mine was harder to prove

[chilly sluice]

yo

im doing

6. p1

im wondering if this argument works

i am proving my formula using induction
so my formula is a piecewise function defined as

b(n) =
1, if n = 0
8 if n = 1
(2n+1)^2 if n>= 2
i want to prove my (2n+1)^2 formula
in my induction, my predicate is that for n moves where n>=2, it forms a square whose sides are 2n+1, thus the number of possible moves is going to be the area of that square which is (2n+1)^2
my base case is n = 2, a 5x5 square, which results in 25 thus b(2) holds true
now assume for an arbitrary k, b(k) holds true
i am struggling to argue for the n = k+1 case
should i say that starting from a 2k + 1 x 2k + 1 square
if the king is in the corner, it can move diagnoally up, if they are in the top corner, or diagonally down if they are in the bottom corner
and if they inbetween these corners, they can move sideways to the left
thus the new side length would be 2k + 1 + 2
which is 2k + 3
which is 2(k+1) + 1?
thus the new square is size 2(k+1) + 1 x 2(k+1) + 1
and thus the possible moves is the area of that square, which is (2(k+1)+1)^2
does this work?

[chilly sluice]

• close

+close