C++ Home

by **Alvaro** » Mon Sep 20, 2004 1:02 pm

Just to get an idea of what people consider easy and hard, give this problem some thought and tell us how difficult you found it.

Given n+1 natural numbers, none of which is larger than 2n, prove that one of them divides another.

by **Guest** » Mon Sep 20, 2004 1:07 pm

I think the fourth options is missing.
option 4
"I have no idea what you just said?"

by **tomcant** » Mon Sep 20, 2004 1:09 pm

Anonymous wrote:I think the fourth options is missing.
option 4
"I have no idea what you just said?"

Put 'Hard' then.

As for me: I think I could do it if I gave it some thought.

by **tomcant** » Mon Sep 20, 2004 1:14 pm

Alvaro wrote:... prove that one of them divides another.

Is that more than one or only one?

by **Guest** » Mon Sep 20, 2004 2:08 pm

tomcant wrote:
Anonymous wrote:I think the fourth options is missing.
option 4
"I have no idea what you just said?"

Put 'Hard' then.

As for me: I think I could do it if I gave it some thought.

My vote is cast for hard.

by **Alvaro** » Mon Sep 20, 2004 2:48 pm

tomcant wrote:
Alvaro wrote:... prove that one of them divides another.

Is that more than one or only one?

That is "at least one".

by **Togra** » Mon Sep 20, 2004 3:22 pm

This little problem seems doable at first sight. I have some ideas, no tight proof yet, so perhaps my early vote for 'easy' should be reconsidered to 'intermediate'.

Anyway, I'm curious Alvaro: does this have something to do with the Math-Contest idea? If so, we should be careful using the word 'prove' - it would definitely scare people away

.

by **Alvaro** » Mon Sep 20, 2004 3:29 pm

Togra wrote:This little problem seems doable at first sight. I have some ideas, no tight proof yet, so perhaps my early vote for 'easy' should be reconsidered to 'intermediate'.

Anyway, I'm curious Alvaro: does this have something to do with the Math-Contest idea? If so, we should be careful using the word 'prove' - it would definitely scare people away .

Do you suggest we use "show" instead?

Yes, this has to do with the contest idea. I participated in the International Math Olympiad, and I can probably come up with some ideas for problems, but I am afraid the range in levels in this site is too wide. I think the problem is easy, but that's mostly because I have seen many problems that are much, much harder. For the average highschool student, this is probably a hard problem. I am trying to find what level people are comfortable with.

by **leas5040** » Mon Sep 20, 2004 4:19 pm

This brings up another good point: Should we just have people provide examples or actually prove it (i.e. by induction or other methods).

by **RecursiveS** » Mon Sep 20, 2004 4:46 pm

On a site like this you have to roll with the punches...

If you want to run a contest - run it! If it's too hard, nobody will enter.

I question the idea of testing people first though...

As you say, "you are trying to find a level that people are comfortable at",
why not just post whatever contest you have in mind and see what happens ?

0 entries == make it easier
1000 entries == make it more difficult

by **Beer Hunter** » Tue Sep 21, 2004 1:06 am

EDIT: Incorrect argument removed. Please disregard my vote for 'easy' and consider there to be another one for 'intermediate'. :)

by **GeekDog** » Tue Sep 21, 2004 2:33 am

leas5040 wrote:This brings up another good point: Should we just have people provide examples or actually prove it (i.e. by induction or other methods).

Providing an example proves nothing, unfortunately, because it doesn't prove that there are no counter-examples. This leads into another problem, which is that very few people know how to construct a mathematical proof properly (even when they know the answer). I certainly don't, and i have a degree in theoretical physics... :roll:

I don't know what a "natural number" is either, which isn't helping me with this problem! I'm guessing it's a positive integer...

The problem seems doable given some time, but it doesn't seem easy or programmable

by **Togra** » Tue Sep 21, 2004 6:11 am

GeekDog wrote:Providing an example proves nothing, unfortunately, because it doesn't prove that there are no counter-examples.

That would be a nice contest format: "Find the counterexample of ... (some conjecture)".

GeekDog wrote:I don't know what a "natural number" is either, which isn't helping me with this problem! I'm guessing it's a positive integer...

You guessed right: ints in the range [1,2n], bounds included.

@problem / vote
My initial vote for 'easy' was far too optimistic :oops:

- I now consider this little problem to be hard. Just spent nearly an hour trying stuff, it lead me to believe the proof must be about prime-density estimations... that's out of my league. Should the proof go that way, Alvaro? You did work it out, didn't you

?

by **Alvaro** » Tue Sep 21, 2004 7:12 am

Togra wrote:@problem / vote
My initial vote for 'easy' was far too optimistic - I now consider this little problem to be hard. Just spent nearly an hour trying stuff, it lead me to believe the proof must be about prime-density estimations... that's out of my league. Should the proof go that way, Alvaro? You did work it out, didn't you ?

No, it has nothing to do with prime density.

Pigeonhole principle: If n+1 pigeons are put into n pigeonholes, there's a hole with more than one pigeon.

Consider the right "pigeonholes" and the problem will be solved.

by **tomcant** » Tue Sep 21, 2004 9:59 am

Alvaro: Could you give me an idea of a really hard question, I just want to get a taster.

C++ Home

How would you rate the difficulty of this problem?

How would you rate the difficulty of this problem?

How would you rate the difficulty of this problem?

Re: How would you rate the difficulty of this problem?

Re: How would you rate the difficulty of this problem?

Who is online