wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> hard >> Covering a Table with Quarters & other problems
        
(Message started by: pjay on Dec 1^st, 2003, 2:50pm)

Title: Covering a Table with Quarters & other problems
Post by pjay on Dec 1^st, 2003, 2:50pm

1) there are 25 objects with integer weights from 1-25. You are now allowed 3 weights to buy from the store and a scale to put the 25 objects in order from lightest to heaviest. If we assume that you are only allowed comparisons between any combination of the 3 weights and one of the objects (i.e. no comparisons between 2 of the 25 objects) what is one possibility
of the 3 weights?

2)you are in a circular pool with a bear at the edge. You run faster than the bear but it runs 4x as fast as you can swim. If you start from the center of the pool show how you can get to the edge and escape. Assume that once you get to the edge you can run immediately. Also assume that
the bear always runs in a direction which minimizes its distance from you.

3) There are 100 men getting onto a plane. The first man
decides to sit wherever he wants with equal probability 1/100. All other passengers sit where they are supposed to if they can, otherwise they choose a seat with prob 1/n with n seats left. What is the probability that the last man sits in his own seat?

4) what is the probability that 3 points randomly chosen on a circle (uniformly) lie on a half circle?

5) 100 men on an island with red dots on their foreheads. If one finds out he has a red dot on his forehead then he wakes up dead the next morning. They are not allowed to talk and there are no mirrors on the island. They are given only the information that at least one of them has a red dot, and they are allowed to look at other people. How long before someone dies?

6)integrate 1/x by parts: \int 1/x dx=\int x/x^2 dx
= -(x/x)-\int -(1/x)dx cancel \int 1/x dx from both sides to get 0=-1

7) 1000 lightbulbs in a row. a man goes thru and toggles the switch on each one so that they are now on. Next he goes thru and toggles every other one so that 2,4,6,... are now off. Goes through again and toggles every third, fourth, etc. Which ones are still on at the end of the process?

8) related to number 7: What is the smallest number with exactly 7 factors?

9) There are 100 nonoverlapping quarters placed on table in such a way that if you place another one, it will overlap with one of the quarters place already (a quarter is on the table if its center is on the table). Prove in a couple sentences that the table can be completely covered with 400 quarters (i.e. you wont be able to see the surface of the table).

10) prove that there are an infinite number of prime numbers

11) a man walks up a hill starting at 6am and is at the top by 6pm. He spends the night and walks down the hill the next day starting at 6am and is at the bottom by 6pm. Show that there was a time of day at which he was at the same height on both days

12) related to 11: Assume the earth is a perfect sphere. Show that atany given time there exists two antipodal points with the same temperature.

13) another handshake problem: there are n people at a party. Assumng noone can shake hands with himself/herself, show that at least 2 people shook the same number of hands (one can only shake hands with another at most once).

14) you have a 10x10 grid. starting from the bottom left you try to go to the top right. how many paths are there that minimize the distance?

Title: Re: some new problems (some easy and some hard)
Post by towr on Dec 1^st, 2003, 3:02pm

many of these are allready on the site.. (in different version)
like 2 (cat and a duck),3,4,5 (red eyed monks), 7, 8, probably 10 (though we have before missed some good oldies), 12, and probably 13 as well

Title: Re: some new problems (some easy and some hard)
Post by Icarus on Dec 1^st, 2003, 5:29pm

2) The Duck in the Pond (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_hard;action=display;num=1028614054)

3) Insane Passenger (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_easy;action=display;num=1067088849) Note that "visitor"'s half-hidden answer has not had a justification published (though it is correct).

4) Points On a Semicircle (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_medium;action=display;num=1060593301)

5) Brown Eyes and Red Eyes (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_medium;action=display;num=1027806383). A classic.

7) Circular Jail Cell (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_hard;action=display;num=1027864221)

[smiley=8.gif]) Seven Factors (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_easy;action=display;num=1068776620)

10) If this one is on the site, I don't remember it, but since it is a simple argument available in any introduction to number theory text, I'll just reproduce it here:[hide] Suppose there were only a finite number of primes. Take their product and add 1. This gives a number not divisable by any prime, which cannot be. Hence the number of primes must be infinite.[/hide]

11) I'm not sure if this particular situation is on the site yet or not. It may be that what towr is recalling is some of the discussion of the temperature problem (12) - the same solution method works for both. An application of a basic analysis result solves them.

12) Temperature Antipodes (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_hard;action=display;num=1068776299)

13) Party Handshakes (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_medium;action=display;num=1028483138)

14) I'm not sure if this one has appeared in this guise. However, the problem is equivalent to the question: How many 11-tuples (a₀, ..., a₁₀) of non-negative integers are there whose sum is 10?

Are you sure of your wording on (1)? I don't see how you can completely distinguish the object weights if you are only allowed comparisons between 1 object and 1 reference weight at a time. Each measurement can divide the weights into 3 classes. Those lighter than the reference weight, those heavier than the reference weight, and the possible single one equal to the reference weight. Start with the middle reference weight. One of its subclasses must have at least 12 possible values. Assume WLOG, that it is the objects weighing less than the middle reference. The higher reference weight will give the same responce for all 12 objects in that class. The smaller reference weight will divide the 12 objects into 3 subclasses, one of which must have 6 members. Thus there are at least 6 objects that give identical results when compared to the three reference weights. (In fact there are more than 6.)

Now if you were allowed to put more than one object or reference weight in the pans at a time...

A restatement of 6, to make it easier to follow:

[int] 1/x dx = [int] x/x² dx
   = [int] x d(-1/x)
   = -x/x - [int] -1/x dx
   = -1 + [int] 1/x dx.

Cancel [int] 1/x dx to yield 0 = -1.

That's a good one that should leave any calculus novice scratching their heads. One hopes that the initiates can spot the problem however! Thanks for posting it.

Since I've commented on everything else, I might as well throw in (9). This one appears to me to justify a "hard" designation (though I may just be missing something). So far all I have is that the table area cannot be more than 225 times the area of a quarter (actually less, but I haven't tried to refine the estimate). This alone does not show that 400 coins is sufficient, since much of the area covered is redundantly covered by other quarters.

Title: Re: some new problems (some easy and some hard)
Post by aero_guy on Dec 1^st, 2003, 7:57pm

It seems that number 6 is actually quite easy when you take into account [hide]constants from integrating indefinite integrals[/hide].

I think I may have something for nine:
[hide]Suppose the coins are laid out in a regular grid format such that a new coin just barely could not fit in the middle of them. In this form it can be shown that five more coins will cover all the open area between the coins if they are places in the center, and directly between any two adjacent coins.

We can show that for this arrangement the needed coins to cover the area within an nxm grid of these coins is 3mn-2(m+n)+1. Now we need to include the number of coins you will need to take care of the edges between these coins and the edge. This will require another 4(m+n) coins. Together that is 3mn+2(m+n)+1. As mn is just equal to the number of coins we started with (N), we need 3N+2(m+n)+1. This is obviously at a max when it is a single long string of coins. For the case of n=100 and m=1 we need 503 coins, more than was suggested.

This must mean they are making some sort of assumption as to the shape of the table. I was using a rectangular table above. If we force it to be square, then we have 3N+4[sqrt]N+1. With N=100 we need 341 coins to cover it.

This strategy makes two major assumptions:
1) The table is square. I have no idea if it is, but I have shown that for some other shapes 400 will not be enough coins.

2) The regular pattern of spacing I started with requires more coins to cover up than any other. No clue if this is true.

There is probably a much more elegant way to solve this.[/hide]

Title: Re: some new problems (some easy and some hard)
Post by towr on Dec 2^nd, 2003, 12:09am

on 12/01/03 at 17:29:21, Icarus wrote:

11) I'm not sure if this particular situation is on the site yet or not. It may be that what towr is recalling is some of the discussion of the temperature problem (12) - the same solution method works for both. An application of a basic analysis result solves them.

I hadn't added this one in my list ::) So I wasn't recalling anything about it

Quote:

14) I'm not sure if this one has appeared in this guise. However, the problem is equivalent to the question: How many 10-tuples (a₁, ..., a₁₀) of non-negative integers are there whose sum is 10?

This is a subcase of a problem Dudidu posted a couple of days ago..
I'm not sure what you're trying to do with that 10-tuple though..
Actually I'm not even sure if we're going from (0,0) to (10,10) (along grid-lines) or from (1,1) to (10,10) (over grid-squares). In the former case I'd say an 11-tuple that adds to 10 would work [hide]giving C(10+(11-1),10)[/hide], and in the latter a 10-tuple that add to 9 [hide]giving C(9+(10-1),9)[/hide]..

Title: rewording #1
Post by pjay on Dec 2^nd, 2003, 9:43am

you are allowed to use more than one of the three weights at a time, but you are not allowed to put more than one of the 25 weights on at any given time.

Title: Re: rewording #1
Post by BNC on Dec 2^nd, 2003, 2:11pm

on 12/02/03 at 09:43:33, pjay wrote:

you are allowed to use more than one of the three weights at a time, but you are not allowed to put more than one of the 25 weights on at any given time.

I'd say you can order 27 weights, using ::[hide]2, 6 and 18[/hide]::.

Title: Re: some new problems (some easy and some hard)
Post by pjay on Dec 2^nd, 2003, 7:48pm

bnc, yes the max is indeed 27, but this gives some hint as to the method so i left it at 25.

Title: Re: some new problems (some easy and some hard)
Post by pjay on Dec 2^nd, 2003, 7:52pm

aero_guy, the table is an arbitrary rectangle, and yes it can be done with 400 quarters. i would argue that you your 503 coins is not really a proof that it takes more than 400 but just a description of one way in which the table can be covered with quarters. one assumption you shouldnt make is that the original 100 coins cannot be moved, however even in the case where you leave the original quarters static, your argument is not really a proof (i agree it is intuitively obvious that your description is the best way to cover the table in that instance, but still it is not a proof that it is optimal covering). what i am looking for here is a two sentence proof that the table can be covered with 400 quarters.

Title: Re: some new problems (some easy and some hard)
Post by aero_guy on Dec 3^rd, 2003, 6:55am

Oh!, you can move the quarters! That makes it a lot easier.

Title: Re: some new problems (some easy and some hard)
Post by Barukh on Dec 3^rd, 2003, 10:54pm

Here’s my try on (9):
[smiley=blacksquare.gif][hide]
Let the radius of the coin be R. Take any coin, and at its center draw a circle with radius 2R. It’s clear that at least one coin overlaps with the ring bounded by that circle and the coin. The area of this ring is 3[pi]R², therefore the uncovered area is less than 300[pi]R². Then, the area of the table is less than 400[pi]R², and may be covered by 400 coins.
[smiley=blacksquare.gif][/hide]

Hmm, it’s more than 2 sentences… Nevermind, very nice tiny problem, pjay!

Title: Re: some new problems (some easy and some hard)
Post by Icarus on Dec 4^th, 2003, 6:20am

It not only is more than 2 sentences, it also does not work. If I gave you a table whose area is 400 times the area of a coin, you will not be able to totally cover it with 400 coins. Since the coins are round, they do not tile, and so must overlap. This seriously reduces the amount of coverage they can provide.

This suggests a related question that I am going to post in a separate thread, to avoid muddying the waters here.

Title: coins covering the table
Post by pjay on Dec 4^th, 2003, 8:54am

i agree with icarus in that baruhk's solution does not work; however i think it my be too harsh to say that the answer was too long. Certainly, the wording could have been changed to fit into 2 sentences...

Title: Re: some new problems (some easy and some hard)
Post by Barukh on Dec 4^th, 2003, 8:55am

Icarus, you are right... I just was blinded by the simplicity of the argument >:(

Title: Re: some new problems (some easy and some hard)
Post by Icarus on Dec 4^th, 2003, 4:34pm

on 12/02/03 at 00:09:11, towr wrote:

I'm not sure what you're trying to do with that 10-tuple though...

Caught in another simple error! :-[ I've corrected it.

Title: Re: some new problems (some easy and some hard)
Post by SWF on Dec 11^th, 2003, 5:16pm

Solution to 9) [hide]Since each point on the table is within 1 quarter diameter of the center of some quarter, doubling the size of each of the 100 quarters will cover the table. Tile four replicas of this covered rectangle, and shrink by a factor of 2 to get 400 quarters of normal size covering the table[/hide].

By the way, it is common practice here to post one riddle per thread, preferred (but not common) to check if a riddle is already here before posting it, and suggested to use meaningful titles and not to say "new" (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_easy;action=display;num=1036468244) in the thread title. I enjoyed the riddle number 9), but without a good title and being mixed in with other repeats, it will be difficult for someone to easily find it in the future.

Title: Re: some new problems (some easy and some hard)
Post by pjay on Dec 11^th, 2003, 7:16pm

SWF good job on #9. Thanks for the tips. This was my first post, so I had no idea what I was doing. Anyways, I've since figured out how things work.

Title: Re: Covering a Table with Quarters & other problem
Post by Icarus on Dec 12^th, 2003, 6:31pm

I changed the thread title to indicate the covering with quarters riddle, since that is the most challenging original problem here.