Difference between revisions of "KGS math club"
(added "Parade" puzzle) |
|||
(102 intermediate revisions by 9 users not shown) | |||
Line 1: | Line 1: | ||
A group of people on [http://www.gokgs.com Kiseido Go Server] Mathematics room. | A group of people on [http://www.gokgs.com Kiseido Go Server] Mathematics room. | ||
− | The meaning of this page is to collect the problems posed there and save hints and solution suggestions. | + | The meaning of this page is to collect the problems posed there and save hints and solution suggestions. In order to write something, I'm afraid you need to register to the AoPS wiki first. After that you're good to go. |
+ | |||
+ | Adding problems should be quite straightforward with the copy-paste template in the wiki source. Please add <math>-tags (or dollar signs, it seems) where required, e.g. <math>f''(x)</math>. Still, if you don't, somebody else will; all additions are appreciated. | ||
{| border="1" cellpadding="5" width="100%" style="border:3px dashed rgb(220,230,255);" | {| border="1" cellpadding="5" width="100%" style="border:3px dashed rgb(220,230,255);" | ||
|+ KGS math problems | |+ KGS math problems | ||
|- | |- | ||
− | ! | + | !Added |
!style="background-color:rgb(220,230,255);" | Author | !style="background-color:rgb(220,230,255);" | Author | ||
!Problem | !Problem | ||
!style="background-color:rgb(220,230,255);" | Solutions | !style="background-color:rgb(220,230,255);" | Solutions | ||
+ | |||
+ | <!-- TEMPLATE, COPY-PASTE-FILL-IN: date, author, problem, solver; n = problem number, then click the red link and copypaste the solution, save. There. If anyone can do the wiki table formatting more elegantly, be my guest; after all, this is wikiiii. | ||
+ | |||
+ | COPY AFTER THIS LINE | ||
+ | |||
+ | |- valign="top" | ||
+ | | | ||
+ | |style="background-color:rgb(220,230,255);" | | ||
+ | | | ||
+ | |style="background-color:rgb(220,230,255);" | [[KGS math club/solution_n| solution ]] | ||
+ | |||
+ | UNTIL BEFORE THIS LINE, paste after this line. Adding newlines to separate rows (Enter key) is encouraged, they won't affect the final formatting --> | ||
+ | |||
+ | |- valign="top" | ||
+ | |2016-12-04 | ||
+ | |style="background-color:rgb(220,230,255);" |Warfreak2 | ||
+ | |The card game Parade has a deck of 66 cards, containing each pair of colour and rank, where there are 6 colours and 11 ranks (0 to 10). A parade is a sequence of cards played one by one; each time a card is played at the end of the sequence, count that number back, and from there to the start, delete any card of the same colour, or of a less-than-or-equal rank. What is the greatest possible length a parade can reach? | ||
+ | |style="background-color:rgb(220,230,255);" | | ||
+ | |||
+ | |- valign="top" | ||
+ | |2016-12-04 | ||
+ | |style="background-color:rgb(220,230,255);" |maproom | ||
+ | |You are driving, in mild dry weather, along a straight road at a steady 70 m.p.h. A police car approaches in the opposite direction with its siren on. As you pass, you hear the pitch of the siren drop by a perfect fifth. What is the speed of the police car? | ||
+ | |style="background-color:rgb(220,230,255);" | | ||
+ | |||
+ | |- valign="top" | ||
+ | |2016-05-07 | ||
+ | |style="background-color:rgb(220,230,255);" |parigi | ||
+ | |With all numbers written in base 10: prove that any integer ending in 7 has a multiple consisting entirely of a string of 1s. | ||
+ | |style="background-color:rgb(220,230,255);" |[[KGS math club/solution_repunit| solution]] by Warfreak2 | ||
+ | |||
+ | |- valign="top" | ||
+ | |2016-05-05 | ||
+ | |style="background-color:rgb(220,230,255);" |maproom | ||
+ | |Devise a set of denominations, as few as possible, such that any integer value from 1 to 100 cents can be paid with no more than two coins. | ||
+ | |style="background-color:rgb(220,230,255);" |[[KGS math club/solution_coins| solution]] by zwim | ||
+ | |||
+ | |- valign="top" | ||
+ | |2015 | ||
+ | |style="background-color:rgb(220,230,255);" |njs | ||
+ | |We fill in a 3x3 square with non-negative integers such that the sum of the numbers in each row and column equals n. Show that the number of such squares is (n+2 choose 2)^2 - 3 * (n+3 choose 4). | ||
+ | |style="background-color:rgb(220,230,255);" | | ||
+ | |||
+ | |- valign="top" | ||
+ | |2015 | ||
+ | |style="background-color:rgb(220,230,255);" |twillo | ||
+ | |For which n can the complete graph K_n have its set of edges partitioned to form edge-disjoint Hamiltonian circuits or Hamitonian paths? | ||
+ | |style="background-color:rgb(220,230,255);" | | ||
+ | |- valign="top" | ||
+ | |2014-09-21 | ||
+ | |style="background-color:rgb(220,230,255);" |njs | ||
+ | |Dissect a regular hexagon into three pieces which can be rearranged to form an equlateral triangle. | ||
+ | |style="background-color:rgb(220,230,255);" | | ||
+ | |||
+ | |- valign="top" | ||
+ | |2014-09-10 | ||
+ | |style="background-color:rgb(220,230,255);" |ndkrempel | ||
+ | |A chess piece, the prince, can move one square south or one square east or one square diagonally north-west. For what sizes of rectangular board can it do a Hamiltonian circuit of the board, visiting each square once and ending up where it started? | ||
+ | |style="background-color:rgb(220,230,255);" | [[KGS math club/solutio_prince| solution]] by gu1729 | ||
+ | |||
+ | |- valign="top" | ||
+ | |2014-06-12 | ||
+ | |style="background-color:rgb(220,230,255);" |twillo | ||
+ | |Topological puzzle: you have a thick rope, and lots of rubber bands each too small to go round the rope. Can you make a structure from the bands, and put it over the end of the rope, such that it cannot be removed by someone without access to an end of the rope? | ||
+ | |style="background-color:rgb(220,230,255);" | | ||
+ | |||
+ | |- valign="top" | ||
+ | |2014-05-30 | ||
+ | |style="background-color:rgb(220,230,255);" |twillo | ||
+ | |For which natural numbers <b>n</b> is it possible to take the integers 1..n and pair them up so that the sum of each pair is a perfect square? | ||
+ | |style="background-color:rgb(220,230,255);" | [[KGS math club/solution_pairing| solution]] by gu1729 | ||
+ | |||
+ | |- valign="top" | ||
+ | |2013? | ||
+ | |style="background-color:rgb(220,230,255);" |twillo | ||
+ | |K_10 is a set of 10 points, with each pair of them joined by a single edge. Colour these edges so that as many as possible of the 3-points subsets are joined by two blue and one red edge. | ||
+ | |style="background-color:rgb(220,230,255);" | | ||
+ | |||
+ | |- valign="top" | ||
+ | |2013? | ||
+ | |style="background-color:rgb(220,230,255);" |sume | ||
+ | |An undirected graph has each vertex connected to no more than five other vertices. Show that it is always possible to color the vertices black and white in such a way that no vertex is connected to more than two vertices of the same color as itself; or provide a counterexample. | ||
+ | |style="background-color:rgb(220,230,255);" | | ||
+ | |||
+ | |- valign="top" | ||
+ | |2013-10-08 | ||
+ | |style="background-color:rgb(220,230,255);" |maproom | ||
+ | |A point is doing Brownian motion in the plane. It is now at (x=1, y=1). With probability 1, it will reach the line (y=0). When it next does, what is the probabilty that its x value will be positive? | ||
+ | |style="background-color:rgb(220,230,255);" |[[KGS math club/solution_06_21| solution]] by cyndane | ||
+ | |||
+ | |- valign="top" | ||
+ | |2013-09-22 | ||
+ | |style="background-color:rgb(220,230,255);" |maproom | ||
+ | |A room contains 100 boxes numbered 1..100, each containing a distinct randomly-selected prisnoer's name. The 100 prisoners will each in turn be admitted to the room and allowed to examine the contents of up to 50 boxes, but to change nothing. They may plan their strategy in advance, but may not communicate once a box has been opened. Iff every prisoner finds his own name, they will all be released. What is the best success rate thay can achieve? | ||
+ | |style="background-color:rgb(220,230,255);" | | ||
+ | |||
+ | |- valign="top" | ||
+ | |2013-07-22 | ||
+ | |style="background-color:rgb(220,230,255);" |maproom | ||
+ | |There is a lottery. You hold one ticket, eight others have been sold. A tenth and final ticket is now up for sale. Then four prizes, of €10, €5, €2, €1, will be issued, as follows. A random ticket will be chosen, and its holder given the biggest remaining prize and all his tickets cancelled, until the prizes have all been distributed. What is the most you should be willing to pay for the tenth ticket? | ||
+ | |style="background-color:rgb(220,230,255);" |[[KGS math club/solution_11_25| solution]] by zwim | ||
+ | |||
+ | |- valign="top" | ||
+ | |2013-04-? | ||
+ | |style="background-color:rgb(220,230,255);" |parigi | ||
+ | |There has been a murder. Two sheriffs have each independently reduced the publicly-known list of eight suspects to two. Using an open communication channel, how can they (1) check whether their length-two lists differ; and if they do, (2) let each other know who the murderer is? They must not let the listeners to the channel (who can break public-key encryption) know who the murderer is. | ||
+ | |style="background-color:rgb(220,230,255);" |[[KGS math club/solution_11_26| solution]] by YogSothoth | ||
+ | |||
+ | |- valign="top" | ||
+ | |2013-04-? | ||
+ | |style="background-color:rgb(220,230,255);" |maproom | ||
+ | |Can you dissect a disk into congruent connected pieces in such a way that more than one, but not all, of the pieces have the disk's centre on their border? | ||
+ | |style="background-color:rgb(220,230,255);" |[[KGS math club/solution_11_24| solution]] by Leira | ||
+ | |||
+ | |- valign="top" | ||
+ | |2012-10-? | ||
+ | |style="background-color:rgb(220,230,255);" |parigi | ||
+ | |Can you arrange ten points in the plane in such a way that they cannot be covered by a set of non-overlapping unit disks? | ||
+ | |style="background-color:rgb(220,230,255);" |[[KGS math club/solution_11_22| solution]] by zwim | ||
+ | |||
+ | |- valign="top" | ||
+ | |2012-10-08 | ||
+ | |style="background-color:rgb(220,230,255);" |Niall | ||
+ | |Four point frogs initially form a square in the plane. Any frog can jump over any other frog in such a way that the other frog forms the midpoint of its jump. Can the frogs ever form a larger square? Can any three of them ever be colinear? | ||
+ | |style="background-color:rgb(220,230,255);" |[[KGS math club/solution_11_21| solution]] by gu1729 | ||
+ | |||
+ | |- valign="top" | ||
+ | |2012-10-08 | ||
+ | |style="background-color:rgb(220,230,255);" |maproom | ||
+ | |You have three amply large buckets, each containing a known number of pebbles. You are allowed, as often as you like, to choose two buckets and to move from the first to the second as many pebbles as were previously in the second. You must always choose them so that there are enough pebbles in the first. Show that, for all sets of starting numbers, you can eventually obtain an empty bucket. | ||
+ | |style="background-color:rgb(220,230,255);" |[[KGS math club/solution_11_23| solution]] by YogSothoth | ||
+ | |||
+ | |- valign="top" | ||
+ | |2012-08-02 | ||
+ | |style="background-color:rgb(220,230,255);" |Warfreak2 | ||
+ | |Without reference to any external material, prove that the side:diagonal ratio of a regular pentagon is 2 : 1+√5. | ||
+ | |style="background-color:rgb(220,230,255);" |[[KGS math club/solution_11_20| solution]] by flyingdario | ||
+ | |||
+ | |- valign="top" | ||
+ | |2012-08-02 | ||
+ | |style="background-color:rgb(220,230,255);" |maproom | ||
+ | |Find a set of sets of natural numbers such that the sum of all the numbers is 20 and their product is as great as possible. | ||
+ | (This is a trick question. This trick is in understanding the properties of sets.) | ||
+ | |style="background-color:rgb(220,230,255);" |[[KGS math club/solution_11_19| solution]] by weiqidevil | ||
+ | |||
+ | |- valign="top" | ||
+ | |2012-06 | ||
+ | |style="background-color:rgb(220,230,255);" |maproom | ||
+ | |A, B and C have a cycle race from E to F. All three set out at 10am at different speeds from E. A is 5km/h faster than B and 10km/h faster than C. They all maintain a constant speed over the course except as follows. Also travelling the same route at a constant speed is a burger van. Any cyclist reaching the van immediately loses a constant 20km/h in speed. The van leaves E at 9am and arrives in F at 3pm; the race itself is a three-way tie. When does it finish? | ||
+ | |style="background-color:rgb(220,230,255);" |[[KGS math club/solution_11_18| solution]] by DanielTom | ||
+ | |||
+ | |- valign="top" | ||
+ | |2012-03-05 | ||
+ | |style="background-color:rgb(220,230,255);" |maproom | ||
+ | |31 points are equally spaced in a circle. In how many distinct ways can you pick 6 of them such that every pair of picked points is at a different separation? | ||
+ | |style="background-color:rgb(220,230,255);" |[[KGS math club/solution_11_17| solution]] by iceweasel | ||
+ | |||
+ | |- valign="top" | ||
+ | |2012-01-20 | ||
+ | |style="background-color:rgb(220,230,255);" |twillo | ||
+ | |You have 64 coins heads up and 36 coins tails up - you have to split them into 2 piles with equal numbers of heads in each. You are permitted to turn coins over but can never tell what state they are in. | ||
+ | |style="background-color:rgb(220,230,255);" |[[KGS math club/solution_11_27| solution]] by YogSothoth | ||
+ | |||
+ | |- valign="top" | ||
+ | |2012-01-25 | ||
+ | |style="background-color:rgb(220,230,255);" |maproom | ||
+ | |Find a permutation group G acting transitively on N letters, and a permutation group H also acting transitively on N letters, such that G and H are isomorphic, but no isomorphism between them corresponds to any mapping of the two sets of letters. | ||
+ | |style="background-color:rgb(220,230,255);" |[[KGS math club/solution_11_15| solution]] by D239500800 | ||
+ | |||
+ | |- valign="top" | ||
+ | |2012-01-20 | ||
+ | |style="background-color:rgb(220,230,255);" |twillo | ||
+ | |An odd number of points are arranged in the plane with no three colinear. Prove that for each of these points, the number of triangles (whose vertices are others of the points) within which it lies is even. | ||
+ | |style="background-color:rgb(220,230,255);" |[[KGS math club/solution_11_14| solution]] by Warfreak2 | ||
|- valign="top" | |- valign="top" | ||
− | | | + | |2011-11-21 |
− | |style="background-color:rgb(220,230,255);" | | + | |style="background-color:rgb(220,230,255);" |maproom |
− | | | + | |You deal a standard bridge pack to four players in the usual way. Which is more likely, and by roughly how much: |
− | |style="background-color:rgb(220,230,255);" | [[KGS math club/ | + | |
+ | (a) You have cards in only two suits, or | ||
+ | |||
+ | (b) There is some suit in which both you and your partner have no cards? | ||
+ | |style="background-color:rgb(220,230,255);" |[[KGS math club/solution_11_13| solution]] by Zahlman | ||
+ | |||
+ | |- valign="top" | ||
+ | |2011-11-08 | ||
+ | |style="background-color:rgb(220,230,255);" | Niall | ||
+ | |An island has 3 colours of snake: red, blue and green. When snakes of different colors meet they both turn into the third color. They never breed or die. | ||
+ | We start with 13 red, 15 green, and 17 blue snakes. Show how to achieve a state where all the snakes are the same color, or prove it is impossible. | ||
+ | |style="background-color:rgb(220,230,255);" |[[KGS math club/solution_11_12| solution]] | ||
+ | |||
+ | |- valign="top" | ||
+ | |2011-08-30 | ||
+ | |style="background-color:rgb(220,230,255);" | maproom | ||
+ | |You have three amply large buckets ... (see 2012-10-08 above) | ||
+ | |style="background-color:rgb(220,230,255);" | (see above) | ||
+ | |||
+ | |- valign="top" | ||
+ | |2011-08-30 | ||
+ | |style="background-color:rgb(220,230,255);" | parigi | ||
+ | |Arrange a bridge pack in a 13×4 array such that | ||
+ | |||
+ | (i) each row has one of each rank, | ||
+ | |||
+ | (ii) each row has three or four of each suit, | ||
+ | |||
+ | (iii) each column has one of each suit, and | ||
+ | |||
+ | (iv) each pair of distinct ranks appears together in some column. | ||
+ | |style="background-color:rgb(220,230,255);" |a [[KGS math club/solution_11_10| solution]] by cyryts | ||
+ | |||
+ | |- valign="top" | ||
+ | |2011-07-07 | ||
+ | |style="background-color:rgb(220,230,255);" | maproom | ||
+ | |N dwarfs, who can discuss strategy first, each have an ordered infinity of red and blue hats placed on their heads, colours assigned randomly. They can see each others', but not their own, hats. Each is to specify a hat on their head (e.g. hat number 4) with a single simultaneous guess. Success is group-wise: they succeed iff everyone manages to identify a blue hat on their own head. How well can they do? | ||
+ | |style="background-color:rgb(220,230,255);" |[[KGS math club/solution_11_9| solution]] | ||
+ | |||
+ | |- valign="top" | ||
+ | |2011-05-?? | ||
+ | |style="background-color:rgb(220,230,255);" | maproom | ||
+ | |Label each of two 6-sided dice with a distinct positive integer on each face, so that all 36 sums that can be obtained from a throw of the dice are prime. Choose the 12 numbers so as to minimise their sum. Label each of two 6-sided dice with a distinct positive integer on each face, so that all 36 sums that can be obtained from a throw of the dice are prime. Choose the 12 numbers so as to minimise their sum. | ||
+ | |style="background-color:rgb(220,230,255);" |[[KGS math club/solution_11_7| solution]] by jj | ||
+ | |||
+ | |- valign="top" | ||
+ | |2011-04-24 | ||
+ | |style="background-color:rgb(220,230,255);" | maproom | ||
+ | |The "derived graph" of a given graph is defined as a graph with the same vertices, and an edge joining any two vertices that are two edges but not less apart in the original graph. What are the derived graphs of (i) the pentagon? (ii) the cube? (iii) the icosahedron? | ||
+ | |style="background-color:rgb(220,230,255);" |[[KGS math club/solution_11_8| solution]] | ||
+ | |- valign="top" | ||
+ | |2011-03-20 | ||
+ | |style="background-color:rgb(220,230,255);" | parigi | ||
+ | |A large circular track has only one place where horsemen can pass; many can pass at once there. Is it possible for nine horsemen to gallop around it continuously, all at different constant speeds? | ||
+ | |style="background-color:rgb(220,230,255);" | [[KGS math club/hints_11_5| hint]], [[KGS math club/solution_11_5| solution]], [[KGS math club/solution_11_6| explicit solution]] by iceweasel | ||
+ | |||
+ | |- valign="top" | ||
+ | |2011-03-06 | ||
+ | |style="background-color:rgb(220,230,255);" | iceweasel | ||
+ | |A 52-card deck is shuffled and cards are taken from the top and shown, one by one. You are forced to make a <nowiki>$1</nowiki> bet that "the next card drawn will be black" once before the deck is emptied. Your only freedom is choosing when to make this bet, depending on what you've seen so far. What is the maximum expected gain from your bet? | ||
+ | |style="background-color:rgb(220,230,255);" |[[KGS math club/solution_11_4| solution]] | ||
+ | |||
+ | |- valign="top" | ||
+ | |2011-02-14 | ||
+ | |style="background-color:rgb(220,230,255);" | warfreak2 | ||
+ | | A regular tetrahedron formed from six thin sticks is completely infested with greenfly, which breed rapidly and spread along the sticks at 1mm per second. There are three ladybugs that can walk at up to 1.1 mm per second, eating the greenfly that they pass. How can they exterminate the greenfly? | ||
+ | |style="background-color:rgb(220,230,255);" |[[KGS math club/solution_11_3| solution]] by Swifft | ||
+ | |- valign="top" | ||
+ | |Feb. 2011 | ||
+ | |style="background-color:rgb(220,230,255);" | maproom | ||
+ | | The number of ways to choose k things from n (n>2k) is equal to the number of ways to choose n-k things. Find a general way to pair up the k-member subsets with the (n-k)-member subsets such that each of the former is a subset of its partner. | ||
+ | |style="background-color:rgb(220,230,255);" |[[KGS math club/solution_11_2| solution]] by iceweasel | ||
+ | |||
+ | |- valign="top" | ||
+ | |Jan. 2011 | ||
+ | |style="background-color:rgb(220,230,255);" | maproom | ||
+ | | How many dissimilar ways are there to arrange four points in the plane such that there are only two distinct distances between pairs of the points? | ||
+ | |style="background-color:rgb(220,230,255);" | [[KGS math club/solution_11_1| solution]] by Warfreak2 | ||
+ | |||
+ | |- valign="top" | ||
+ | |late 2010 | ||
+ | |style="background-color:rgb(220,230,255);" | | ||
+ | |Find a set P such that P×P is a proper subset of P. | ||
+ | |style="background-color:rgb(220,230,255);" | [[KGS math club/solution_10_2| solution]] by maproom | ||
+ | |||
+ | |- valign="top" | ||
+ | |11.8.2010 | ||
+ | |style="background-color:rgb(220,230,255);" | ghej | ||
+ | |For the curve x^2 + x y + y^2 = 1, find the tangent that passes through the point (0,2). | ||
+ | |style="background-color:rgb(220,230,255);" | [[KGS math club/solution_10_1| solution ]] | ||
+ | |||
+ | |- valign="top" | ||
+ | |19.8.2009 | ||
+ | |style="background-color:rgb(220,230,255);" | royu | ||
+ | | You have the set {9, 99, 999, ...}. Show that given any natural number n not divisible by 2 or 5, n divides at least one element of the set. | ||
+ | |style="background-color:rgb(220,230,255);" | [[KGS math club/hints_9_1| hint ]] [[KGS math club/solution_9_1| solution ]] | ||
+ | |||
+ | |- valign="top" | ||
+ | | 19.8.2009 | ||
+ | |style="background-color:rgb(220,230,255);" | bourbaki | ||
+ | | Suppose A and B are n x n matrices with real entries such that either A or B commutes with C = AB - BA. Prove that C is nilpotent, i.e. C^k = 0 for some integer k | ||
+ | |style="background-color:rgb(220,230,255);" | [[KGS math club/solution_8_1| solution ]] | ||
+ | |||
+ | |- valign="top" | ||
+ | | 18.7.2009 | ||
+ | |style="background-color:rgb(220,230,255);" | taoyan | ||
+ | | How many times do the clock hands (hour and minute) overlap between 11:59:59 before lunch and 00:00:01 at night? | ||
+ | |style="background-color:rgb(220,230,255);" | [[KGS math club/solution_7_1| solution ]] | ||
+ | |||
+ | |- valign="top" | ||
+ | | 27.7.2008 | ||
+ | |style="background-color:rgb(220,230,255);" | royu StoneTiger | ||
+ | | You have a collection of 11 balls with the property that if you remove any one of the balls, the other 10 can be split into two groups of 5 so that each weighs the same. If you assume that all of the balls have rational weight, there is a cute proof that they all must weigh the same. Can you find a proof? Can you find a way to extend the result to the general case where the balls have real weights? | ||
+ | |style="background-color:rgb(220,230,255);" | [[KGS math club/solution_6_1| solution ]] | ||
|- valign="top" | |- valign="top" | ||
− | | | + | |6.7.2008 |
|style="background-color:rgb(220,230,255);" | amkach | |style="background-color:rgb(220,230,255);" | amkach | ||
− | | | + | |Prove or disprove: If P(x) is a polynomial (with non-zero degree) of one real variable and a and b satisfy <math>P^{(n)}(a) = P^{(n)}(b)</math> for all integers n > 0 (i.e., <math>P(a) = P(b), P'(a) = P'(b), P''(a) = P''(b)</math>, etc.), then a = b |
− | |style="background-color:rgb(220,230,255);" | [[KGS math club/ | + | |style="background-color:rgb(220,230,255);" | [[KGS math club/solution_5_1| solution ]] |
+ | |||
+ | |- valign="top" | ||
+ | |1.7.2008 | ||
+ | |style="background-color:rgb(220,230,255);" | quimey | ||
+ | |Assume <math>m</math> and <math>n</math> are integers and can be expressed as sum of <math>2</math> squares (i.e, exists <math>a,b,c,d</math> integers with <math>m=a^2+b^2, n=c^2+d^2)</math>. Show <math>m*n</math> can be written as sum of <math>2</math> squares. And the same but with <math>4</math> squares. | ||
+ | |style="background-color:rgb(220,230,255);" | [[KGS math club/solution_4_1| solution ]] | ||
|- valign="top" | |- valign="top" | ||
|30.6.2008 | |30.6.2008 | ||
|style="background-color:rgb(220,230,255);" | amkach | |style="background-color:rgb(220,230,255);" | amkach | ||
− | |For n > | + | |For <math>n \geq 2</math>, consider the <math>n-</math>dimensional hypercube with side length <math>4</math> centered at the origin of <math>n-</math>space. Place inside of it <math>2^n</math> <math>n-</math>dimensional hyperspheres of radius <math>1</math>, centered at each of the points <math>(\pm1, \pm1, ..., \pm1)</math>. These hyperspheres are tangent to the hypercube and to each other. |
− | Then place an n-dimensional hypersphere, centered at the origin, of size so that it is tangent to each of the 2^n hyperspheres of radius 1. In which dimensions n is this central hypersphere contained within the hypercube? | + | Then place an <math>n-</math>dimensional hypersphere, centered at the origin, of size so that it is tangent to each of the <math>2^n</math> hyperspheres of radius <math>1</math>. In which dimensions <math>n</math> is this central hypersphere contained within the hypercube? |
|style="background-color:rgb(220,230,255);" | [[KGS math club/solution_3_1| solution ]] | |style="background-color:rgb(220,230,255);" | [[KGS math club/solution_3_1| solution ]] | ||
+ | |||
+ | |||
|- valign="top" | |- valign="top" | ||
− | | | + | |20.2.2007 |
− | |style="background-color:rgb(220,230,255);" | | + | |style="background-color:rgb(220,230,255);" | StoneTiger |
− | | | + | |Does any member of the sequence <math>1, 4, 20, 80, ...</math> generated by <cmath>x(n) = 6x(n-1) - 12x(n-2) + 8x(n-3)</cmath> ever have a factor in common with <math>2007</math>? |
− | |style="background-color:rgb(220,230,255);" | [[KGS math club/ | + | |style="background-color:rgb(220,230,255);" | [[KGS math club/solution_2_1|sigmundur]] |
− | |||
|- valign="top" | |- valign="top" | ||
− | | | + | |21.6.2008 |
− | |style="background-color:rgb(220,230,255);" | | + | |style="background-color:rgb(220,230,255);" | amkach |
− | | | + | |Consider the two player game that begins with an even length sequence of positive integers. Each player, in turn, removes either the first or last of the remaining integers, ending when all the integers have been removed. A player's score is the sum of the integers that they removed; the winner is the player with the higher score (with a tie if equal scores). Show that Player One has a non-losing strategy, i.e., can always force a tie or a win. |
− | |style="background-color:rgb(220,230,255);" | [[KGS math club/ | + | |style="background-color:rgb(220,230,255);" | [[KGS math club/hints_1_1|hints]] [[KGS math club/solution_1_1|solution]] [[KGS math club/solution_1_2|solution2]] |
− | |||
− | |||
|} | |} |
Latest revision as of 15:17, 18 July 2017
A group of people on Kiseido Go Server Mathematics room.
The meaning of this page is to collect the problems posed there and save hints and solution suggestions. In order to write something, I'm afraid you need to register to the AoPS wiki first. After that you're good to go.
Adding problems should be quite straightforward with the copy-paste template in the wiki source. Please add <math>-tags (or dollar signs, it seems) where required, e.g. . Still, if you don't, somebody else will; all additions are appreciated.
Added | Author | Problem | Solutions
|
---|---|---|---|
2016-12-04 | Warfreak2 | The card game Parade has a deck of 66 cards, containing each pair of colour and rank, where there are 6 colours and 11 ranks (0 to 10). A parade is a sequence of cards played one by one; each time a card is played at the end of the sequence, count that number back, and from there to the start, delete any card of the same colour, or of a less-than-or-equal rank. What is the greatest possible length a parade can reach? | |
2016-12-04 | maproom | You are driving, in mild dry weather, along a straight road at a steady 70 m.p.h. A police car approaches in the opposite direction with its siren on. As you pass, you hear the pitch of the siren drop by a perfect fifth. What is the speed of the police car? | |
2016-05-07 | parigi | With all numbers written in base 10: prove that any integer ending in 7 has a multiple consisting entirely of a string of 1s. | solution by Warfreak2 |
2016-05-05 | maproom | Devise a set of denominations, as few as possible, such that any integer value from 1 to 100 cents can be paid with no more than two coins. | solution by zwim |
2015 | njs | We fill in a 3x3 square with non-negative integers such that the sum of the numbers in each row and column equals n. Show that the number of such squares is (n+2 choose 2)^2 - 3 * (n+3 choose 4). | |
2015 | twillo | For which n can the complete graph K_n have its set of edges partitioned to form edge-disjoint Hamiltonian circuits or Hamitonian paths? | |
2014-09-21 | njs | Dissect a regular hexagon into three pieces which can be rearranged to form an equlateral triangle. | |
2014-09-10 | ndkrempel | A chess piece, the prince, can move one square south or one square east or one square diagonally north-west. For what sizes of rectangular board can it do a Hamiltonian circuit of the board, visiting each square once and ending up where it started? | solution by gu1729 |
2014-06-12 | twillo | Topological puzzle: you have a thick rope, and lots of rubber bands each too small to go round the rope. Can you make a structure from the bands, and put it over the end of the rope, such that it cannot be removed by someone without access to an end of the rope? | |
2014-05-30 | twillo | For which natural numbers n is it possible to take the integers 1..n and pair them up so that the sum of each pair is a perfect square? | solution by gu1729 |
2013? | twillo | K_10 is a set of 10 points, with each pair of them joined by a single edge. Colour these edges so that as many as possible of the 3-points subsets are joined by two blue and one red edge. | |
2013? | sume | An undirected graph has each vertex connected to no more than five other vertices. Show that it is always possible to color the vertices black and white in such a way that no vertex is connected to more than two vertices of the same color as itself; or provide a counterexample. | |
2013-10-08 | maproom | A point is doing Brownian motion in the plane. It is now at (x=1, y=1). With probability 1, it will reach the line (y=0). When it next does, what is the probabilty that its x value will be positive? | solution by cyndane |
2013-09-22 | maproom | A room contains 100 boxes numbered 1..100, each containing a distinct randomly-selected prisnoer's name. The 100 prisoners will each in turn be admitted to the room and allowed to examine the contents of up to 50 boxes, but to change nothing. They may plan their strategy in advance, but may not communicate once a box has been opened. Iff every prisoner finds his own name, they will all be released. What is the best success rate thay can achieve? | |
2013-07-22 | maproom | There is a lottery. You hold one ticket, eight others have been sold. A tenth and final ticket is now up for sale. Then four prizes, of €10, €5, €2, €1, will be issued, as follows. A random ticket will be chosen, and its holder given the biggest remaining prize and all his tickets cancelled, until the prizes have all been distributed. What is the most you should be willing to pay for the tenth ticket? | solution by zwim |
2013-04-? | parigi | There has been a murder. Two sheriffs have each independently reduced the publicly-known list of eight suspects to two. Using an open communication channel, how can they (1) check whether their length-two lists differ; and if they do, (2) let each other know who the murderer is? They must not let the listeners to the channel (who can break public-key encryption) know who the murderer is. | solution by YogSothoth |
2013-04-? | maproom | Can you dissect a disk into congruent connected pieces in such a way that more than one, but not all, of the pieces have the disk's centre on their border? | solution by Leira |
2012-10-? | parigi | Can you arrange ten points in the plane in such a way that they cannot be covered by a set of non-overlapping unit disks? | solution by zwim |
2012-10-08 | Niall | Four point frogs initially form a square in the plane. Any frog can jump over any other frog in such a way that the other frog forms the midpoint of its jump. Can the frogs ever form a larger square? Can any three of them ever be colinear? | solution by gu1729 |
2012-10-08 | maproom | You have three amply large buckets, each containing a known number of pebbles. You are allowed, as often as you like, to choose two buckets and to move from the first to the second as many pebbles as were previously in the second. You must always choose them so that there are enough pebbles in the first. Show that, for all sets of starting numbers, you can eventually obtain an empty bucket. | solution by YogSothoth |
2012-08-02 | Warfreak2 | Without reference to any external material, prove that the side:diagonal ratio of a regular pentagon is 2 : 1+√5. | solution by flyingdario |
2012-08-02 | maproom | Find a set of sets of natural numbers such that the sum of all the numbers is 20 and their product is as great as possible.
(This is a trick question. This trick is in understanding the properties of sets.) |
solution by weiqidevil |
2012-06 | maproom | A, B and C have a cycle race from E to F. All three set out at 10am at different speeds from E. A is 5km/h faster than B and 10km/h faster than C. They all maintain a constant speed over the course except as follows. Also travelling the same route at a constant speed is a burger van. Any cyclist reaching the van immediately loses a constant 20km/h in speed. The van leaves E at 9am and arrives in F at 3pm; the race itself is a three-way tie. When does it finish? | solution by DanielTom |
2012-03-05 | maproom | 31 points are equally spaced in a circle. In how many distinct ways can you pick 6 of them such that every pair of picked points is at a different separation? | solution by iceweasel |
2012-01-20 | twillo | You have 64 coins heads up and 36 coins tails up - you have to split them into 2 piles with equal numbers of heads in each. You are permitted to turn coins over but can never tell what state they are in. | solution by YogSothoth |
2012-01-25 | maproom | Find a permutation group G acting transitively on N letters, and a permutation group H also acting transitively on N letters, such that G and H are isomorphic, but no isomorphism between them corresponds to any mapping of the two sets of letters. | solution by D239500800 |
2012-01-20 | twillo | An odd number of points are arranged in the plane with no three colinear. Prove that for each of these points, the number of triangles (whose vertices are others of the points) within which it lies is even. | solution by Warfreak2 |
2011-11-21 | maproom | You deal a standard bridge pack to four players in the usual way. Which is more likely, and by roughly how much:
(a) You have cards in only two suits, or (b) There is some suit in which both you and your partner have no cards? |
solution by Zahlman |
2011-11-08 | Niall | An island has 3 colours of snake: red, blue and green. When snakes of different colors meet they both turn into the third color. They never breed or die.
We start with 13 red, 15 green, and 17 blue snakes. Show how to achieve a state where all the snakes are the same color, or prove it is impossible. |
solution |
2011-08-30 | maproom | You have three amply large buckets ... (see 2012-10-08 above) | (see above) |
2011-08-30 | parigi | Arrange a bridge pack in a 13×4 array such that
(i) each row has one of each rank, (ii) each row has three or four of each suit, (iii) each column has one of each suit, and (iv) each pair of distinct ranks appears together in some column. |
a solution by cyryts |
2011-07-07 | maproom | N dwarfs, who can discuss strategy first, each have an ordered infinity of red and blue hats placed on their heads, colours assigned randomly. They can see each others', but not their own, hats. Each is to specify a hat on their head (e.g. hat number 4) with a single simultaneous guess. Success is group-wise: they succeed iff everyone manages to identify a blue hat on their own head. How well can they do? | solution |
2011-05-?? | maproom | Label each of two 6-sided dice with a distinct positive integer on each face, so that all 36 sums that can be obtained from a throw of the dice are prime. Choose the 12 numbers so as to minimise their sum. Label each of two 6-sided dice with a distinct positive integer on each face, so that all 36 sums that can be obtained from a throw of the dice are prime. Choose the 12 numbers so as to minimise their sum. | solution by jj |
2011-04-24 | maproom | The "derived graph" of a given graph is defined as a graph with the same vertices, and an edge joining any two vertices that are two edges but not less apart in the original graph. What are the derived graphs of (i) the pentagon? (ii) the cube? (iii) the icosahedron? | solution |
2011-03-20 | parigi | A large circular track has only one place where horsemen can pass; many can pass at once there. Is it possible for nine horsemen to gallop around it continuously, all at different constant speeds? | hint, solution, explicit solution by iceweasel |
2011-03-06 | iceweasel | A 52-card deck is shuffled and cards are taken from the top and shown, one by one. You are forced to make a $1 bet that "the next card drawn will be black" once before the deck is emptied. Your only freedom is choosing when to make this bet, depending on what you've seen so far. What is the maximum expected gain from your bet? | solution |
2011-02-14 | warfreak2 | A regular tetrahedron formed from six thin sticks is completely infested with greenfly, which breed rapidly and spread along the sticks at 1mm per second. There are three ladybugs that can walk at up to 1.1 mm per second, eating the greenfly that they pass. How can they exterminate the greenfly? | solution by Swifft |
Feb. 2011 | maproom | The number of ways to choose k things from n (n>2k) is equal to the number of ways to choose n-k things. Find a general way to pair up the k-member subsets with the (n-k)-member subsets such that each of the former is a subset of its partner. | solution by iceweasel |
Jan. 2011 | maproom | How many dissimilar ways are there to arrange four points in the plane such that there are only two distinct distances between pairs of the points? | solution by Warfreak2 |
late 2010 | Find a set P such that P×P is a proper subset of P. | solution by maproom | |
11.8.2010 | ghej | For the curve x^2 + x y + y^2 = 1, find the tangent that passes through the point (0,2). | solution |
19.8.2009 | royu | You have the set {9, 99, 999, ...}. Show that given any natural number n not divisible by 2 or 5, n divides at least one element of the set. | hint solution |
19.8.2009 | bourbaki | Suppose A and B are n x n matrices with real entries such that either A or B commutes with C = AB - BA. Prove that C is nilpotent, i.e. C^k = 0 for some integer k | solution |
18.7.2009 | taoyan | How many times do the clock hands (hour and minute) overlap between 11:59:59 before lunch and 00:00:01 at night? | solution |
27.7.2008 | royu StoneTiger | You have a collection of 11 balls with the property that if you remove any one of the balls, the other 10 can be split into two groups of 5 so that each weighs the same. If you assume that all of the balls have rational weight, there is a cute proof that they all must weigh the same. Can you find a proof? Can you find a way to extend the result to the general case where the balls have real weights? | solution |
6.7.2008 | amkach | Prove or disprove: If P(x) is a polynomial (with non-zero degree) of one real variable and a and b satisfy ![]() ![]() |
solution |
1.7.2008 | quimey | Assume ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() |
solution |
30.6.2008 | amkach | For ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() Then place an |
solution
|
20.2.2007 | StoneTiger | Does any member of the sequence ![]() ![]() ![]() |
sigmundur
|
21.6.2008 | amkach | Consider the two player game that begins with an even length sequence of positive integers. Each player, in turn, removes either the first or last of the remaining integers, ending when all the integers have been removed. A player's score is the sum of the integers that they removed; the winner is the player with the higher score (with a tie if equal scores). Show that Player One has a non-losing strategy, i.e., can always force a tie or a win. | hints solution solution2 |