## How would you rate the difficulty of this problem?

Post any maths and/or physics related questions here.

Moderators: Darobat, RecursiveS, Dante Shamest, Bugdude, Wizard

## How would you rate the difficulty of this problem?

Easy
4
27%
Intermediate
6
40%
Hard
5
33%

### How would you rate the difficulty of this problem?

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.

Alvaro
Moderator

Posts: 5185
Joined: Mon Sep 22, 2003 4:57 pm
Location: NY, USA

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

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.
If it wasn't for C, we would be using BASI, PASAL and OBOL.

tomcant

Posts: 3101
Joined: Tue Sep 23, 2003 1:56 am
Location: Colchester, UK

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

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

Is that more than one or only one?
If it wasn't for C, we would be using BASI, PASAL and OBOL.

tomcant

Posts: 3101
Joined: Tue Sep 23, 2003 1:56 am
Location: Colchester, UK

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.
Guest

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

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

Is that more than one or only one?

That is "at least one".

Alvaro
Moderator

Posts: 5185
Joined: Mon Sep 22, 2003 4:57 pm
Location: NY, USA

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 .
Togra

Posts: 188
Joined: Wed Jul 28, 2004 8:51 am
Location: NL

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.

Alvaro
Moderator

Posts: 5185
Joined: Mon Sep 22, 2003 4:57 pm
Location: NY, USA

This brings up another good point: Should we just have people provide examples or actually prove it (i.e. by induction or other methods).
"Given enough time, man can do anything with a bit of string and some Tinker toys." Bruce Bolden, Senior Instructor at the University of Idaho.

leas5040

Posts: 1214
Joined: Mon Apr 12, 2004 9:51 pm
Location: Moscow, ID

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

RecursiveS

Posts: 1236
Joined: Thu Sep 18, 2003 8:33 am
Location: Dorset, UK

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

Beer Hunter

Posts: 912
Joined: Sat Dec 13, 2003 7:12 pm
Location: Australia

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...

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

GeekDog

Posts: 1160
Joined: Sun Sep 28, 2003 1:42 pm
Location: UK

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 - 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 ?
Togra

Posts: 188
Joined: Wed Jul 28, 2004 8:51 am
Location: NL

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.

Alvaro
Moderator

Posts: 5185
Joined: Mon Sep 22, 2003 4:57 pm
Location: NY, USA

Alvaro: Could you give me an idea of a really hard question, I just want to get a taster.
If it wasn't for C, we would be using BASI, PASAL and OBOL.

tomcant

Posts: 3101
Joined: Tue Sep 23, 2003 1:56 am
Location: Colchester, UK

Next