You are using an out of date browser. It may not display this or other websites correctly.

You should upgrade or use an alternative browser.

You should upgrade or use an alternative browser.

- Thread starter AdkAdi
- Start date

- Joined
- Apr 22, 2015

- Messages
- 3,760

Hi Jomo (stupid phone keeps changing yer name to Joni). Had you intended to work with20 <= p/q <=21

20 <= 50p/q <= 21

or are you using a different example for illustration purposes?

In the given exercise, q cannot be 1,2,3,4,6,7,8,9,11,13,14,16,18,19,... because p values would not be Integers.

I'd started by writing

40/100 <= p/q <= 42/100

and thinking about how many p/q would equal 0.4 (i.e., equivalent fractions -- q is multiple of 5), and then I'd wondered if there might be a way to determine how many wouldn't.

(There are no additional fractions equivalent to 21/50, so the only p/q with q=50 would be 20/50 and 21/50.)

Manually checking with low q values, it appeared that the number (n) of p/q without a terminating decimal form appearing after q being a multiple of 5 might be increasing like this:

q, n

5, 0

10, 1

15, 1

20, 2

25, 2

30, 3

35, 3

etc

That would help with counting all p's and q's, but we don't want to include any repeats, so my approach would need a lot of manual checking.

- Joined
- Apr 22, 2015

- Messages
- 3,760

Hello Adk. What sorts of things has your class been discussing?I have tried transposing the variables

- Joined
- Oct 29, 2019

- Messages
- 1,188

@Otis is correct, in order to guide you we need to know what strategy your teacher expects you to use. Therefore please show some of your work. In the absence of this, here are a couple of extra ideas...

I'm quite a visual thinker, so personally I'd think about a method to count the number of integer (q, p) grid points in the light blue region of the following graph (including any grid points that lie ON the red lines).

OR, actually, I'd be thinking of writing a computer program to count the solutions since it's such a small set of q values!

I'm quite a visual thinker, so personally I'd think about a method to count the number of integer (q, p) grid points in the light blue region of the following graph (including any grid points that lie ON the red lines).

OR, actually, I'd be thinking of writing a computer program to count the solutions since it's such a small set of q values!

Last edited:

- Joined
- Apr 22, 2015

- Messages
- 3,760

That would be simplest, but I'm hoping the OP will teach me something from number theory.writing a computer program to count

- Joined
- Dec 30, 2014

- Messages
- 11,180

Yes, I did mean to write 20 <= 50p/q <= 21Hi Jomo (stupid phone keeps changing yer name to Joni). Had you intended to work with

20 <= 50p/q <= 21

- Joined
- Dec 30, 2014

- Messages
- 11,180

Computer program sometimes get in the way of real mathematics.@Otis is correct, in order to guide you we need to know what strategy your teacher expects you to use. Therefore please show some of your work. In the absence of this, here are a couple of extra ideas...

I'm quite a visual thinker, so personally I'd think about a method to count the number of integer (q, p) grid points in the light blue region of the following graph (including any grid points that lie ON the red lines).

View attachment 28892

OR, actually, I'd be thinking of writing a computer program to count the solutions since it's such a small set of q values!

- Joined
- Oct 29, 2019

- Messages
- 1,188

That would be simplest, but I'm hoping the OP will teach me something from number theory.

I know where you're both coming from, and (partly) agree with you both. It does seem very unlikely that @AdkAdi was being asked to write a computer algorithm to solve this. I was trying to illustrate that there are different approaches, and without seeing any work from OP how are we supposed to provide relevant help?Computer program sometimes get in the way of real mathematics.

Last edited:

- Joined
- Oct 29, 2019

- Messages
- 1,188

Here's an improved image and an extra hint for my first proposed method......I'd think about a method to count the number of integer (q, p) grid points in the light blue region of the following graph (including any grid points that lie ON the red lines).

HINT: Can you see that the number of grid intersection points in 0EAC will be double the number of grid intersection points in 0AC (but you'll need to be careful and take into account the grid intersection points that lie along the outer lines of the shapes).

NOTE: I have not worked this out to an end result, but I think this method could be used to yield a closed form solution for any upper-limit of q (not just 99)

- Joined
- Oct 6, 2005

- Messages
- 10,623

One way is to ask the OP questions and wait.without seeing any work from OP how are we supposed to provide relevant help?

Another way is to not wait but guess (including a proviso, perhaps).

On the other hand, many replies here are written for a general audience (not concerned with relevance for the OP per se, as long as there's relevance for some students in what they say).

I don't see any issues with your suggestions.

I am preparing for a Regional math Olympiad competition and for that I need to have a good amount of grip on Number Theory.Are you taking a number theory class? If not, then what class are you in and what has been discussed recently?

- Joined
- Apr 22, 2015

- Messages
- 3,760

No not at allAre you allowed to use any technology, in the competition?

[imath]\;[/imath]

- Joined
- Apr 22, 2015

- Messages
- 3,760

Then our choices are currently limited (for quick methods using paper & pencil) until someone posts what we're missing.No not at all

Have you tried thinking about a simpler form, similar to the given situation?

- Joined
- Oct 29, 2019

- Messages
- 1,188

Obtaining the answer using my suggested method was more complicated than I thought. There must be an easier method. But I'll show you my work anyway (I also verified the answer via computer)

20q ≤ 50p ≤ 21q

The LHS inequality is shown as line 0A and RHS as line 0B in the following graph...

#intersections in shaded area 0AB (including all grid intersections that occur ON the outer lines - subsequently referred to as "outers")

= 0AC*(with all outers) *+ ABDC *(with all outers except AC)* - 0BD *(with all outers except 0B)*

To calculate the number of grid intersection points within triangle 0AC, turn the triangle into rectangle 0EAC, subtract the number of intersections that occur on the diagonal 0A, and then divide by two, and finally add back the number of diagonal intersection points. For this to work, the outer edges of the rectangle must align with the grid intersection points. Therefore increase the range of q to 0≤q≤100 (which yields integer coordinates for A,B,C and D), and then at the end subtract the results for q=0 and q=100 to obtain the desired range of 1≤q≤99

At point E q=100

At points A and C, p=100*20/50 = 40

At points B and D, p=100*21/50 = 42

**OAC*** (with all outers) *

The number of grid point intersections on line 0A is Ia=21. The first few are (0,0) (2,5) (4,10) (6,15)...(40,100) therefore the total number is (100/5)+1

Number of intersections within OAC is ((40+1)*(100+1) - Ia )/2 + Ia = 2081

**ABDC*** (with all outers except AC)*

(42-40) * (100+1) = 202

**OBD*** (with all outers except on line 0B)*

The number of grid point intersections on line 0A is Ib=3. These are (0,0) (21,50) (42,100)

Number of intersections within ODB is ((42+1)*(100+1) - Ib)/2 = 2170

**INTERIM RESULT**

0AC + ABDC - 0BD

= 2081 + 202 - 2170

= 113

**FINAL RESULT**

Remove intersections for q=0, and q=100. When q=0 we have 0 ≤ p ≤ 0 therefore one option at (0,0)

and when q=100 we have 40 ≤ p≤ 42 therefore 3 options at (40,100) (41,100) (42,100)

Removing these gives number of (p,q)

= 113 - (1+3)

=**109**

The LHS inequality is shown as line 0A and RHS as line 0B in the following graph...

#intersections in shaded area 0AB (including all grid intersections that occur ON the outer lines - subsequently referred to as "outers")

= 0AC

To calculate the number of grid intersection points within triangle 0AC, turn the triangle into rectangle 0EAC, subtract the number of intersections that occur on the diagonal 0A, and then divide by two, and finally add back the number of diagonal intersection points. For this to work, the outer edges of the rectangle must align with the grid intersection points. Therefore increase the range of q to 0≤q≤100 (which yields integer coordinates for A,B,C and D), and then at the end subtract the results for q=0 and q=100 to obtain the desired range of 1≤q≤99

At point E q=100

At points A and C, p=100*20/50 = 40

At points B and D, p=100*21/50 = 42

The number of grid point intersections on line 0A is Ia=21. The first few are (0,0) (2,5) (4,10) (6,15)...(40,100) therefore the total number is (100/5)+1

Number of intersections within OAC is ((40+1)*(100+1) - Ia )/2 + Ia = 2081

(42-40) * (100+1) = 202

The number of grid point intersections on line 0A is Ib=3. These are (0,0) (21,50) (42,100)

Number of intersections within ODB is ((42+1)*(100+1) - Ib)/2 = 2170

0AC + ABDC - 0BD

= 2081 + 202 - 2170

= 113

Remove intersections for q=0, and q=100. When q=0 we have 0 ≤ p ≤ 0 therefore one option at (0,0)

and when q=100 we have 40 ≤ p≤ 42 therefore 3 options at (40,100) (41,100) (42,100)

Removing these gives number of (p,q)

= 113 - (1+3)

=

Last edited: