A community for students.

Here's the question you clicked on:

55 members online
  • 0 replying
  • 0 viewing

ganeshie8

  • one year ago

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

  • This Question is Closed
  1. ganeshie8
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 4

    #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.

  2. dan815
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

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

  3. ganeshie8
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 4

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

  4. dan815
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    really

  5. ganeshie8
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 4

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

  6. dan815
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    how did u check so many

  7. dan815
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    thats not too big for the computer ?

  8. ganeshie8
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 4

    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

  9. dan815
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

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

  10. dan815
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

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

  11. ganeshie8
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 4

    when the red becomes negative, just break the loop

  12. dan815
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

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

  13. ganeshie8
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 4

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

  14. dan815
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    what does push method do

  15. ganeshie8
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 4

    push adds an element to the array

  16. ganeshie8
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 4

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

  17. ganeshie8
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 4

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

  18. dan815
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

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

  19. dan815
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    lets say we start with 5 Red and 4 Yellow

  20. ganeshie8
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 4

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

  21. dan815
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    was is the exchange option double way

  22. dan815
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

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

  23. ganeshie8
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 4

    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

  24. ganeshie8
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 4

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

  25. ganeshie8
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 4

    *hard

  26. dan815
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    okay so we can exhcange both ways?

  27. dan815
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    Red to Yellow and Yellow to Red right

  28. ganeshie8
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 4

    nope, i think the problem changes based on the assumtion

  29. dan815
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    i think its red to yellow only

  30. dan815
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    if u can go other way its infinite

  31. ganeshie8
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 4

    yeah i got u

  32. dan815
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    is it wrong to think this way okay wait

  33. dan815
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    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 . .

  34. dan815
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

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

  35. dan815
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

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

  36. dan815
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    |dw:1437489711171:dw|

  37. dan815
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    then ud do the same pattern to cover all the possibilities

  38. dan815
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

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

  39. dan815
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    the 2^50 stuff is when arrangement matters

  40. dan815
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    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

  41. dan815
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    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

  42. dan815
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

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

  43. dan815
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

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

  44. dan815
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

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

  45. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    heh, cute code @ganeshie8

  46. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    dan815 here's better annotated code

  47. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

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

  48. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    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\)

  49. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    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\)

  50. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    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

  51. dan815
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

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

  52. dan815
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    @oldrin.bataku oh thank you for that annotations!

  53. dan815
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    @Empty

  54. dan815
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

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

  55. dan815
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    now everything makes sense again

  56. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

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

  57. ganeshie8
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 4

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

  58. ganeshie8
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 4

    \(\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\)

  59. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    yep, that works well :)

  60. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    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$$

  61. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    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)

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

    • Attachments:

Ask your own question

Sign Up
Find more explanations on OpenStudy
Privacy Policy

Your question is ready. Sign up for free to start getting answers.

spraguer (Moderator)
5 → View Detailed Profile

is replying to Can someone tell me what button the professor is hitting...

23

  • Teamwork 19 Teammate
  • Problem Solving 19 Hero
  • You have blocked this person.
  • ✔ You're a fan Checking fan status...

Thanks for being so helpful in mathematics. If you are getting quality help, make sure you spread the word about OpenStudy.

This is the testimonial you wrote.
You haven't written a testimonial for Owlfred.