#LyX 2.4 created this file. For more info see https://www.lyx.org/ \lyxformat 620 \begin_document \begin_header \save_transient_properties true \origin unavailable \textclass book \begin_preamble \input defs \end_preamble \use_default_options true \maintain_unincluded_children no \language english \language_package default \inputencoding utf8 \fontencoding auto \font_roman "default" "default" \font_sans "default" "default" \font_typewriter "default" "default" \font_math "auto" "auto" \font_default_family default \use_non_tex_fonts false \font_sc false \font_roman_osf false \font_sans_osf false \font_typewriter_osf false \font_sf_scale 100 100 \font_tt_scale 100 100 \use_microtype false \use_dash_ligatures true \graphics default \default_output_format default \output_sync 0 \bibtex_command default \index_command default \float_placement class \float_alignment class \paperfontsize default \spacing single \use_hyperref false \papersize default \use_geometry false \use_package amsmath 1 \use_package amssymb 1 \use_package cancel 1 \use_package esint 1 \use_package mathdots 1 \use_package mathtools 1 \use_package mhchem 1 \use_package stackrel 1 \use_package stmaryrd 1 \use_package undertilde 1 \cite_engine basic \cite_engine_type default \biblio_style plain \use_bibtopic false \use_indices false \paperorientation portrait \suppress_date false \justification true \use_refstyle 1 \use_formatted_ref 0 \use_minted 0 \use_lineno 0 \index Index \shortcut idx \color #008000 \end_index \secnumdepth 3 \tocdepth 3 \paragraph_separation indent \paragraph_indentation default \is_math_indent 0 \math_numbering_side default \quotes_style english \dynamic_quotes 0 \papercolumns 1 \papersides 1 \paperpagestyle default \tablestyle default \tracking_changes false \output_changes false \change_bars false \postpone_fragile_content false \html_math_output 0 \html_css_as_file 0 \html_be_strict false \docbook_table_output 0 \docbook_mathml_prefix 1 \end_header \begin_body \begin_layout Standard \begin_inset Note Note status open \begin_layout Plain Layout TODO 3, 4, 12 (2pp., 1:14) \end_layout \end_inset \end_layout \begin_layout Standard \begin_inset ERT status open \begin_layout Plain Layout \backslash rexerc3[M24] \end_layout \end_inset An extended binary tree with \begin_inset Formula $m$ \end_inset external nodes determines a set of path lengths \begin_inset Formula $l_{1},l_{2},\dots,l_{m}$ \end_inset that describe the lengths of paths from the root to the respective external nodes. Conversely, if we are given a set of numbers \begin_inset Formula $l_{1},l_{2},\dots,l_{m}$ \end_inset , is it always possible to construct an extended binary tree in which these numbers are the path lengths in some order? Show that this is possible if and only if \begin_inset Formula $\sum_{j=1}^{m}2^{-l_{j}}=1$ \end_inset . \end_layout \begin_layout Standard \begin_inset ERT status open \begin_layout Plain Layout \backslash answer \end_layout \end_inset We assign each external node an interval of real numbers as follows: start with \begin_inset Formula $[l,u)=[0,1)$ \end_inset ; then, for each edge in the path from the root to the node, if it's a left edge, set \begin_inset Formula $[l,u)\gets[l,\frac{l+u}{2})$ \end_inset , and if it's a right edge, set \begin_inset Formula $[l,u)\gets[\frac{l+u}{2},u)$ \end_inset , so the interval's length is \begin_inset Formula $2^{-l}$ \end_inset , \begin_inset Formula $l$ \end_inset being the path length. It's easy to see that these intervals are disjoint and that, for each \begin_inset Formula $x\in[0,1)$ \end_inset , there is a special node whose interval contains \begin_inset Formula $x$ \end_inset . With this in mind: \end_layout \begin_layout Itemize \begin_inset Argument item:1 status open \begin_layout Plain Layout \begin_inset Formula $\implies]$ \end_inset \end_layout \end_inset This is precisely the sum of the lengths of the intervals, which is 1 because \begin_inset Formula $[0,1)$ \end_inset is the disjoint union of these intervals. \end_layout \begin_layout Itemize \begin_inset Argument item:1 status open \begin_layout Plain Layout \begin_inset Formula $\impliedby]$ \end_inset \end_layout \end_inset We just have to sort the path lengths in increasing order, assign consecutive intervals of length \begin_inset Formula $2^{-l_{k}}$ \end_inset starting from 0 and converting the intervals to paths (more precisely, to sequences of left/right turns), which we can do since the increasing order ensures that the starting point \begin_inset Formula $l_{k}$ \end_inset of an interval \begin_inset Formula $[l_{k},u_{k})$ \end_inset is a multiple of the length \begin_inset Formula $u_{k}-l_{k}$ \end_inset . These paths are all different and none is a prefix of another one, so they define the leaves of a binary tree. \end_layout \begin_layout Standard \begin_inset ERT status open \begin_layout Plain Layout \backslash rexerc4[M25] \end_layout \end_inset (E. S. Schwartz and B. Kallick.) Assume that \begin_inset Formula $w_{1}\leq w_{2}\leq\dots\leq w_{m}$ \end_inset . Show that there is an extended binary tree that minimizes \begin_inset Formula $\sum w_{j}l_{j}$ \end_inset and for which the terminal nodes in left to right order contain the respective values \begin_inset Formula $w_{1},w_{2},\dots,w_{m}$ \end_inset . \end_layout \begin_layout Standard \begin_inset ERT status open \begin_layout Plain Layout \backslash answer \end_layout \end_inset Let \begin_inset Formula $T$ \end_inset be an extended binary tree that minimizes \begin_inset Formula $\sum w_{j}l_{j}$ \end_inset . For \begin_inset Formula $i