- ganeshie8

Q4 and Q5
my answer is NOTA for both, looking for a better justification
http://assets.openstudy.com/updates/attachments/55ac929ee4b0d48ca8ed17ac-imqwerty-1437374350288-5.jpg

- schrodinger

I got my questions answered at brainly.com in under 10 minutes. Go to brainly.com now for free help!

Get this expert

answer on brainly

SEE EXPERT ANSWER

Get your **free** account and access **expert** answers to this

and **thousands** of other questions

- ganeshie8

#4
let \(i\) be the number of operations required excluding swaps, then :
\[(15-3i) + (12+2i) = 10\]
solving this gives me \(i=17\)
so a minimum of \(17\) operations is required to get a sum of \(10\).
since all the options are less than \(17\), i ticked last option.

- dan815

actually the min is even more than 17 :), u can only exchange a total of 5 times before u exhaust all red :

- ganeshie8

exactly, i was being pessimistic
actually it seems there is no way to get a state where \(red = yellow\)
but the proof seems hard

Looking for something else?

Not the answer you are looking for? Search for more explanations.

## More answers

- dan815

really

- ganeshie8

yes i checked for all the sequences upto a length of 50 operations
(2^50 sequences)

- dan815

how did u check so many

- dan815

thats not too big for the computer ?

- ganeshie8

each move consists of choosing between two operations :
1) swap
2) give away 3 red, get 2 yellow
for any sequence of length n, there are exactly 2^n possibilities

- dan815

not quite i think since there is that one restrition where if u dont have enough red u cannot give away anymore

- dan815

its slightly varying problem, the second u exchange u have stepped into a lower domain of numbers

- ganeshie8

when the red becomes negative, just break the loop

- dan815

when u are on 27 u can use swap to acheive all combinations, then when u are on 26, use swap

- ganeshie8

here is the script
https://jsfiddle.net/0keuvouv/

- dan815

what does push method do

- ganeshie8

push adds an element to the array

- ganeshie8

//declare the array subset
```
subset = [ ];
```
//add "2, 3" to the array
```
subset.push(2);
subset.push(3);
```

- ganeshie8

after above commands, subset[0] contains 2 and subset[1] contains 3

- dan815

for some reason i find it confusing still, can i ask u a simpler question

- dan815

lets say we start with 5 Red and 4 Yellow

- ganeshie8

this spits out all the sequences
https://jsfiddle.net/0keuvouv/1/

- dan815

was is the exchange option double way

- dan815

like u can exchange 2 yellow for 3 red and vice versa

- ganeshie8

if we start with 5 red and 5 yellow,
then we can give away 2 yellow, get 3 yellow and see if we ever arrive at 15 red and 12 yellow

- ganeshie8

idk programming wise it looks easy
but math wise it looks ahrd

- ganeshie8

*hard

- dan815

okay so we can exhcange both ways?

- dan815

Red to Yellow
and Yellow to Red right

- ganeshie8

nope, i think the problem changes based on the assumtion

- dan815

i think its red to yellow only

- dan815

if u can go other way its infinite

- ganeshie8

yeah i got u

- dan815

is it wrong to think this way okay wait

- dan815

lets say I start at 5 - Red 4 Yellow
i currently have 9 flowers
i can have 0 red to 9 red
a total of 9 options
i will swap in a way that i end up with 3 red and 6 yellow in the end
so i can go to 8 flow option with no problem
therefore
the total nubmer of combinations must be
10 swaps
1 exchange
9 swaps
1 exchange
8
1
7
.
.

- dan815

oh i see the problem is that we cannot get to all the combinaions with that many swaps

- dan815

wait i got an idea its not that many too i think

- dan815

|dw:1437489711171:dw|

- dan815

then ud do the same pattern to cover all the possibilities

- dan815

isnt this way a lot less options and u still get all the possible combinations

- dan815

the 2^50 stuff is when arrangement matters

- dan815

im not saying what im doing is optimal, but it is much less and shows that u can get to all the possiblites with less doesnt it

- dan815

for example lets say with that method defined above, inefficient maybe but still
lets say starting with 5 Red and 4 Yellow
(5,4)
(4,5)
(3,6)
.
.
(0,9)
.
.
(9,0)
Now exchnges stars the 8 flower case with
(6,2)
(5,3)
.
.
(0,8)
.
.
(8,0)
Now exhange starts the 7 floser case with
(5,2)
.
.
and so on

- dan815

i think finding a closer form answer for this pattern isnt anything too non trivial

- dan815

am i just not making any sense lol, i dont know

- dan815

findint the most efficient way to do these swaps looks like a very interesting problem though

- anonymous

heh, cute code @ganeshie8

- anonymous

dan815 here's better annotated code

- anonymous

https://jsfiddle.net/uL2ns14L/2/

- anonymous

hmm, presume we can represent a state as a binomial \(r+yX\) so then move-equivalence is represented by: $$r+yX \sim (r+yX)+ i(-3 + 2X) + j(2 - 3X)$$ so we're interested where \(i\ge 0\) represents exchanges and \(j\ge 0\) swapped exchanges (since swapping only exists to let us exchange in the reverse direction).
so it follows if we want \(15+12X\sim 5+5X\) we'd need to show that there is a pair of nonnegative integer solutions to $$10=-3i+2j\\7=2i-3j$$
so consider: $$20=-6i+4j\\21=6i-9j\\\implies 1=-5j$$so it follows \(5+5X\) is not move-equivalent to \(15+12X\)

- anonymous

and if we can never reach \(5+5X\) from \(15+12X\) then it follows that not every combination of flowers is reachable from \(15+12X\)

- anonymous

the set of reachable combinations (R,Y) is given here by Xs where the row gives Y and column gives R
http://pastebin.com/d8eT8WbJ

- dan815

here there is atleast one solution for red = yellow when u have 5 red and u exchange ull have 2 red and 2 yellow

- dan815

@oldrin.bataku oh thank you for that annotations!

- dan815

- dan815

omg i misunderstood the swap operation xD, i thought swap only changed 1 red to 1 yellow

- dan815

now everything makes sense again

- anonymous

well i gave a mathematical proof that 5 reds and 5 yellows from 15 and 12 is not possible no matter how many steps

- ganeshie8

That looks so neat @oldrin.bataku !
hope i can mimic the same to show that red=yellow is impossible

- ganeshie8

\(\cdots\)
so it follows if we want \(15+12X\sim a+aX\) we'd need to show that there is a pair of nonnegative integer solutions to
$$15=a-3i+2j\\12=a+2i-3j$$
subtract and get
$$3=5(j-i)$$
since \(5\nmid 3\), it follows \(a+aX\) is not move-equivalent to \(15+12X\)

- anonymous

yep, that works well :)

- anonymous

for counting all the possible reachable configurations, consider the system of inequalities: $$i\ge 0\\j\ge 0\\15-3i+2j\ge 0\\12+2i-3j\ge 0$$

- anonymous

this bounds a quadrilateral in the plane of \((i,j)\) so we can count the number of possible such configurations (each has a unique sequence of moves I think)

- anonymous

http://www.wolframalpha.com/input/?i=integer+solutions+to+x+%3E%3D+0%2C+y+%3E%3D+0%2C+15+-+3x+%2B+2y+%3E%3D+0%2C+12+%2B+2x+-+3y+%3E%3D+0

Looking for something else?

Not the answer you are looking for? Search for more explanations.