• Log InLog In
  • Register
Liquid`
Team Liquid Liquipedia
EDT 21:28
CEST 03:28
KST 10:28
  • 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
RSL Season 1 - Final Week6[ASL19] Finals Recap: Standing Tall12HomeStory Cup 27 - Info & Preview18Classic wins Code S Season 2 (2025)16Code S RO4 & Finals Preview: herO, Rogue, Classic, GuMiho0
Community News
Esports World Cup 2025 - Brackets Revealed7Weekly Cups (July 7-13): Classic continues to roll2Team TLMC #5 - Submission extension2Firefly given lifetime ban by ESIC following match-fixing investigation17$25,000 Streamerzone StarCraft Pro Series announced7
StarCraft 2
General
Esports World Cup 2025 - Brackets Revealed Who will win EWC 2025? Team TLMC #5 - Submission extension The GOAT ranking of GOAT rankings Esports World Cup 2025 - Final Player Roster
Tourneys
RSL: Revival, a new crowdfunded tournament series FEL Cracov 2025 (July 27) - $8000 live event $5,100+ SEL Season 2 Championship (SC: Evo) WardiTV Mondays Sparkling Tuna Cup - Weekly Open Tournament
Strategy
How did i lose this ZvP, whats the proper response Simple Questions Simple Answers
Custom Maps
External Content
Mutation # 482 Wheel of Misfortune Mutation # 481 Fear and Lava Mutation # 480 Moths to the Flame Mutation # 479 Worn Out Welcome
Brood War
General
BW General Discussion Flash Announces (and Retracts) Hiatus From ASL Starcraft in widescreen BGH Auto Balance -> http://bghmmr.eu/ A cwal.gg Extension - Easily keep track of anyone
Tourneys
Cosmonarchy Pro Showmatches [Megathread] Daily Proleagues CSL Xiamen International Invitational [BSL20] Non-Korean Championship 4x BSL + 4x China
Strategy
Simple Questions, Simple Answers I am doing this better than progamers do.
Other Games
General Games
Nintendo Switch Thread Stormgate/Frost Giant Megathread Path of Exile CCLP - Command & Conquer League Project The PlayStation 5
Dota 2
Official 'what is Dota anymore' discussion
League of Legends
Heroes of the Storm
Simple Questions, Simple Answers Heroes of the Storm 2.0
Hearthstone
Heroes of StarCraft mini-set
TL Mafia
TL Mafia Community Thread Vanilla Mini Mafia
Community
General
US Politics Mega-thread Russo-Ukrainian War Thread Summer Games Done Quick 2025! Things Aren’t Peaceful in Palestine Stop Killing Games - European Citizens Initiative
Fan Clubs
SKT1 Classic Fan Club! Maru Fan Club
Media & Entertainment
Movie Discussion! [Manga] One Piece Anime Discussion Thread [\m/] Heavy Metal Thread
Sports
Formula 1 Discussion TeamLiquid Health and Fitness Initiative For 2023 2024 - 2025 Football Thread NBA General Discussion NHL Playoffs 2024
World Cup 2022
Tech Support
Computer Build, Upgrade & Buying Resource Thread
TL Community
The Automated Ban List
Blogs
Men Take Risks, Women Win Ga…
TrAiDoS
momentary artworks from des…
tankgirl
from making sc maps to makin…
Husyelt
StarCraft improvement
iopq
Trip to the Zoo
micronesia
Customize Sidebar...

Website Feedback

Closed Threads



Active: 501 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
Replay Cast
00:00
SEL Masters #4 - Day 2
CranKy Ducklings108
Liquipedia
[ Submit Event ]
Live Streams
Refresh
StarCraft 2
Nina 236
Livibee 130
ProTech56
StarCraft: Brood War
Artosis 836
Icarus 4
Dota 2
monkeys_forever919
NeuroSwarm142
League of Legends
JimRising 709
Trikslyr91
Counter-Strike
Fnx 1527
taco 318
Super Smash Bros
hungrybox799
Other Games
summit1g14628
shahzam1670
Day[9].tv425
C9.Mang0219
Maynarde158
Mew2King32
RuFF_SC219
Organizations
Other Games
gamesdonequick3522
BasetradeTV38
StarCraft 2
Blizzard YouTube
StarCraft: Brood War
BSLTrovo
sctven
[ Show 16 non-featured ]
StarCraft 2
• Berry_CruncH147
• Mapu6
• AfreecaTV YouTube
• intothetv
• Kozan
• IndyKCrew
• LaughNgamezSOOP
• Migwel
• sooper7s
StarCraft: Brood War
• BSLYoutube
• STPLYoutube
• ZZZeroYoutube
League of Legends
• Doublelift5923
• Scarra1626
• Rush627
Other Games
• Day9tv425
Upcoming Events
Replay Cast
8h 32m
WardiTV European League
14h 32m
ShoWTimE vs sebesdes
Percival vs NightPhoenix
Shameless vs Nicoract
Krystianer vs Scarlett
ByuN vs uThermal
Harstem vs HeRoMaRinE
PiGosaur Monday
22h 32m
uThermal 2v2 Circuit
1d 14h
Replay Cast
1d 22h
The PondCast
2 days
Replay Cast
2 days
Epic.LAN
3 days
CranKy Ducklings
4 days
Epic.LAN
4 days
[ Show More ]
BSL20 Non-Korean Champi…
4 days
Bonyth vs Sziky
Dewalt vs Hawk
Hawk vs QiaoGege
Sziky vs Dewalt
Mihu vs Bonyth
Zhanhun vs QiaoGege
QiaoGege vs Fengzi
Sparkling Tuna Cup
5 days
Online Event
5 days
BSL20 Non-Korean Champi…
5 days
Bonyth vs Zhanhun
Dewalt vs Mihu
Hawk vs Sziky
Sziky vs QiaoGege
Mihu vs Hawk
Zhanhun vs Dewalt
Fengzi vs Bonyth
Liquipedia Results

Completed

2025 ACS Season 2: Qualifier
RSL Revival: Season 1
Murky Cup #2

Ongoing

JPL Season 2
BSL 2v2 Season 3
CSL 17: 2025 SUMMER
Copa Latinoamericana 4
Jiahua Invitational
BSL20 Non-Korean Championship
Championship of Russia 2025
FISSURE Playground #1
BLAST.tv Austin Major 2025
ESL Impact League Season 7
IEM Dallas 2025
PGL Astana 2025
Asian Champions League '25
BLAST Rivals Spring 2025
MESA Nomadic Masters

Upcoming

CSL Xiamen Invitational
CSL Xiamen Invitational: ShowMatche
2025 ACS Season 2
CSLPRO Last Chance 2025
CSLPRO Chat StarLAN 3
BSL Season 21
K-Championship
RSL Revival: Season 2
SEL Season 2 Championship
uThermal 2v2 Main Event
FEL Cracov 2025
Esports World Cup 2025
Underdog Cup #2
ESL Pro League S22
StarSeries Fall 2025
FISSURE Playground #2
BLAST Open Fall 2025
BLAST Open Fall Qual
Esports World Cup 2025
BLAST Bounty Fall 2025
BLAST Bounty Fall Qual
IEM Cologne 2025
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 © 2025 TLnet. All Rights Reserved.