Hi!

Some time ago I've solved problem 10104 (Euclid Problem) by using Euclid's Extended Algorithm. The thing is that I didn't even considered the additional restrictions (|x|+|y| = minimum, x<= y if there's a tie). Recently I re-read the problem and come to wonder if the algorithm always gives a pair with those restrictions or if I just was lucky and the tests are incomplete. I've been trying to prove it (or finding a conter-example) and it seems that the algorithm aways meets the restrictions but haven't found a proof yet.

What I have tried is:

d = ax + by

So the general solutions are of the form:

d = a(x + (b/d)t) + b(y -(a/d)t)

Plotting the equation |x + (b/d)t| + |y -(a/d)t|, we have three line regions which make a V form (well, not exactly but kind of). So if the point we have is the smallest, then as we decrease (or increase) the value of t the sums will also increase. As the smallest is supposed to be t= 0, we just have to check for the values of t= 1 and t= -1. So we have to prove that:

|x| + |y| = |x + (b/d)| + |y - (a/d)|

|x| + |y| = |x - (b/d)| + |y + (a/d)|

and here's where I'm stuck (well, I've some more stuff but not much).

Also, I think that the minimum value (not necessarily integer) that the function can get is:

t = 2d(y-x)/(a+b)

I don't remember how I got this formula this value, but I didn't proved it (I'm not very good proving things, I usually get things by observation and "instinct"). I think this formula might also lead to something interesting.

Another method that I haven't tried much that might be a good idea is checking the minimum values of x and y as we calculate Euclid's Extended. The base values for x and y are 0 and 1, so this ones are obviously minimum, so we might check if the minimum property conserves as we calculate the new values of x and y. Have been able to prove this though.

I wanted to hear some comments as there might be better ways of proving this. Anyway, any help/comments/ideas appreciated!

Best regards,

Pier

## Eulcid Problem

Let's talk about algorithms!

**Moderator:** Board moderators

- Pier
- New poster
**Posts:**38**Joined:**Thu Mar 27, 2003 9:12 pm**Location:**Aguascalientes, Mexico-
**Contact:**

### Eulcid Problem

Post
by **Pier** » Sat Jul 01, 2006 6:12 am

There are 10 kind of people on this world: those who understand binary and those who don't!

Jump to

- Real Time Contests and Last Minute Information
- ↳ General
- ↳ Real Time Clarification
- ↳ Fixing Mistakes
- ↳ HOWTOs
- ↳ Bugs and suggestions
- New system
- ↳ FAQ
- ↳ Bugs and suggestions
- Let's make some programs!
- ↳ Other words
- ↳ Algorithms
- ↳ New features
- Help on the Problemset
- ↳ Volume 1 (100-199)
- ↳ Volume 2 (200-299)
- ↳ Volume 3 (300-399)
- ↳ Volume 4 (400-499)
- ↳ Volume 5 (500-599)
- ↳ Volume 6 (600-699)
- ↳ Volume 7 (700-799)
- ↳ Volume 8 (800-899)
- ↳ Volume 9 (900-999)
- ↳ Volume 10 (1000-1099)
- ↳ Volume 11 (1100-1199)
- ↳ Volume 12 (1200-1299)
- ↳ Volume 13 (1300-1399)
- ↳ Volume 14 (1400-1499)
- ↳ Volume 15 (1500-1599)
- ↳ Volume 16 (1600-1699)
- ↳ Volume 17 (1700-1799)
- ↳ Volume 100 (10000-10099)
- ↳ Volume 101 (10100-10199)
- ↳ Volume 102 (10200-10299)
- ↳ Volume 103 (10300-10399)
- ↳ Volume 104 (10400-10499)
- ↳ Volume 105 (10500-10599)
- ↳ Volume 106 (10600-10699)
- ↳ Volume 107 (10700-10799)
- ↳ Volume 108 (10800-10899)
- ↳ Volume 109 (10900-10999)
- ↳ Volume 110 (11000-11099)
- ↳ Volume 111 (11100-11199)
- ↳ Volume 112 (11200-11299)
- ↳ Volume 113 (11300-11399)
- ↳ Volume 114 (11400-11499)
- ↳ Volume 115 (11500-11599)
- ↳ Volume 116 (11600-11699)
- ↳ Volume 117 (11700-11799)
- ↳ Volume 118 (11800-11899)
- ↳ Volume 119 (11900-11999)
- ↳ Volume 120 (12000-12099)
- ↳ Volume 121 (12100-12199)
- ↳ Volume 122 (12200-12299)
- ↳ Volume 123 (12300-12399)
- ↳ Volume 124 (12400-12499)
- ↳ Volume 125 (12500-12599)
- ↳ Volume 126 (12600-12699)
- ↳ Volume 127 (12700-12799)
- ↳ Volume 128 (12800-12899)
- ↳ Volume 129 (12900-12999)
- ↳ Volume 130 (13000-13099)
- ↳ Volume 131 (13100-13199)
- Help on languages
- ↳ C
- ↳ C++
- ↳ Pascal
- ↳ Java
- Off Topic
- ↳ Off topic (General chit-chat)
- Category
- ↳ ACM ICPC Archive Board