6
$\begingroup$

The OP is studying for his local math competition (Australian), and when running through past papers I found some questions subtle to handle. I decide to buy some books to aid my study, but there are questions I totally don't have any idea in what books they might appear, can you guys please tell me what branches are these questions from, and what books can I use to attack them? (e.g. the question 'finding all the integer values of $\displaystyle \frac{7n+18}{2n+3}$' is classified as number theory problem.)

(answers to these questions are not required though.)

1.How many (disconnected) enclosures can 24 fences make if fences are not allowed to intersect and can only be jointed at the end points? (e.g. it's obvious that with 5 fences we can only make 2 enclosures, namely 2 triangles with a shared side.)

What is the maximum number of intervals that can be connected between 6 points, whose configuration can be arbitrary but on the same plane, where the intervals are not allowed to intersect each other except at endpoints. (e.g. it's also obvious that with 4 points we can connect 6 intervals, namely the configuration of a CONVEX quadrilateral and its 2 diagonals.)

2.If $a_1=2$, $a_{n+1}=a_{n}+\mbox{the largest prime factor of $a_n$}$ (namely, $a_2=4,a_3=6,a_4=9$...) after what $n$ will $a_n$ exceed $2014$(not quite sure which number it is, but some given number).

3.If $a_1=3$,$a_{n+1}=a_n+a_n^2$, what is the second last digit of $a_{2014}$? Note:I edited an absent-minded typo here.

(Probably 2 and 3 are from number theory, but from what book can I learn the recursion part?)

4.If we divide a cube into 8 pieces in the canonical way (it's too complicated to post pictures.)and an ant is going from one vertex to the opposite vertex along the traces of the cuts,and is only allowed to turn at the intersection points. If the distance to the terminal point is only monotonically decreasing, how many different ways can the ant get there?

5.If 8 teams are playing a tournament where every team plays each other team once. 2 points for a win, 1 point for a draw and 0 points for a lose, how many points must a team obtain to secure being in the top 4?

6.How many non-isosceles triangles can be drawn with its vertices on the grid points of a 3*3 grid?

7.Assign one number to each vertex of a hexagon, and one number in the middle. If every number is to be the average of the numbers surrounding it (i.e. the central number is the average of the brim 6 numbers, and the every brim point is the average of the central number and its adjacent 2 numbers.) If one brim point is 1 and the one opposite to it is 100, what are the others?

There are still others to be asked, but we can stop here. I only need to know what branches they are from, so that I can find books to aid myself. Thanks

| cite | improve this question | |
$\endgroup$
  • 1
    $\begingroup$ #1 seems to be Graph theory. It translates to: Given $n$ edges, what is the maximum number of disconnected graphs you can make out of it, which are piecewise connected? Note: For 5 edges, your answer of 2 triangles with a shared side is incorrect, as the graph so obtained is connected, whereas you ask for a disconnected graph. $\endgroup$ – Train Heartnet Nov 30 '14 at 5:23
  • $\begingroup$ I'd say that all of those are combinatorics or number theory. I'm not sure of any good books though - especially since "combinatorics" can arise out of basically any discrete mathematical structure (though I suppose many of these questions are graph theory-ish) $\endgroup$ – Milo Brandt Nov 30 '14 at 5:24
  • $\begingroup$ For #2 and #3, I believe the keywords you are looking for are "difference (not differential) equations" and "generating functions". These may not necessarily be the path to solving those questions, but in general, recursive sequences are studied using the above. And for the remaining questions, as Meelo pointed out, almost all belong to the domain of enumerative combinatorics with a graph-theoretic emphasis. $\endgroup$ – Train Heartnet Nov 30 '14 at 5:37
  • 1
    $\begingroup$ Many contest problems are not about understanding a branch of mathematics, but about good problem solving skills. e.g. I estimate at least one problem is just recognizing that if you write down what you're asked to do, you get a high school algebra problem (or, at least, a major part of the problem is just solving the high school algebra problem). (there may be tricks to get an easier problem, but those wouldn't be learned by studying a mathematical subject) $\endgroup$ – user14972 Nov 30 '14 at 5:39
  • 1
    $\begingroup$ @JobinIdiculla I believe for #1 the enclosures are supposed to be 'disjoint', but the graph itself is not disconnected. $\endgroup$ – Steven Stadnicki Nov 30 '14 at 5:58
5
$\begingroup$

Part of the difficulty of a contest math problem lies in deciding what area or possibly areas of math you should be looking at, and another part lies in applying general problem-solving strategies rather than applying specific knowledge about different fields of mathematics. This is why many of the standard contest preparation books are not specific to one area of math. Three standard examples are:

So I don't expect trying to find books about a particular area to help much: it's usually better to focus on general problem-solving, at least for contests at this level.

Your problem all roughly fall under the headings of geometry, combinatorics, number theory, or graph theory, but I don't think you need to know many specific things about any of these subjects to solve the problems. (Edit: With perhaps the following exception: for the first problem as well as for the unnumbered problem beneath it, it might be helpful to know Euler's formula for planar graphs.) Let me instead offer some hints involving general problem-solving strategies. I haven't solved any of these problems, so these are the things I would try before knowing whether or not they actually work.

  1. Replace $24$ with some smaller numbers; I see you already started with $5$, but keep going. The real question is what you can do with $n$ fences. Think about inducting on $n$. Simultaneously try to write down examples and upper bounds. For example, try to show that with $n$ fences you can't get more than $n - 2$ enclosures, then try to improve this.

  2. Calculate more terms and see if you notice a useful pattern. I did this for a bit, and you'll notice that it's convenient to write $a_n$ as a product in a particular way.

  3. Edit: Calculate more terms of the sequence $\bmod 100$ and see if you notice a useful pattern.

  4. Count how many different ways the ant can get from where it's going to any of the other possible places it can go. You'll notice a useful recursion.

  5. Try to figure out how many points the top $4$ teams can possibly get, keeping in mind that they can't all win all of their games.

  6. Count all of the triangles, then count all of the isosceles ones. Edit: To count all triangles, start by counting all triplets of distinct points, then subtract the ones that aren't triangles.

  7. You can try to write down a big system of equations here, but it'll get messy. I suggest doing the following instead: ignore the $1$ and $100$ for now. Fix the value of some of the numbers in such a way that they uniquely determine the others, and you'll get a simpler system of equations to solve. Edit: Are you sure you stated this correctly? As stated, I believe all of the numbers must be the same.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ For $3$, I believe that the question deals with taking the sequence modulo $100$ and looking at the "tens" digit. $\endgroup$ – apnorton Nov 30 '14 at 15:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.