Scribd Logo
Upload

Welcome to Scribd!

  • 67 views

    Casework Aime

    Uploaded by

    Sarah Joy Manimtim
    The document provides solutions to multiple problems involving probability, combinatorics, and algebra. The key steps are: 1) For a problem on a bug moving on a cube, it counts the number of "good paths" where the bug visits each vertex exactly once in 7 moves. Through cases, it finds there are 3 good paths after 2 moves, for a total probability of 3/27. 2) For seating arrangements on 10 chairs, it uses inclusion-exclusion to find the number of subsets with at least 3 adjacent chairs is 550. 3) For a recursive formula problem, it sums the recursions to find the value is 12.

    Copyright:

    © All Rights Reserved
    Download as DOCX, PDF, TXT or read online from Scribd

    Casework Aime

    Uploaded by

    Sarah Joy Manimtim
    67 views5 pages
    The document provides solutions to multiple problems involving probability, combinatorics, and algebra. The key steps are: 1) For a problem on a bug moving on a cube, it counts the number of "good paths" where the bug visits each vertex exactly once in 7 moves. Through cases, it finds there are 3 good paths after 2 moves, for a total probability of 3/27. 2) For seating arrangements on 10 chairs, it uses inclusion-exclusion to find the number of subsets with at least 3 adjacent chairs is 550. 3) For a recursive formula problem, it sums the recursions to find the value is 12.

    Original Title

    casework aime.docx

    Copyright

    © © All Rights Reserved

    Available Formats

    DOCX, PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    The document provides solutions to multiple problems involving probability, combinatorics, and algebra. The key steps are: 1) For a problem on a bug moving on a cube, it counts the number of "good paths" where the bug visits each vertex exactly once in 7 moves. Through cases, it finds there are 3 good paths after 2 moves, for a total probability of 3/27. 2) For seating arrangements on 10 chairs, it uses inclusion-exclusion to find the number of subsets with at least 3 adjacent chairs is 550. 3) For a recursive formula problem, it sums the recursions to find the value is 12.

    Copyright:

    © All Rights Reserved
    Download as DOCX, PDF, TXT or read online from Scribd
    Download as docx, pdf, or txt
    67 views5 pages

    Casework Aime

    Uploaded by

    Sarah Joy Manimtim
    The document provides solutions to multiple problems involving probability, combinatorics, and algebra. The key steps are: 1) For a problem on a bug moving on a cube, it counts the number of "good paths" where the bug visits each vertex exactly once in 7 moves. Through cases, it finds there are 3 good paths after 2 moves, for a total probability of 3/27. 2) For seating arrangements on 10 chairs, it uses inclusion-exclusion to find the number of subsets with at least 3 adjacent chairs is 550. 3) For a recursive formula problem, it sums the recursions to find the value is 12.

    Copyright:

    © All Rights Reserved
    Download as DOCX, PDF, TXT or read online from Scribd
    Download as docx, pdf, or txt
    of 5

    Problem

    How many three-digit numbers satisfy the property that the middle digit is the
    average of the first and the last digits?

    Solution 2 (much faster and slicker)


    Alternatively, we could note that the middle digit is uniquely defined by the first
    and third digits, since it is half of their sum. This also means that the sum of
    the first and third digits must be even. Since even numbers are formed either
    by adding two odd numbers or two even numbers, we can split our problem
    into 2 cases:
    If both the first digit and the last digit are odd, then we have 1, 3, 5, 7, or 9 as
    choices for each of these digits, and there are numbers in this case.
    If both the first and last digits are even, then we have 2, 4, 6, 8 as our choices
    for the first digit and 0, 2, 4, 6, 8 for the third digit. There are
    numbers here.
    The total number, then, is
    Problem
    A bug starts at one vertex of a cube and moves along the edges of the cube
    according to the following rule. At each vertex the bug will choose to travel
    along one of the three edges emanating from that vertex. Each edge has
    equal probability of being chosen, and all choices are independent. What is
    theprobability that after seven moves the bug will have visited every vertex
    exactly once?

    Solutions
    Let us count the good paths. The bug starts at an arbitrary vertex, moves to a
    neighboring vertex (3 ways), and then to a new neighbor (2 more ways).
    So, without loss of generality, let the cube have vertex such
    that and are two opposite faces with above and
    above . The bug starts at and moves first to , then to .
    From this point, there are two cases.
    Case 1: the bug moves to . From , there is only one good move available,
    to . From , there are two ways to finish the trip, either by
    going or . So there are 2 good paths in
    this case.
    Case 2: the bug moves to . Case 2a: the bug moves . In this case,
    there are 0 good paths because it will not be possible to visit both and
    without double-visiting some vertex. Case 2b: the bug moves . There is
    a unique good path in this case, .
    Thus, all told we have 3 good paths after the first two moves, for a total
    of good paths. There were possible paths the bug
    could have taken, so the probability a random path is good is the ratio of good

    paths to total paths, .


    Problem
    Ten chairs are arranged in a circle. Find the number of subsets of this set of
    chairs that contain at least three adjacent chairs.

    Solution 1 (Casework)
    We know that a subset with less than chairs cannot contain adjacent
    chairs. There are only sets of chairs so that they are all adjacent. There
    are subsets of chairs where all are adjacent, and or where
    there are only If there are chairs, have all adjacent, or

    have adjacent, and or have adjacent. With chairs in the

    subset, have all adjacent, or have adjacent, or

    have adjacent, or have groups of adjacent chairs,

    and or have group of adjacent chairs. All possible


    subsets with more than chairs have at least group of adjacent chairs, so

    we add or , or , or , and or Adding, we


    get

    Solution 2 (PIE)
    Starting with small cases, we see that four chairs give , five chairs
    give , and six chairs give Thus, n chairs
    should give , as confirmed above. This claim can be verified by the
    principle of inclusion-exclusion: there are ways to arrange adjacent
    chairs, but then we subtract ways to arrange Finally, we add to
    account for the full subset of chairs. Thus, for we get a first count
    of
    However, we overcount cases in which there are two distinct groups of three
    or more chairs. Time to casework: we have cases for two groups of directly
    opposite each other, for two groups of four, for two groups of not
    symmetrically opposite, for a group of and a group of , and for a
    group of and a group of Thus, we have .
    Problem
    Given that

    find the value of .

    Solution
    We find that by the recursive formula. Summing the recursions

    yields . Thus .
    Since , it follows that

    You might also like