My Math Forum  

Go Back   My Math Forum > Math Forums > Math Events

Math Events Math Events, Competitions, Meetups - Local, Regional, State, National, International


Reply
 
LinkBack Thread Tools Display Modes
August 7th, 2009, 08:48 PM   #1
Senior Member
 
Joined: Apr 2007

Posts: 2,140
Thanks: 0

International Mathematical Olympiad, year 1971

1971/3. Prove that the set of integers of the form contains an infinite subset in which every two members are relatively prime.
johnny is offline  
 
August 10th, 2009, 01:45 PM   #2
Global Moderator
 
CRGreathouse's Avatar
 
Joined: Nov 2006
From: UTC -5

Posts: 16,046
Thanks: 938

Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms
Re: International Mathematical Olympiad, year 1971

Hmm. If a | 2^n - 3, then a divides 2^(n + a - 1) - 3 because the period of 2^k - 3 mod a divides a - 1. So unless a < 5 (and even then it should work out, only a few cases must be tested) you have a does not divide 2^(n + a) - 3.

Not quite enough, but it feels like it's a step toward an answer.
CRGreathouse is offline  
August 10th, 2009, 04:22 PM   #3
Senior Member
 
Joined: Apr 2007

Posts: 2,140
Thanks: 0

Good solution to start out with, CRGreathouse. Honestly, I am a total beginner to the field of number theory. It would be a ways off until I can master number theory and tackle such IMO number theory problems...
johnny is offline  
August 10th, 2009, 09:07 PM   #4
Global Moderator
 
CRGreathouse's Avatar
 
Joined: Nov 2006
From: UTC -5

Posts: 16,046
Thanks: 938

Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms
Re:

Quote:
Originally Posted by johnny
Good solution to start out with, CRGreathouse. Honestly, I am a total beginner to the field of number theory. It would be a ways off until I can master number theory and tackle such IMO number theory problems...
Honestly this one baffles me. I think it's one of the harder ones, unless I'm missing some simple trick.
CRGreathouse is offline  
August 10th, 2009, 10:22 PM   #5
Senior Member
 
Joined: Apr 2007

Posts: 2,140
Thanks: 0

IMO problems are supposed to be hard problems. But, when you take a look at the solution of a IMO problem without solving it, you will be amazed how simple the solution is, so like you have said, there could be a simple trick that goes along with the above problem.
johnny is offline  
August 11th, 2009, 12:41 AM   #6
Global Moderator
 
CRGreathouse's Avatar
 
Joined: Nov 2006
From: UTC -5

Posts: 16,046
Thanks: 938

Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms
Re:

Quote:
Originally Posted by johnny
IMO problems are supposed to be hard problems. But, when you take a look at the solution of a IMO problem without solving it, you will be amazed how simple the solution is, so like you have said, there could be a simple trick that goes along with the above problem.
I'm not used to working on contest problems so I'm not good at finding tricks. Most of my methods on these problems have been fairly standard approaches, I think -- though the reciprocal problem turned out to be much simpler than I expected (because the problem was chosen to be unusually approachable, no doubt).

Hint on the problem: the approach of choosing congruence classes recursively by primes doesn't work (if the prime divides one less than the current modulus); I need a less restrictive approach.
CRGreathouse is offline  
August 31st, 2009, 05:47 AM   #7
Senior Member
 
Joined: Dec 2008

Posts: 160
Thanks: 0

Re: International Mathematical Olympiad, year 1971

Honestly, I do not see how tip from CG lead to the solution.
Here is a solution I propose:
Let we already have a sequence of that - are relatively prime to each other.
I show how to find that sequence is a sequence where all are relatively prime.
Let
Put - Euler function, then and is relatively prime with all
zolden is offline  
August 31st, 2009, 05:40 PM   #8
Senior Member
 
Joined: Apr 2007

Posts: 2,140
Thanks: 0

zolden, are you like mathematically gifted or something. . .?
johnny is offline  
September 1st, 2009, 11:51 AM   #9
Senior Member
 
Joined: Dec 2008

Posts: 160
Thanks: 0

Re: International Mathematical Olympiad, year 1971

I am just hanging around. Sometimes, interesting problems get posted.
zolden is offline  
September 1st, 2009, 04:44 PM   #10
Senior Member
 
Joined: Apr 2007

Posts: 2,140
Thanks: 0

Well, it's good to have good people on the forum! Stick around if you want, and we will discuss things, indeed!
johnny is offline  
Reply

  My Math Forum > Math Forums > Math Events

Tags
1971, international, mathematical, olympiad, year



Thread Tools
Display Modes


Similar Threads
Thread Thread Starter Forum Replies Last Post
Some questions about International Mathematical Olympiad Eminem_Recovery Math Events 9 January 23rd, 2011 05:36 AM
A problem from 32nd International Mathematical Olympiad johnny Math Events 1 September 2nd, 2009 08:55 AM
A problem from 31st International Mathematical Olympiad johnny Math Events 4 September 2nd, 2009 07:06 AM
The 8th Korean Mathematical Olympiad johnny Math Events 5 July 23rd, 2009 03:12 PM
Some questions about International Mathematical Olympiad Eminem_Recovery Algebra 1 December 31st, 1969 04:00 PM





Copyright © 2019 My Math Forum. All rights reserved.