• Log InLog In
  • Register
Liquid`
Team Liquid Liquipedia
EST 15:42
CET 21:42
KST 05:42
  • Home
  • Forum
  • Calendar
  • Streams
  • Liquipedia
  • Features
  • Store
  • EPT
  • TL+
  • StarCraft 2
  • Brood War
  • Smash
  • Heroes
  • Counter-Strike
  • Overwatch
  • Liquibet
  • Fantasy StarCraft
  • TLPD
  • StarCraft 2
  • Brood War
  • Blogs
Forum Sidebar
Events/Features
News
Featured News
Team Liquid Map Contest #2312[ASL22] Finals Preview: Sweet Victory!12[ASL22] Ro4 Preview: Mirror Mirror6[ASL22] Ro8 Preview: Within Reach5[ASL22] Ro8 Preview: In A Tizzy11
Community News
Weekly Cups (Nov 9-15): Clem and herO take over6Dark completes military service, returns to SC217[BSL23] RO16 Group Stage20Weekly Cups (Nov 2-8): herO back on top?2Weekly Cups (Oct 26 - Nov 1): MaxPax, herO, Solar win0
StarCraft 2
General
Weekly Cups (Nov 9-15): Clem and herO take over SC4ALL: II Indiegogo Campaign Announcement No more SC2 streamers on team liquid? Team Liquid Map Contest #23 StarCraft open world shooter announced at BlizzCon
Tourneys
RSL goes to London! 2026 Offline Finals Nov 21-22 soO & FanTaSy return! SC2 Kevin Scrim 4v4 (Nov 16) Sparkling Tuna Cup - Weekly Open Tournament Sea Duckling Open (Global, Bronze-Diamond) Dark returns! GSL CK #7 4v4 Team Battle (Nov 19)
Strategy
[H] ZvP Mid-Late Game: Stalkers Collossi HT
Custom Maps
[G] How to playtest arcade maps Starcraft 2 Advance [D] the control group Simple Questions/Answers
External Content
Mutation # 553 Undermined The PondCast: SC2 News & Results Mutation # 552 Secret Storm Mutation # 551 Robotic Revival
Brood War
General
People still play BW? List of top players active on ShieldBattery SC4ALL: II Indiegogo Campaign Announcement XUN appreciation thread BW General Discussion
Tourneys
$3,000 Sijosae Tier 2,3,4 Cup (Nov 23-24 2026) [BSL23] Ro16 Group B - Saturday 21:00 CET 2v2v2v2 Tournament Stage 2: Players KCM Race Survival 2026 Season 4
Strategy
Pluto's TvP 5Marine 2Medic Push Simple Questions, Simple Answers Infested Terran strategies in 2026 Nuke strategy worked in K-League 2026-11-09
Other Games
General Games
Nintendo Switch Thread The PlayStation 5 Stormgate/Frost Giant Megathread Warcraft III: The Frozen Throne Free Space RTS Game, optimised f. Phone/Tablet etc
Dota 2
League of Legends
[TL LoL EUW IHs] Teemo shall perish
Heroes of the Storm
Heroes of the Storm 2.0
Hearthstone
Deck construction bug
TL Mafia
TL Mafia Community Thread
Community
General
US Politics Mega-thread The Games Industry And ATVI Russo-Ukrainian War Thread Things Aren’t Peaceful in Palestine Trading/Investing Thread
Fan Clubs
Fan Club Resource Thread Reynor Fan Club The Flash Fan Club
Media & Entertainment
Movie Discussion! Anime Discussion Thread [Manga] One Piece
Sports
Formula 1 Discussion Football (Soccer) Thread TeamLiquid Health and Fitness Initiative For 2023
World Cup 2022
Tech Support
Computer Build, Upgrade & Buying Resource Thread
TL Community
The Automated Ban List Recent Gifted Posts
Blogs
The time I organised my…
AssyrianKing
Why I built Repalyzer (1.1.…
BlueStar
Innovate or Game Over?
TrAiDoS
ShieldBattery on Mac
Kraekkling
Can Bots Beat Pros?? Starcr…
namkraft
James Bond movies ranking - pa…
Topin
StarCraft improvement
iopq
Socialism Anyone?
GreenHorizons
Customize Sidebar...

Website Feedback

Closed Threads



Active: 10565 users

Fun Math Problem - Page 2

Blogs > EtherealDeath
Post a Reply
Prev 1 2 All
ero
Profile Joined April 2009
United States66 Posts
August 27 2009 13:15 GMT
#21
On August 27 2009 11:46 EtherealDeath wrote:
Within this bounded interval are some set number of other bounded intervals, which may or may not intersect with other bounded intervals. For example, one possible set of intervals is {[1,100],[2,36],[45,798]}.


If I understand this problem correctly, then in this example the choice of points would be {100, 2, 798}, where the third number (798) could really be anything from 192 to 798.

Is this right?
starfries
Profile Blog Joined July 2009
Canada3508 Posts
August 27 2009 13:33 GMT
#22
On August 27 2009 21:52 ninjafetus wrote:
Restating the problem more clearly for anyone still confused.

You are given an closed interval [a,b], and some number of closed subintervals S_i = [a_i, b_i].
For each S_i, choose a c_i contained in [a_i, b_i] such that min_{i,j} (c_i, c_j) is maximized.

Wait, that might not be any more clear at all, save for math people who already get it...

In other words, each subinterval gets a point. Choose the points so that the distance between the two closest points is maximized over all possible choices of points.


That was sooooo much clearer, thanks
DJ – do you like ramen, Savior? Savior – not really. Bisu – I eat it often. Flash – I’m a maniac! | Foxer Fighting!
EtherealDeath
Profile Blog Joined July 2007
United States8366 Posts
August 27 2009 21:38 GMT
#23
On August 27 2009 18:56 Muirhead wrote:
My argument definitely works. I know a lot of people on this site spurt nonsense solutions to these kinds of questions, but I do actually have a math/IMO background . It's a little complicated, but if you think about it you'll understand it. I am well aware that changing a_1 can change every other a_i.

Alternatively, note that my argument proves that the coordinates of the solution points are rational linear combinations of the coordinates of the endpoints. Furthermore, the argument provides natural bounds on the denominators of the coefficients. Thus, we only need to check a finite number of d as in severedevil's argument.



Hm.. I am sort of seeing how it would be piecewise, but not totally confident on it yet. Will have to think about it some more when I can I suppose.
moriya
Profile Joined March 2009
United States54 Posts
Last Edited: 2009-08-28 05:34:55
August 28 2009 05:28 GMT
#24
Well, I am not sure if I totally get it but basically that's a smart idea.

One problem could be from the sorting. Have you assumed that the smallest point in the optimum solution must be picked from [a1,b1] so that you can run P for [a2,b2] to [an,bn]? Think about this testing data:[1,10] [1,15] [3,20] [4,5]. The smallest point in the solution is 4 which is picked from [4,5] set. So actually we need do P for n-1 times.

Correct me muirhead if I didnot get you
On August 27 2009 13:49 Muirhead wrote:
I do not know (or believe) that there is a terribly simple formula for the answer.

If I just had to write a computer program to find an exact answer, I would proceed inductively. Suppose that there are n intervals, and that I have a computer program that can find the answer given n-1 intervals.

The computer program (call it P) that solves for n-1 intervals would receive input of the form [a_1,b_1],[a_2,b_2],...,[a_{n-1},b_{n-1}] where the a_i are inputted in nondecreasing order.

Furthermore, suppose the computer program P would give me my answer as a function of a_1, assuming a_1 <= a_2 and that the other a_i and b_i are fixed. The function would be piecewise linear and therefore easy to express.

I claim that, given P, it is easy to construct a similar program which works with an input of n intervals. The new program Q would insert a test value of a_1. Then it would run P on [a_2,b_2],...,[a_n,b_n], spitting out a function of a_2. It would compute the value of a_2 such that the maximum minimum distance spit out by that function is as close to |a_1-a_2| as possible, thus solving the problem for the test value of a_1. Through judicious choices of test values of a_1, the full function of a_1 could be discovered. This is because Q knows the answer it should spit out is a piecewise linear function of a_1 with the number of distinct linear components a bounded function of n.

Prev 1 2 All
Please log in or register to reply.
Live Events Refresh
BSL
05:00
S23 - Ro16 Group D
Bonyth vs Doodle
Kyrie vs Jimin
ZZZero.O244
LiquipediaDiscussion
IPSL
02:00
Ro16 Group A
Ret vs ggnore13
nOmaD vs Aether
Liquipedia
RSL Revival
22:00
Offline Finals: Playoffs
Serral vs herOLIVE!
Tasteless2691
ComeBackTV 1463
RotterdaM1244
IntoTheiNu 701
TaKeTV 594
IndyStarCraft 472
kabyraGe 262
LamboSC2232
Rex63
3DClanTV 62
LiquipediaDiscussion
[ Submit Event ]
Live Streams
Refresh
StarCraft 2
Tasteless 2691
RotterdaM 1244
IndyStarCraft 472
LamboSC2 232
ProTech132
Rex 63
JuggernautJason12
EmSc Tv 9
StarCraft: Brood War
Britney 26705
Shuttle 340
ZZZero.O 244
Noble 6
Dota 2
Gorgc7853
Counter-Strike
pashabiceps1727
gobbtv67
Heroes of the Storm
Khaldor510
Liquid`Hasu436
Other Games
tarik_tv4296
Grubby2739
FrodaN1377
B2W.Neo683
ToD77
Mew2King63
Pyrionflax37
Railgan10
Organizations
Other Games
gamesdonequick964
StarCraft 2
EmSc Tv 9
[ Show 15 non-featured ]
StarCraft 2
• Adnapsc2 13
• maralekos8
• AfreecaTV YouTube
• intothetv
• Kozan
• IndyKCrew
• Migwel
StarCraft: Brood War
• 80smullet 13
• BSLYoutube
• STPLYoutube
• ZZZeroYoutube
Dota 2
• WagamamaTV659
Other Games
• imaqtpie975
• Shiphtur378
• tFFMrPink 10
Upcoming Events
Replay Cast
2h 19m
Tournament
11h 19m
WardiTV Weekly
15h 19m
Ultimate Battle
15h 19m
Bisu vs Light
Kung Fu Cup
1d 14h
Solar vs Classic
ByuN vs SHIN
PiGosaur Cup
2 days
The PondCast
3 days
KCM Race Survival
3 days
Liquipedia Results

Completed

Proleague 2026-11-17
Blizzard Classic Cup 2026
HCC Season 3

Ongoing

Acropolis #5
KCM Race Survival 2026 Season 4
International ShieldBattery League
BSL Season 23
IPSL Winter 2026-27
RSL Offline Finals
Calamity Cup Div. A Season 8
Underdog Cup 2026 Div 2-3
Stake Ranked Episode 6
BLAST Rivals Fall 2026
IEM Beijing 2026
PGL Masters Bucharest 2026
Stake Ranked Episode 5
1win Private Club #2
Thunderpick World Champ. '26
ESL Pro League Season 24
Stake Ranked Episode 4
1win Private Club #1
Logitech G Play Connect 2026
SL StarSeries Fall 2026
FISSURE Playground #3

Upcoming

CSL Season 23: Qualifier 1
Sector 591
Sijosae Cup
CSL Season 23: Qualifier 2
YSL S4
SC4ALL II: Brood War
CSL 2026 Winter (S23) - 3v3
HSC XXX
Stellar Fest 2: Lunar Cup
StarCraft2 Weekly Open Tournament 2026 Grand Finals
SC4ALL II: StarCraft II
Kung Fu Cup 2026 Grand Finals
IEM Kraków 2027
PGL Bucharest 2027
BLAST Bounty Winter 2027
PGL Major Singapore 2026
TLPD

1. ByuN
2. TY
3. Dark
4. Solar
5. Stats
6. Nerchio
7. sOs
8. soO
9. INnoVation
10. Elazer
1. Rain
2. Flash
3. EffOrt
4. Last
5. Bisu
6. Soulkey
7. Mini
8. Sharp
Sidebar Settings...

Advertising | Privacy Policy | Terms Of Use | Contact Us

Original banner artwork: Jim Warren
The contents of this webpage are copyright © 2026 TLnet. All Rights Reserved.